《《算法与数据结构》实验(上机)教学大纲》由会员分享，可在线阅读，更多相关《《算法与数据结构》实验(上机)教学大纲（6页珍藏版）》请在金锄头文库上搜索。
1、 算法与数据结构 实验 (上机 )教学大纲课程名称 ： 中文名称 ： 算法与数据结构 ， 英文名称 ： Data Structure and Algorithms实验 学时 ： 10 学时 （ 必做 实验 6学时 ， 选作 实验 4学时 ）适用专业 ： 电气信息类及仪器仪表类各专业一 、 实验 课程的性质 、 目的与任务 ： 算法与数据结构 是电信学院各专业的一门专业基础必修课 ， 是理论与实践并重的课程 。 实验 是该课 程 实践教学环节的重要 环节 ， 它的内容覆盖了算法与数据结构的各个主要部分 。 通过 实验 可以加深对数据结构基本概念 、 基本理论的理解 ， 使学生巩固和运用所学 知识
2、以解决实际的具体问题 ， 同时提高程序设计和实际操作的能力 ， 在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练 。 原则上要求学生针对实际 问题 进行 数据结构设计 、 算法设计 、 编程调试 、 算法测试和优化 ， 获得运行结果 ， 并作为课程考核内容的一部分 ， 也 为后续课程的学习打下良好的基础 。二 、 实 验 报告内容 问题描述 ： 包括 需求分析 、 实现 目标 、 任务 、 条件和约束的描述 。 充分地分析和理解问题本身 ， 弄清要求做什么 ，包括功能要求 、 性能要求 、 设计要求和约束以及基本数据特性 ， 数据间的联系等 。 设计 ： 包括概要设
3、计和详细设计在概要设计中 ， 第一步先进行 数据结构设计 ： 针对要求解决的问题 ， 考虑各种可能的数据结构 ， 还可以根据算法的时间复杂度和空间复杂度 一起考虑 ， 以 确定 最合适的 数据结构 ， 主要描述逻辑结构 。第二步进行 关键 算法 设计 ： 对每个算法的功能及初始条件和操作结果认真分析确定 ， 并针对模块化 开发的 特点 ， 自顶向下分解成若干顺序模块 ， 确定 模块间的相互关系以及模块之间的信息交换问题 。第三步设计 主控 模块 及功能模块层次 间的 结构 ；在 详细设计 中 ， 第一步对数据结构的存储结构进行描述 ， 对数据结构 的逻辑结构和物理结构进行定义 ， 掌握其特点和
4、映射关系 。第二步对 每个算法 进行实现 ， 包括输入 、 处理和输出 的描述 。程序代码 尽可能的多加 注释 ， 用 C 语言或 C 语言实现 。3 测试 ： 准备典型测试数据和测试方案 ， 对 测试结果 进行 分析与讨论 ， 对 测试过程中遇到的主要问题及所采用的解决措施 进行总结 ， 以优化算法 。 使用说明和作业小结 （ 如果有 ） ： 使用说明主要描述如何使用你的程序以及使用时的主要事项 ； 在小结中说明 实验过程中碰到的问题 ， 算法的 改进 思想 、 经验和体会 。 打印一份程序清单及运行示例的结果 。 （ 如果任课老师要求提交电子版 ， 则按时上传 ）三 实 验 内容 、 要求
5、及学 时分配 ： 算法与数据结构 课程的实验内容比较丰富 ， 但为了在理论课程学习的同时要求学生通过实践掌握必要的知识以外 ， 还给学生提供一个自由发挥的空间 ， 因此在实践环节上提供了必做实验和选做实验两项 ， 在不同的实验中 ， 较为基础并且必须掌握的内容为基本实验 ， 在此基础上进而研究 ， 有一些 综合性的 扩展实验 ， 可供 感兴趣的学生在课外完成 ， 培养其综合应用和对实际问题分析与解决的能力 。（ 一 ） 必做实验 （ 6学时 ）1、 线性表的 存储结构 定义及基本操作 （ 2学时 ）2、 栈和队列的定义及基本操作 （ 2学时 ）3、 二叉树的定义及基本操作 （ 2学时 ）（ 二
6、 ） 选做实验 （ 六选二 ， 4 学时 ）1、 线性表的综合应用 （ 2学时 ）2、 栈和队列的综合应用 （ 2学时 ）3、 赫夫曼编码及其应用 （ 2学时 ）4、 图及其应用 （ 2学时 ）5、 最短路径和关键路径的研究与实现 （ 2学时 ）6、 查找和排序算法的实现 （ 2学时 ）四 实验的具体要求和指导 ：实验一 ： 线性表的存储结构定义及基本操作 （ 必做 ： 基本 2 学时 ， 扩展 4 学时 ）实验目的 ：掌握线性表的逻辑特征掌握线性表顺序存储结构的特点 ， 熟练掌握 顺序 表的基本运算熟练掌握线性表的 链式存储结构定义及基本操作理解 循环链表和双链表的特点和基本运算加深对顺序存
7、储数据结构的理解 和 链式存储数据结构的理解 ， 逐步培养解决实际问题的编程能力实验内容 ：（ 1） 基本实验内容 ：建立顺序表 ， 完成顺序表的基本操作 ： 初始化 、 插入 、 删除 、 逆转 、 输出 、 销毁 , 置空表 、 求表长 、 查找元素 、判线性表是否为空 ；建立单链表 ， 完成链表 （ 带表头结点 ） 的基本操作 ： 建立链表 、 插入 、 删除 、 查找 、 输出 ； 其 它 基本操作还有销毁链表 、 将链表置为空表 、 求链表的长度 、 获取某位置结点的内容 、 搜索结点 。（ 2） 扩展实验内容 ：查前驱元素 、 查后继元素 、 顺序表合并 ， 两个有序 单 链表的合
8、并操作 等 。实验 二 ： 线性表的综合应用 （ 选做 ： 2学时 ）实验目的 ：掌握顺序表和链表的概念 ， 学会对问题进行分析 ， 选择恰当的逻辑结构和物理结构加深对顺序表和链表的理解 ， 培养解决实际问题的编程能力实验内容 :实现一元稀疏多项式的表示及基本操作 （ 建立 、 销毁 、 输出 、 加法 、 减法 、 乘法等操作 ）；实验三 ： 栈和队列的 定义 及基本操作 （ 必做 ： 2学时 ）实验目的 ：熟练掌握栈和队列的特点掌握栈的定义和基本操作 ， 熟练掌握顺序栈的操作及应用掌握对列的定义和基本操作 ， 熟练掌握链式队列的操作及应用 , 掌握环形队列的入队和出队等基本操作加深对栈结构
9、和队列结构的理解 ， 逐步培养 解决实际问题的编程能力实验内容 :定义顺序栈 ， 完成栈的基本操作 ： 空栈 、 入栈 、 出栈 、 取栈顶元素 ；实现十进制数与八进制数的转换 ， 十进制数与十六进制数的转换和任意进制之间的转换 ；定义链式队列 ， 完成队列的基本操作 ： 入队和出队 ；实验 四 ： 栈和队列的 综合应用 （ 选做 ： 2 学时 ）实验目的 ：熟悉栈的定义和栈的基本操作熟悉队列的定义和栈的基本操作掌握递归和非递归算法的实现技术和实际应用加深对栈结构的理解 ， 培养解决实际问题的编程能力 。实验内容 :实现 Hanoi塔的问题 ；完成迷宫问题或马踏 棋盘问题求解 。实验 五 ：
10、二叉树的定义及基本操作 （ 必做 ： 基本 2学时 ， 扩展 4 学时 ）实验目的 ：熟练掌握二叉树的 二叉链表 存储结构掌握二叉树的非线性和递归性特点熟练掌握二叉树的递归遍历操作的实现方法 ， 掌握二叉树的非递归遍历操作的实现掌握线索二叉树的定义和基本操作加深对二叉树结构和性质的理解 逐步培养解决实际问题的编程能力实验内容 :（ 1） 基本实验内容 ：定义 二叉树的链式存储结构 ；实现二叉树的基本操作 ： 建空树 、 销毁二叉树 、 生成二叉树 (先序 ,中序或后序 )、 判二叉树是否为空 、 求二叉树的深度 、 求二叉树的根 等基本算法 ；实现二叉树的递归 (先序 、 中序或后序 )遍历算
11、法 ；（ 2） 扩展实验内容 ：求某一个结点的双亲结点 , 求某一个结点的左孩子 （ 或右孩子 ） 结点 ； 求某一个孩子的左兄弟 （ 或右兄弟 ） 算法 ；利用栈 ， 实现二叉树的非递归 (先序 、 中序或后序 )遍历算法 ；利用队列 ， 实现 层序递归遍历二叉树 ；定义线索二叉树的 链式存储结构 ， 建立线索二叉树 ， 实现线索二叉树的插入和删除操作 ；实验 六 ： 赫夫曼 编码 及其应用 （ 选做 ： 基本 2学时 ， 扩展 2 学时 ）实验目的 ：掌握 赫夫曼 树的概念 、 存储结构掌握建立 赫夫曼 树和 赫夫曼 编码的方法及带权路径长度 的计算熟练掌握二叉树的应用实验内容 :（ 1）
12、 基本实验内容 ： 实现 赫夫曼 树的生成 ， 完成 赫夫曼 编码 的输出 ；（ 2） 扩展实验内容 ： 完成一组码字的 赫夫曼 编码及解码 (以一个文本文件的内容为例 ).实验 七 ： 图 及其 应用 （ 选做 ： 2学时 ）实验目的 ：熟练掌握 图的两种存储结构 (邻接矩阵和邻接表 )的表示方法掌握 图的基本运算及应用加深对图的理解 ， 逐步培养解决实际问题的编程能力实验内容 :采用邻接表或邻接矩阵方式存储图 ， 实现图的深度遍历和广度遍历 ；用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径 。实验 八 ： 最短路径和关键路径的研究与实现 （ 选做 ： 2 学时 ）实验目的 ：掌握图
13、的邻接矩阵 、 邻接表的表示方法掌握迪杰斯特拉和弗洛伊德的最短路径 算法理解拓扑排序 ， 掌握关键路径的算法加深对图的理解 ， 逐步培养解决实际问题的编程能力实验内容 ：最短路径和关键路径的 实现实验 九 ： 查找和排序算法的实现 （ 选做 ： 基本 2 学时 ， 扩展 4学时 ）实验目的 ：掌握有序表 、 无序表 查找的基本思想及存储 、 运算的实现熟练掌握常用 排序 算法 的基本思想及实现深刻理解各种算法的特点 ， 并加以灵活应用加深对查找 和排序 的理解 ， 逐步培养解决实际问题的 编程能力实验内容 :（ 1） 基本实验内容 ：建立一个无序表并实现其上的顺序查找 ； 建立一个有序表并实现
14、其上的折半查找 ；实现插入排序 、 起泡排序 、 快速排序和希尔排序 的基本算法 ；（ 2） 扩展实验内容 ：构造哈希函数 ， 实现哈希查找 ；建立二叉排序树并在其上查找指定关键字 。四 、 大纲说明本课程 的教学由于 多以 抽象类型及 伪 C 代码进行 算法的 描述 ， 在实验中 ， 一定要以 C或 C+代码的形式 实现各算法 ，并通过实验得以调试 、 运行通过 ， 得到预期的结果 。实验大纲的学时分配 由 必做 实验和 选做 实验两部分组成 ， 有些实验又有更高的要求 ， 包含基 本实验和扩展实验 ，其 基本实验是 要求学生在课程的实验学时内 必须 保证 完成并掌握的 ， 而 扩展实验 内容可以满足部分同学 进行系统化 、综合性学习的 要求 ， 不做强制性的限定 。五 、 考核以学生的实验报告情况和做实验时的表现为考核依据 。六 、 教材及教学参考书1. 严蔚敏 ， 吴伟民著 、 数据结构 、 C语言版 、 清华大学出版社 、 19972. 严蔚敏 ， 吴伟民著 、 数据结构题集 、 C语言版 、 清华大学出版社 、 1997
