一、实验目的：1．掌握线性表的链式存储结构。

2．熟练地利用链式存储结构实现线性表的基本操作。

3．能熟练地掌握链式存储结构中算法的实现。

二、实验内容：1．用头插法或尾插法建立带头结点的单链表。

2．实现单链表上的插入、删除、查找、修改、计数、输出等基本操作。

三、实验要求：1. 根据实验内容编写程序，上机调试、得出正确的运行程序。

2. 写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时五、实验步骤：1．进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。

①定义单链表的数据类型，然后将头插法和尾插法、插入、删除、查找、修改、计数、输出等基本操作都定义成子函数的形式，最后在主函数中调用它，并将每一种操作前后的结果输出，以查看每一种操作的效果。

②部分参考程序（略）六、实践部分选作实验可以从以下两个实验中任选一个：1 试设计一元多项式相加（链式存储）的加法运算。

A（X）=7+3X+9X8+5X9B（X）=8X+22X7-9X81．建立一元多项式；2．输出相应的一元多项式；3．相加操作的实现。

2 约瑟夫生死环利用单循环链表存储结构，解决约瑟夫（Josephus）环问题。

即：将编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一个正整数密码。

开始时任选一个正整数作为报数上限值m,从某个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有的人全部出列为止。

令n最大值取30。

设计一个程序，求出出列顺序，并输出结果。

一、实验目的：1．掌握二叉树的数据类型描述及二叉树的特性。

2．掌握二叉树的链式存储结构(二叉链表)的建立算法。

3．掌握二叉链表上二叉树的基本运算的实现。

二、实验内容：从1、2中选择一项内容，再从3、4中选择一项内容1．用递归实现二叉树的先序、中序、后序3种遍历。

2．用非递归实现二叉树的先序、中序、后序3种遍历。

3．计算二叉树的总结点数、叶子结点个数，以及二叉树的深度。

4．实现二叉树的层次遍历。

三、实验要求：1．根据实验内容编程，上机调试、得出正确的运行程序。

2．写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时五、实验步骤：1．进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。

①将建立二叉树及先序、中序、后序3种遍历算法都写成子函数，然后分别在主函数中调用它，但在建立二又树中，必须把二叉树看成完全二叉树的形式。

若不是完全二叉树，则在输入数据时，用虚结点(不存在)表示(本算法中，用“*”号代替)。

②用非递归法实现二叉树的遍历非递归算法中，必须设置堆栈，可以直接用一维数组来代替栈，但必须另外设置栈顶指针。

③在二叉树遍历的基础上计算总结点数、叶子结点个数，以及二叉树的深度。

④实现二叉树的层次遍历用一个一维数组代替队列，实现二叉树的层次遍历。

六、实践部分选作实验可以从以下两个实验中任选一个：1．给定权值5,29,7,8,14,23,3,11，建立哈夫曼树，输出哈夫曼编码。

2．对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。

算法提示：将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数调用它们。

实验三图形结构一、实验目的1．掌握图的数据类型描述及定义；2．掌握用邻接矩阵和邻接表的方法描述图的存储结构；3．理解并掌握深度优先遍历和广度优先遍历的存储结构。

二、实验内容：从1、2中选择一项内容，再从3、4中选择一项内容1．建立无向图的邻接矩阵，并实现插入、删除边的功能。

2．建立有向图的邻接表，并实现插入、删除边的功能。

3．建立一个包含6个结点的图，并实现该图的深度优先搜索遍历。

4．建立一个包含6个结点的图，并实现该图的广度优先搜索遍历。

三、实验要求：1．根据实验内容编程，上机调试、得出正确的运行程序。

2．写出实验报告（包括源程序和运行结果）。

四、实验学时：4学时五、实验步骤：1.进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。

①内容1的知识要点：//邻接矩阵的存储结构图由一个非空的顶点的集合和一个描述顶点之间关系(边)的集合组成。

它可以定义为G=(V，E)。

其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图是一种复杂的数据结构。

对于实际问题，需要根据具体图的结构特点以及所要实施的操作，选择建立合适的存储结构。

图的存储结构包括邻接矩阵和邻接表。

邻接矩阵：用一维数据组存储图中顶点的信息，用矩阵表示图中各顶点之间的相邻关系。

它属于静态存储方法。

邻接表：邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。

顺序存储部分用来保存图中顶点的信息，链式存储部分用来保存图中边的信息。

②内容2的知识要点：//邻接表的存储结构构造有向图链接表与无向图链接表的算法区别是：无向图两结点无向对偶，因而邻接表有一定的对偶性；有向图两结点间有向无对偶关系，因而建立邻接表时应根据输入的顶点及边的有向关系建立(当箭头方向离开结点为有关，当箭头方向指向结点为无关)。

③内容3的知识要点：//图的深度优先搜索遍历深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从vo出发，访问vo的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问的顶点w2，然后从w2出发，访问w2的一个未被访问的邻接顶点w3，依此类推，直到一个所有邻接点都被访问过为止。

图采用邻接表作存储结构，图的深度优先遍历次序为①→②→④→⑤→⑥→③参考程序运行过程中，深度优先遍历时指针p的移动方向示意如图下所示，图中p1、p2、p3、p4、p5和p6为深度优先遍历图的各结点时，指针p的移动次序。

//图的广度优先搜索遍历④内容4的知识要点：广度优先遍历图的算法：首先访问指定的起始顶点v0,从v0出发，访问v0的所有未被访问的邻接顶点w1，w2，…，w k，然后再依次从w1，w2，…，w k出发，访问所有未被访问过的邻接顶点，依此类推，直到图中所有未被访问过的邻接顶点都被访问过为止。

根据广度优点遍历的规则，在其算法实现中，借助一个队列g－queue来存放已被访问过的顶点。

从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依此类推，直至队列为空且图中结点均被访问过为止。

图的广度优先遍历次序为：①→②→③→④→⑤→⑥参考程序运行过程中，广度优先搜索时指针p的移动示意如下图所示，图中片p1、p2、p3、p4、p5和p6为广度优先遍历图的各结点指针p的移动次序。

六、实践部分选作实验可以从以下两个实验中任选一个：1、设计一个交通导航咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径问题。

设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。

2、假设一个城市有n个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。

请设计一个能满足要求的造价方案。

可以用带权的无向图（即无向网）表示这n个小区之间的电网连接，其中顶点表示小区，权值表示城市之间电网建设的造价，构造一个无向网的最小生成树即是满足要求的最低电网连接造价方案。

实验四查找和排序一、实验目的1.掌握各种查找算法的基本思想、适用条件及算法实现；2.熟练掌握二叉排序树的构造和查找方法；3.掌握各种排序算法的基本思想、适用条件及算法实现；4.掌握各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂性和稳定性的分析方法。

二、实验内容从1、2中选择一项内容，再从3、4中选择一项内容1. 建立一个线性表，对表中数据元素存放的先后次序没有任何要求。

输入待查数据元素的关键字进行查找。

（为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据部分忽略不考虑。

）2. 查找表的存储结构为有序表，即表中记录按关键字大小排序存放。

输入待查数据元素的关键字进行查找。

3. 随机函数产生10000个随机数，用直接插入、二分插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间。

4. 随机函数产生30000个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。

三、实验要求1. 根据实验内容编程，上机调试、得出正确的运行程序。

2. 写出实验报告（包括源程序和运行结果）。

四、实验学时2学时。

五、实验步骤：1．进入编程环境，建立一新文件；2. 参考以下相关内容，编写程序，观察并分析输出结果。

①顺序查找的基本思想及程序实现对于给定的关键字k，从表的一端开始，逐个进行数据元素的关键字和给定值的比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于k的节点，则查找失败。

建立一个顺序表，数据元素从下标为1的单元开始放入，下标为0的单元起监视哨作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，若直到下标为0时才找到关键字则说明查找失败；若不到下标为0时就找到关键字，则查找成功。

②折半查找的基本思想及程序实现：设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high]，要查找的关键字值为key，中间元素的下标为mid=(low+high)／2 (向下取整)，令key与r[mid]的关键字比较：●若key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。

●若key<r[mid].key，所要找的记录只能在左半部分记录中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小了一半。

●若key>r[mid].key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小了一半。

重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key说明查找成功；或者出现low的值大于high的情况，说明查找不成功。

建立一个有序表，数据元素从下标为1的单元开始放入。

实现查找算法时，首先将low 赋值为l，high等于最后一个数据元素的下标，然后将给定的关键字的值与查找区间[low，high]中间的数据元素的关键字比较，实现查找过程。

③排序算法提示为了产生随机数，必须用到头文件stdlib．h中的两个函数srand()和rand()来设置随机种子以及产生随机数。

为了能够计时，必须用到头文件time．h中的time()和difftime()两个函数，time()用于截取计算机内的时钟，difftime()用于得到两次时钟间隔的时间(秒)。