《数据结构与算法》实验教案

1-实验教案实验名称实验一顺序表授课时数2实验目的：1.理解线性表的逻辑结构特征，会定义线性表的顺序存储类型；2.熟悉顺序表的基本操作和具体的函数实现；3.熟悉多文件程序的输入、编辑、调试和运行的全过程。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）顺序表的类型定义及基本运算（必做，设计性/验证性）初始化顺序表、清空顺序表、求顺序表长度、判断顺序表是否为空、遍历顺序表、查找元素、插入元素、删除元素、逆置顺序表。（2）学生成绩管理系统（选做，设计性）（3）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究，组织讲演答辩活动三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：顺序表的插入和删除运算教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,吴昊,文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,20192．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[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++语言版）[M].电子工业出版社,2019实验教案实验名称实验三栈与队列授课时数2实验目的：1.理解栈和队列的逻辑特点，能在实际应用中正确选用2.熟练掌握栈和队列的顺序和链式实现方法，以及基本操作的算法实现3.会判断循环队列空和满，会计算循环队列中元素个数教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工二.实验室1.实验内容（1）栈的类型定义及基本运算（必做，设计性/验证性）实现顺序栈和链栈，完成栈的基本操作：初始化栈、检查栈是否为空、清空栈、入栈、退栈、取栈顶元素。（2）队列的类型定义及基本运算（必做，设计性/验证性）实现循环队列和链队列，完成队列的基本操作：初始化队列、检查队列是否为空、清空队列、入队、出队、取队首元素。（3）利用两个栈模拟一个队列（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”（2）编程环境不限，VS、DEVCPP等均可（3）小组讨论合作探究，组织讲演答辩活动三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：判断循环队列空和满，带头尾指针的链队列入队和出队时的特殊情况教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,吴昊,文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,2019实验教案实验名称实验四二叉树授课时数2实验目的：1.熟练掌握二叉树的二叉链表存储结构的实现；2.掌握二叉树的前序、中序、后序以及层次遍历算法；3.灵活运用遍历算法实现二叉树的其它操作。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）二叉树的类型定义、递归遍历及其它基本运算（必做，设计性/验证性）实现二叉链表表示的二叉树，完成二叉树的基本操作：初始化二叉树、按前序次序建立一个二叉树、检查二叉树是否为空、按任一种遍历次序（包括按前序、中序、后序、层次）输出二叉树中的所有结点、求二叉树的深度、求二叉树的高度、求二叉树结点总数、清除二叉树。（2）判断二叉树是否是完全二叉树（选做，设计性）（3）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1）编码应遵循“数据结构与算法编程规范”，建议在程序中添加“诚信代码保证”；（2）编程环境不限，VS、DEVCPP等均可；（3）小组讨论合作探究，组织讲演答辩活动。三.课后（线上）完成代码的整合与调试，在校内SPOC平台提交报告和作品视频，开展自评互评本章节的教学重点、难点：二叉树的遍历运算及扩展应用教学方法、教学手段：1．使用教具：计算机和投影仪2．辅助教学：校内SPOC、百科园、算法演示动画参考资料：1．冯广慧,吴昊,文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,20192．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[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、百科园、算法演示动画参考资料：1．冯广慧,吴昊,文全刚.算法与数据结构（C++语言版）[M].电子工业出版社,20192．陈守孔,胡潇琨,李玲,冯广慧.算法与数据结构考研试题精析（第四版）[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++语言版）[M].电子工业出版社,2019实验教案实验名称实验七图的邻接表表示法授课时数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++语言版）[M].电子工业出版社,2019实验教案实验名称实验八排序授课时数2实验目的：1.熟悉常用排序的方法、过程及原则；2.掌握常用算法的思想及实现方法；3.会计算排序算法的时间和空间复杂度。教学内容（讲授提纲）一.课前（线上）1.观看算法模拟动画，理解算法思想；2.课前查阅资料，储备背景知识，构思解决方案，确定小组分工。二.实验室1.实验内容（1）实现常用排序算法（必做，验证性）插入类排序：直接插入排序、希尔排序；交换类排序：冒泡排序、快速排序；选择类排序：简单选择排序、堆排序；归并类排序：2路归并排序。随机生成100000个数，测试上述排序算法性能。（2）在直接插入排序算法基础上实现，1）二分法插入排序，2）交换式插入排序（3）奇偶交换排序（选做，设计性）（4）鼓励自主拟定实践训练项目（选做，设计性）2.实验要求（1