计算机类大学生小学期实验1

1、算法与数据结构综合训练报 告第一部分：基本算法训练 组号： 02 组长： 温佳美 成员： 安秀芳、施璇、 丁子叶、黄城 2015年 7 月 9 日一、任务说明 1。分工及时间安排。温佳美（组长）：3、Prim算法 11、希尔排序 14、归并排序 15、四则表达式计算组员：安秀芳： 6、Dijkstra算法 9、二叉排序树生成算法（含平衡化） 12、快速排序 PPT主讲人施璇：10、哈希表生成及哈希查找算法 13、堆排序 16、矩阵运算 以及PPT制作丁子叶：1、哈夫曼编码算法 2、由遍历序列恢复二叉树 4、Kruskal算法 8、关键路径算法黄城：5、Floyd 算法 7、拓扑排序 17、有向

2、图的强连通分量求解 2。任务描述2、 设计1。抽象数据类型安秀芳： 6、Dijkstra算法 ：图 9、二叉排序树生成算法（含平衡化） ：树，链表 12、快速排序 ：顺序表施璇：10、哈希表生成及哈希查找算法：哈希表 13、堆排序：顺序表 16、矩阵运算 ：无丁子叶：1.哈夫曼编码：树 2.遍历序列恢复二叉树：二叉树 4.Kruskal算法:图 8.关键路径算法：图，邻接表2。主程序流程及各程序模块的层次关系 本次实验综合为一个main.cpp文件，将所有的程序整合在一个main.cpp文件中。增加菜单函数，显示所有的算法题目及作者名字，选择想要的功能，并用switch()语句选择功能并调用相

3、应的函数实现功能。最后在主函数里调用menu()函数，通过whlie循环选择返回主菜单还是直接退出。小组不同程序之间的相同的数据结构及算法共享。3、 调试分析3、Prim算法： a.构造数据结构-图。 b.采用邻接矩阵法创建无向图。 c.Prim算法“加点法”，求最小生成树。算法实现需要一个辅助数组closedge，以记录最小边在U中的那个顶点，以及最小边上的权值。在连通图中，选取一个节点为顶点，加入U中，对其余的每个顶点，将closedgei初始化为到U的边的信息。选出closedge中最小边closedgek，将k加入U中，更新剩余每组最小边的信息。循环直到所有节点加入。11、希尔排序：a

4、.构造数据结构-顺序表。b.初始化顺序表，输入排序个数与排序序列。c.希尔排序采用分组插入，第一个去增量d1，所有间隔为d1的记录分在同一趟，每组中进行直接插入。第二趟取增量d2，重复，直到取到增量1，每组直接插入排序为止。 14、归并排序：顺序表 a.构造数据结构-顺序表。b.初始化顺序表，输入排序个数与排序序列。c.归并排序，将顺序表n个记录递归一分为二，直到每个子序列的长度为1。然后进行2-路归并排序，得到n/2个长度为2或1的有序子序列；再两两归并。重复。 15、四则表达式计算：栈 a. 构造数据类型栈，数栈和字符栈。 b. 定义数栈和字符栈的初始化、压栈、弹栈、取栈顶元素的函数。 c

5、. 先在字符栈中压入#。输入字符串，当输入字符不是#，或字符栈顶元素不是#，循环操作，从第一个字符串开始判断，若是数字字符，输出（后序表达式），再向后判断，直到遇到符号字符，将之前的字符串转化为大整数，p=0;p=s*10+si,将其 -0变为整形，压入数栈；若为符号字符，比较字符栈栈顶元素与所输入的字符运算符高低，：将输入字符压入字符栈； :弹字符栈，输出（后序表达式），两次弹数栈，进行相应操作，将结果压入数栈；=：字符栈弹栈。1.哈夫曼编码 首先建立赫夫曼树，由于每个赫夫曼编码是变长编码，因此使用一个指针数组来存放每个字符编码串的首地址。个字符的赫夫曼编码存储在由HuffmanCode定义

6、的动态分配的数组HC中，构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到跟的路径，这样生成的编码与要求的编码反序，出将生成的的代码先从后往前一次存放在一个临时的一维数组cd中，并设一个变量start记录编码在cd中起始位置，当某字符编码完成时，从cd的start处将编码到该字符相应的编码串中。此程序较简单，没什么问题。 2. 遍历恢复二叉树由先序和中序或后序和中序可唯一确定一棵二叉树，主要问题是恢复二叉树出现问题，后经反复调试发现只要不输入相同的结点就可以。4. Kruskal算法对于教材中的Locate()函数来获取结点下标没有思路，但我觉得直接使用序号作为结点更简单，所以采用了后者

7、。8. 关键路径算法代码课本上基本都有，没什么大问题，但从中也了解到知识学过了也得多回头温习，温故而知新。6、Dijkstra算法 采用邻接矩阵创建有向网，每次求得v0到某个顶点v的最短路径，将v加到s集，更新最短路径的长度同时更改Vi的前驱。通过终点依次找到其前驱，利用for语句倒序输出即为最短路径。在找前驱时数组起始位置没有写对，经过反复查看得出正确答案。 9、二叉排序树生成算法（含平衡化） 使用二叉排序树的二叉链表作为存储结构，创建二叉树，插入一个结点，若树中已存在相同关键字结点，不再插入，调试过程中平衡二叉树的输出形态位置不对，通过比对结果，反复修改结点的位置，最终得出正确的平衡二叉树

8、形态。10、 哈希表生成及哈希查找算法：利用除留余数法构造散列函数。解决冲突的方法为：利用开放地址法中的线性探测法。当发生冲突时，从冲突地址的下一个单元顺序寻找空单元，如果到最后一个位置也没找到空单元，则回到表头开始继续查找，直到找到一个空位，就把此元素放到此空位中。如果找不到空位，则说明散列表已满，需要进行溢出处理。12、快速排序 在从大到小排序的过程中出现错误，枢轴的选择出现错误，通过参考从小到大排序的过程，修改数据交换的条件，从而得出正确结果。13、 堆排序：首先用筛选法调整堆，然后反复调用调整堆的函数建初堆，把无序序列建成大根堆或者小根堆，最后对顺序表进行堆排序并输出每一次排序之后的序

9、列。16、矩阵运算 ：首先用一个输入函数，进行矩阵的输入，然后建立加减法和乘法的函数。在做加减法的时候要注意两个矩阵的行数和列数相同，在进行矩阵乘法时两个矩阵只要保证一个矩阵的列数和另一个矩阵的行数相等即可。4、 系统测试及结果 （结果附截图）3、Prim算法： 测试：课本图P140页11、希尔排序： 测试:课本例题P21349 38 65 97 76 13 27 49 55 04步长：5 13 27 49 55 4 49 38 65 97 76步长：3 13 4 49 38 27 49 55 65 97 76步长：1 4 13 27 38 49 49 55 65 76 97 14、归并排序：

10、 测试：数据课本P22615、四则表达式计算： 测试：数据12*(10-5)/(20-12)=7.5后序表达式为：12 10 5 - * 20 12 （去括号）1.赫夫曼编码.2. 遍历恢复二叉树4. Kruskal6、Dijkstra算法8. 关键路径算法9、二叉排序树生成算法（含平衡化） 10、哈希表生成及哈希查找算法 12、 快速排序 13、 堆排序 16、矩阵运算5、 总结与体会 通过几天的小学期训练，让我们重新回顾并巩固了数据结构与算法的相关知识。在编程的时候，我们都能很明显地感觉到以前学过的知识有很多都已经遗忘，所以编程的时候不免有些吃力。一开始，老师就说过数据结构是基础，基础不牢固，越往后越难走。因此，我们应该在不断学习的过程