数据结构与算法_2005《数据结构》实验课程教学大纲王阿川

数据结构数据结构 实验课程教学大纲实验课程教学大纲 1 1 实验课程名称 实验课程名称 数据结构实验 2 2 实验课程名称 英文 实验课程名称 英文 Data Structure 3 3 课程代码 课程代码 130038 4 4 实验课程性质 实验课程性质 非独立设课 5 5 学 学 时 时 16 6 6 学 学 分 分 7 7 适用专业 适用专业 计算机科学与技术 8 8 先修或同修课程 先修或同修课程 高级语言程序设计 面向对象概念和技术 离散数学等 9 9 开课单位 开课单位 信息与计算机工程学院 1010 制定实验教学大纲的依据 制定实验教学大纲的依据 教育部数据结构课程教学指导性大纲 东北林业大学数据 结构教学大纲 1111 本实验课在培养实验能力中的地位及作用 本实验课在培养实验能力中的地位及作用 数据结构是信息与计算科学专业中一门重要的专业基础课程 用数字计算机解决任何 实际问题都离不开数据表示和数据处理 而数据表示和处理的核心问题之一是数据结构及 其算法实现 他为计算机专业人员提供了必要的技能训练 按照 素质教育 要求 培养 具有一定创新能力和创造能力的人才为目标 本课程实验将数据结构和高级语言程序设计 两部分相结合 着重培养学生进行复杂 综合性程序设计的训练过程为主要目的 以实验 设计方法 设计思路 实验手段的合理运用等内容为主 充分发挥学生的主观能动性 因 材施教 通过实践 学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一 步的掌握 并对在不同存储结构上实现不同的运算方式和技巧有所体会 通过数据结构的 实验课程的学习 为后续课程 特别是软件方面的课程打下了厚实的知识基础 同时也提 供了必要的技能训练 1212 应达到的实验能力标准 应达到的实验能力标准 上机实习是对学生的一种全面综合训练 是与课堂听讲 自学和练习相辅相成的必不 可少的一个教学环节 通常 实习题中的问题比平时的练习题要复杂 也更接近实际 数 据结构这门课程安排的 4 次上机实验都属于一种设计类型的实验 每个实验的训练重点在 于基本的数据结构 而不强调面面俱到 实验的目的是旨在使学生进一步巩固课堂上所学 的理论知识 深化理解和灵活掌握教学内容 在实验教学过程中培养学生的实验技能和科学研究能力 引导学生学会分析 研究计 算机所要加工的数据的结构特性 以便为应用涉及的数据选择适当的逻辑结构 存储结构 及相应的实现算法 并初步了解对算法的时间分析和空间分析技术 另一方面 通过对本 课程算法设计和上机实践的训练 还应培养学生的数据抽象能力和程序设计的能力 培养 学生编制算法的能力和编程解决实际问题的动手能力 进而全面提高学生对复杂问题的程 序设计能力 创新能力和综合素质 要求学生在上机前应认真做好各种准备工作 熟悉机器的操作系统和语言的集成环境 独立完成算法编制和程序代码的编写 上机时应随带有关的高级语言教材或参考书 要学 会程序调试与纠错 1313 实验内容 实验内容 在实验前 进行问题分析和任务的定义 数据类型和系统设计 编码实现和静态检查 上机准备和上机调试 总结和整理实习报告 设计好 C 语言或 C 程序 然后在系统平台 上进行编辑 编译 执行和验证结果 得到完整 正确的 C 语言或 C 程序 每次实验后要交实验报告 实验报告的内容应包括 1 实验题目 班级 学号 姓 名 完成日期 2 简要的需求分析与概要设计 3 详细的算法描述 4 程序清单 与运行结果 5 收获与体会 1 实验一 线性表的顺序存储结构 输入一组整型元素序列 建立顺序表 实现该顺序表的遍历 在该顺序表中进行顺序查找某一元素 查找成功返回 1 否则返回 0 判断该顺序表中元素是否对称 对称返回 1 否则返回 0 实现把该表中所有奇数排在偶数之前 即表的前面为奇数 后面为偶数 输入整型元素序列利用有序表插入算法建立一个有序表 利用算法 6 建立两个非递减有序表并把它们合并成一个非递减有序表 编写一个主函数 调试上述算法 综合训练 利用顺序表实现一个班级学生信息管理 数据录入 插入 删除 排序 查找等 2 实验二 链式存储结构 一 单向链表的有关操作 随机产生或键盘输入一组元素 建立一个带头结点的单向链表 无序 遍历单向链表 把单向链表中元素逆置 不允许申请新的结点空间 在单向链表中删除所有的偶数元素结点 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数 并利用该函数 建立一个非递减有序单向链表 利用算法 5 建立两个非递减有序单向链表 然后合并成一个非递增链表 利用算法 5 建立两个非递减有序单向链表 然后合并成一个非递减链表 利用算法 1 建立的链表 实现将其分解成两个链表 其中一个全部为奇数 另一 个全部为偶数 尽量利用已知的存储空间 采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果 在主函数中设计一个简单的菜单 分别调试上述算法 综合训练 利用链表实现一个班级学生信息管理 数据录入 插入 删除 排序 查找等 并能够实现将数据存储到文件中 3 实验三 链式存储结构 二 双向链表的有关操作 利用尾插法建立一个双向链表 遍历双向链表 实现双向链表中删除一个指定元素 在非递减有序双向链表中实现插入元素 e 仍有序算法 判断双向链表中元素是否对称若对称返回 1 否则返回 0 设元素为正整型 实现算法把所有奇数排列在偶数之前 在主函数中设计一个简单的菜单调试上述算法 4 实验四 栈和队列的有关操作 采用链式存储实现栈的初始化 入栈 出栈操作 采用顺序存储实现栈的初始化 入栈 出栈操作 采用链式存储实现队列的初始化 入队 出队操作 采用顺序存储实现循环队列的初始化 入队 出队操作 在主函数中设计一个简单的菜单 分别测试上述算法 综合训练 利用栈实现表达式求值算法 利用栈实现迷宫求解 5 实验五 二叉树的常见操作 输入字符序列 建立二叉链表 中序遍历二叉树 递归算法 中序遍历二叉树 非递归算法 最好也能实现先序 后序非递归算法 求二叉树的高度 求二叉树的叶子个数 将二叉链表视为森林的孩子兄弟链表 计算森林中叶子个数 建立中序线索二叉树 并实现中序遍历 借助队列实现二叉树的层次遍历 在主函数中设计一个简单的菜单 分别调试上述算法 综合训练 为 N 个权值设计哈夫曼编码 6 实验六 图的有关操作 键盘输入数据 建立一个有向图的邻接表 输出该邻接表 建立一个无向图的十字链表 在有向图的邻接表的基础上计算各顶点的度 并输出 以有向图的邻接表为基础实现输出它的拓扑排序序列 采用邻接矩阵存储一个有向图 输出单源点到其它顶点的最短路径 采用邻接表存储实现无向图的深度优先非递归遍历 采用邻接表存储实现无向图的广度优先遍历 采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 判断无向图任意两个顶点间是否有路径 若有输出路径上的顶点序列 在主函数中设计一个简单的菜单 分别调试上述算法 综合训练 为计算机专业设计教学计划 4 个学年 每学年 2 个学期 开设 50 门 课程 每学期所开课程门数尽量均衡 课程的安排必须满足先修关系 7 实验七 查找的有关操作 利用实验一建立有序表 采用折半查找实现某一已知的关键字的查找 随机产生一组关键字 利用二叉排序树的插入算法建立二叉排序树 然后删除某一 指定关键字元素 建立 树并实现删除某一指定关键字元素 已知散列函数为 H key key p p 为自定的常数 冲突处理方法分别为线性探测 法 外拉链法实现散列表的建立 利用插入算法实现 8 实验八 排序的有关操作 输入一组关键字序列分别实现下列排序 实现简单选择排序 直接插入排序和冒泡排序 实现希尔排序算法 实现快速排序算法 实现堆排序算法 快速排序的非递归算法 实现折半插入排序 采用链式存储实现简单选择排序 直接插入排序和冒泡排序 在主函数中设计一个简单的菜单 分别测试上述算法 综合训练 采用几组不同数据测试各个排序算法的性能 比较次数和移动次数 1414 实验成绩考核办法 实验成绩考核办法 每学期实验课结束后按考试管理制度考试 实验成绩根据学生预习情况 实验操作情 况 实验报告的质量综合评定 实验成绩占总成绩的 10 1515 实验教材 参考资料 实验教材 参考资料 数据结构 C 语言版 严蔚敏 吴伟民 清华大学出版社 2003 数据结构 C 语言描述 耿国华 西安电子科技大学出版社 2002 数据结构算法设计指导 胡学钢 清华大学出版社 1999 Data Structures Algorithms and Applications in C Sarta Sahni 著 McGraw Hill 出 版 Data Structure with C William Ford William Topp 清华大学影印版 1616 实验项目汇总表 实验项目汇总表 序号实验项目名称学时实验类型实验类别每组学生数 1线性表的顺序存储结构2设计性实验必修1 2 链式存储结构 一 单向链表的有关操作 2设计性实验必修1 3 链式存储结构 二 双 向链表的有关操作 2设计性实验必修1 4栈和队列的有关操作2验证性实验必修1 5二叉树的常见操作2设计性实验必修1 6图的有关操作2验证性实验必修1 7查找的有关操作2验证性实验必修1 8排序的有关操作2验证性实验必修1 合计16 实验分组 实验分组