1、算法与数据结构实验教学大纲一、课程性质、目的和任务本实验课程与算法与数据结构课堂教学有机结合，相辅相成。在课堂教学中，比较全面概括性地讲述数据结构学科中一些基础性知识重要概念及各种算法，而在本实验课程中，将这些基础性知识重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标：（1） 掌握计算机处理数据的基本方法。（2） 了解算法需用的时间及空间分析方法。（3） 能够为实际应用所涉及的数据选择适当的逻辑结构存储结构及相应的算法。（4） 通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。二、学习本课程学生应掌握的前设课程知识一般在第2学期或第3学期开课。前设课程为
2、：计算机导论C语言程序设计离散数学。三、项目及学时分配序号项目名称时数项目类别项目类型要求每组人数课内课外实验一线性表的基本操作66专业基础验证性选修1实验二线性表的应用66专业基础综合性必修1实验三二叉树及其应用44专业基础验证性必修1实验四图及其应用66专业基础综合性必修1实验五查找44专业基础综合性选修1实验六排序44专业基础综合性选修1四、教学方法在实验教学的初期，引导学生将算法转化为源程序，在计算机上调试、调试和运行。之后，逐渐放手，让学生自己来实现算法的源程序编写、调试和运行。我们设置二个层次的实验内容：验证型和综合型。任课教师在实践环节中亲自指导，通过选择合理的实验题目及实验方案
3、来引导学生积极主动地学习，以锻炼学生的动手能力、创新能力和表达能力。强化学生的个性化指导，使学生在实践中提高软件设计、程序编码和测试能力。五、教学内容及要求实验一 线性表的基本操作教学目的：1熟练掌握顺序表的基本操作。2熟练掌握链表的基本操作。3深入了解栈和队列的特性，巩固这两种数据结构的构造方法。4掌握栈和队列在不同的存储方式下的基本操作。5掌握稀疏矩阵的三元组表示方法，了解它的其他表示方法；掌握稀疏矩阵转置的基本算法。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C+ 6.0工具编辑、编译、执行程序。3程序编写尽量规范化。4对于基本题主要是由学生自己对
4、问题进行分析、设计。5对于提高题，则先是由教师进行引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时数：6学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0软件集成开发环境。实验内容：1编写函数，创建一个顺序表（数据自拟）；2编写函数，在顺序表的指定位置插入一个元素；3编写函数，在顺序表的指定位置删除一个元素；4编写函数，将两个有序顺序表合并成一个新的有序顺序表；5编写函数，创建一个头结点的单链表顺序表（数据自似）；6编写函数，在单链表的指定位置插入一个元素；7编写函数，在单链表的指定位置删除一个元素；8编写函数，
5、实现顺序栈的各种基本操作；9编写函数，实现链式队列的各种基本操作；10编写函数，实现循环队列的各种基本操作。11编写二个函数，分别实现创建用三元组表示的稀疏矩阵、求稀疏矩阵的转置矩阵。实验二 线性表的应用教学目的：1掌握线性表的综合应用。2掌握稀疏的一元多项式的运算处理方法。3掌握迷宫问题的处理方法。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C+ 6.0工具编辑、编译、执行程序。3程序编写尽量规范化。4对于基本题主要是由学生自己对问题进行分析、设计。5对于提高题，则先是由教师进行引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时
6、数：6学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0软件集成开发环境。实验内容：1编写函数，创建一个稀疏的一元多项式（数据自拟）；2编写函数，按类似数学格式输出多项式；3编写函数，求两个多项式的和；4编写函数，求两个多项式的积；5编写函数，对多项式求导。6编写函数，解决迷宫问题。实验三 二叉树及其应用教学目的：1掌握二叉树的存储方法。2掌握二叉树的基本算法。3熟练掌握Huffman树和Huffman编码的构造方法。4了解Huffman编码的具体应用。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C
7、+ 6.0工具编辑、编译、执行程序。3程序编写尽量规范化。4对于基本题主要是由学生自己对问题进行分析、设计。5对于提高题，则先是由教师进行引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时数：4学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0软件集成开发环境。实验内容：1编写函数，创建一棵二叉树；2编写函数，按树状结构输出二叉树；3编写函数，用递归算法分别求二叉树的各种遍历序列；4编写函数，用非递归算法求二叉树的中序遍历序列。5编写函数，构造Huffman树和Huffman编码；6编写函数，输入一串要传输的字符，
8、输出转换后的二进制Huffman编码；7编写函数，接收一串二进制Huffman编码，将它还原成原字符串。实验四 图及其应用教学目的：1熟练掌握图的各种存储结构。2掌握图的基本操作和具体应用。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C+ 6.0工具编辑、编译、执行程序。3程序编写尽量规范化。4对于基本题主要是由学生自己对问题进行分析、设计。5对于提高题，则先是由教师进行引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时数：6学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0
9、软件集成开发环境。实验内容：1编写函数，构造以邻接矩阵表示的图；2编写函数，构造以邻接表表示的图；3编写函数，实现图的深度优先遍历算法（DFS）；4编写函数，实现图的广度优先遍历算法（BFS）；5编写函数，实现求最小生成树的Prim算法。实验五 查找教学目的：1掌握顺序表和有序表的查找方法及其平均查找长度的计算方法。2掌握二叉排序树的构造和查找方法。3掌握哈希表的构造方法。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C+ 6.0工具编辑、编译、执行程序。3程序编写尽量规范化。4对于基本题主要是由学生自己对问题进行分析、设计。5对于提高题，则先是由教师进行
10、引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时数：4学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0软件集成开发环境。实验内容：1编写函数，实现顺序查找算法；2编写函数，实现二分查找算法；3编写函数，实现二叉排序树的构造算法；4编写函数，实现二叉排序树的查找算法；5编写函数，对给定的哈希函数和冲突解决方法，创建哈希表。实验六 排序教学目的：1熟练掌握各种排序算法；2比较各种排序算法的时间性能。教学要求：1学生课前必须预习，教师通过课堂提问等方式检查预习效果。2用Visual C+ 6.0工具编辑、编译、执行程
11、序。3程序编写尽量规范化。4对于基本题主要是由学生自己对问题进行分析、设计。5对于提高题，则先是由教师进行引导性的问题分析及设计分析，然后再由学生自己进行问题分析入设计分析。教学时数：4学时主要设备：1硬件：PC 机；2软件：PC 机操作系统 Windows XP、Visual C+ 6.0软件集成开发环境。实验内容：1编写函数，实现冒泡排序算法；2编写函数，实现简单选择排序算法；3编写函数，实现直接插入排序算法；4编写函数，实现希尔排序算法；5编写函数，实现堆排序算法；6编写函数，实现快速排序算法；7编写函数，实现基数排序算法；8比较各种排序算法的时间复杂度。六、主要教材（指导书）及参考用书
12、1、教材：数据结构实验指导书（自编）2、参考书目：（1）数据结构C语言描述，耿国华主编，高等教育出版社会，2005年7月（2）数据结构实践指导教程（C语言版），阮宏一主编，华中理工大学出版社，2004年9月出版（3）数据结构题集（C语言版），严蔚敏吴伟民米宁编著，清华大学出版社，1999年2月出版3、其他参考资料：（1）（2）http:/www.nist.gov/dads/（3）http:/www.student.seas.gwu.edu/idsv/idsv.html（4）http:/www.datastructures.info/（5）http:/courses.cs.vt.edu/csonline/DataStructures/Lessons/index.html（6）http:/www.cs.sunysb.edu/skiena/214/lectures/（7）http:/www.informatics.susx.ac.uk/courses/dats/dats.html七、考核与成绩评定成绩评定方法：实验预习占10%；实验态度占10%；实验报告占80%。实验成绩最终以20%的比例计入该门课程的总评成绩中。八、其他说明九、编制与审核编制人： 李忠月 审核人： 年 月 日7 / 7
