《数据结构与算法》-实验指导书-冯广慧

220-目录1.数据结构与算法实验教学大纲2.数据结构与算法实验内容3.数据结构与算法实验报告模板实验指导书20**～20**学年第1学期系（中心）计算机学院教研室课程名称数据结构与算法主讲教师计算机学院制

数据结构与算法实验教学大纲（20**年制订）一、课程编号：二、先修课程：程序设计基础三、学分：3.5学分（理论和实验共计3.5学分）四、学时：16学时五、课程性质与任务1．课程性质《数据结构与算法》是计算机程序设计的重要理论基础，是计算机专业的核心专业基础课程，也是非计算机专业的主要选修课程，同时还是一门考研课程，数据结构前承高级语言程序设计和离散数学，后接操作系统、编译原理、数据库原理等专业课程，为研制开发各种系统和应用软件奠定理论和实践基础，该课程的学习效果不仅关系到后续课程的学习，而且直接关系到软件设计水平的提高和专业素质的培养，在计算机学科教育中有非常重要的作用。《数据结构与算法》实验主要研究分析计算机存储、组织数据的方式，使学生学会数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。2．课程任务选择合适的数据结构更容易设计出更高效运行或存储效率的算法，在进行程序设计时必须将数据结构和与之相关的算法结合起来考虑。数据结构课程的学习离不开实践。针对数据结构的程序设计实践不仅可以加深对课程内容的理解，更重要的是可以通过实践进一步掌握程序设计的技能与方法，初步感受软件开发过程的项目管理方法与规范，为更进一步的学习打下基础。《数据结构与算法》实验不仅仅是以实现相应的程序为目标，更重要的是在完成算法的过程中逐步培养今后从事软件开发所需要的各种能力与素质。其中很重要的一种能力就是软件文档的写作能力。因此，在实验实施中，不仅需要完成程序并进行测试，还需要撰写相应的实验报告。实验报告不仅是对算法与数据结构的总结，也是对软件文档写作能力的初步训练。六、课程教学基本要求实验结束要进行验收，要求学生提交合格的实验报告，确保程序能够运行，能够清楚的介绍自己的工作。老师在检查过程中可针对学生设计的数据结构与算法提出问题，学生回答，若无法编程实现所设计的数据结构与算法，则为不及格，若可以编程实现，但效果一般，则酌情扣分，若程序运行无问题，则提问回答不好的也要相应扣分。每个同学都要提交实验报告，要求在规定时间内提交文档。最后验收时，若文档不全，成绩受到一定影响。

七、学时分配表表1学时分配表教学内容(周)实验学时其它备注第1周实验一顺序表2第3周实验二单链表2第5周实验三栈与队列2第7周实验四二叉树2第9周实验五Huffman树2第11周实验六图的邻接矩阵表示法2第13周实验七图的邻接表表示法2第15周实验八排序2八、考核评分标准实验成绩满分100分，平时成绩占比20％，程序代码、报告文档和答辩情况共计占比80%。九、实验内容

实验内容实验名称实验一顺序表授课时数2实验目的：1.理解线性表的逻辑结构特征，会定义线性表的顺序存储类型；2.熟悉顺序表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）顺序表的类型定义及基本运算（必做，设计性/验证性）初始化顺序表、清空顺序表、求顺序表长度、判断顺序表是否为空、遍历顺序表、查找元素、插入元素、删除元素、逆置顺序表。（2）学生成绩管理系统（选做，设计性）（3）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究，组织讲演答辩活动三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：顺序表的插入和删除运算教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,20232．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[M].机械工业出版社,2020

实验内容实验名称实验二单链表授课时数2实验目的：1.理解线性表的逻辑结构特征，会定义线性表的链式存储类型；2.熟悉单链表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）单链表的类型定义及基本运算（必做，设计性/验证性）初始化单链表、清空单链表、求单链表长度、判断单链表是否为空、遍历单链表、查找元素、插入元素、删除元素、逆置单链表、头插法创建单链表。（2）约瑟夫环（选做，设计性）（3）请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：单链表的插入、删除、逆置教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,20232．陈守孔等.算法与数据结构考研试题精析（第四版）[M].机械工业出版社,2020实验内容实验名称实验三栈与队列授课时数2实验目的：1.理解栈和队列的逻辑特点，能在实际应用中正确选用2.熟练掌握栈和队列的顺序和链式实现方法，以及基本操作的算法实现3.会判断循环队列空和满，会计算循环队列中元素个数教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工二.实验室1.实验内容（1）栈的类型定义及基本运算（必做，设计性/验证性）实现顺序栈和链栈，完成栈的基本操作：初始化栈、检查栈是否为空、清空栈、入栈、退栈、取栈顶元素。（2）队列的类型定义及基本运算（必做，设计性/验证性）实现循环队列和链队列，完成队列的基本操作：初始化队列、检查队列是否为空、清空队列、入队、出队、取队首元素。（3）利用两个栈模拟一个队列（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究，组织讲演答辩活动三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：判断循环队列空和满，带头尾指针的链队列入队和出队时的特殊情况教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,2023实验内容实验名称实验四二叉树授课时数2实验目的：1.熟练掌握二叉树的二叉链表存储结构的实现；2.掌握二叉树的前序、中序、后序以及层次遍历算法；3.灵活运用遍历算法实现二叉树的其它操作。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）二叉树的类型定义、递归遍历及其它基本运算（必做，设计性/验证性）实现二叉链表表示的二叉树，完成二叉树的基本操作：初始化二叉树、按前序次序建立一个二叉树、检查二叉树是否为空、按任一种遍历次序（包括按前序、中序、后序、层次）输出二叉树中的所有结点、求二叉树的深度、求二叉树的高度、求二叉树结点总数、清除二叉树。（2）判断二叉树是否是完全二叉树（选做，设计性）（3）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：二叉树的遍历运算及扩展应用教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,20232．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[M].机械工业出版社,2020实验内容实验名称实验五Huffman树授课时数2实验目的：1.掌握Huffman树的构造方法及Huffman编码的实现2.了解Huffman树在通信、编码领域的应用过程。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）Huffman树和Huffman编码（必做，设计性/验证性）从终端输入若干个字符，统计字符出现的频率，将字符出现的频率作为结点的权值，建立Huffman树，然后对各字符进行Huffman编码，要求打印Huffman树和对应的Huffman编码。（2）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：Huffman树的构造方法及Huffman编码教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：冯广慧,唐懿芳,陈立云.算法与数据结构（第2版）[M].电子工业出版社,20232．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[M].机械工业出版社,2020

实验内容实验名称实验六图的邻接矩阵表示法授课时数2实验目的：1.熟悉图的邻接矩阵表示法的特点和定义方法；2.掌握应用邻接矩阵构造有向图、无向图的算法；3.掌握图的深度优先、广度优先遍历算法并实现。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）图的邻接矩阵表示法义及基本运算（必做，设计性/验证性）实现邻接矩阵表示的图，完成基本操作：查找边、插入边、删除边、深度优先遍历、广度优先遍历、拓扑排序。（2）给你一块n*m的草坪，问如果只点一次火，最多能烧多少块草坪。可以从n*m的草地中任意一个地方开始点火，火只能往上下左右传递，没有草的地方不能燃烧。（选做，设计性）（3）哥尼斯堡七桥问题（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：图的深度优先、广度优先遍历教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,20232．陈守孔等.算法与数据结构考研试题精析（第四版）[M].机械工业出版社,2020实验内容实验名称实验七图的邻接表表示法授课时数2实验目的：1.熟悉图的邻接表表示法的特点和定义方法；2.掌握应用邻接表构造有向图、无向图的算法；3.掌握图的深度优先、广度优先遍历算法并实现。教学内容（讲授提纲）第（2）题图一.课前（线上）第（2）题图1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）图的邻接表表示法义及基本运算（必做，设计性/验证性）实现邻接表表示的图，完成基本操作：查找边、插入边、删除边、深度优先遍历、广度优先遍历、拓扑排序。（2）给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院。（选做，设计性）（3）实现最短路经、最小生成树的求法。（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：图的深度优先、广度优先遍历教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,唐懿芳,陈立云.算法与数据结构（C++语言版）（第2版）[M].电子工业出版社,2023实验内容实验名称实验八排序授课时数2实验目的