数据结构课程设计实验指导书2011

1、数据结构课程设计实验指导书东华大学计算机科学与技术学院2011年12月目 录1.前言12 顺序表与链表52.1 实验内容52.2 实现提示63 树和二叉树83.1 实验内容83.2 实现提示84 图104.1 实验内容104.2 实现提示115 查找和排序125.1 问题描述125.2 问题分析125.3 实现提示131. 前言数据结构是计算机科学与技术专业的一门核心专业基础课程，它主要介绍线性结构、树型结构和图型结构的存储实现与基本操作，尤其是查找与排序算法的实现，并分析相应算法的时间、空间效率。其主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生掌握典型算法的设计思想

2、及程序实现，能够根据实际问题选取合适的存储方案、设计出简洁、高效、实用的算法，并为后续课程的学习及软件开发打下良好的基础。为了更好地配合数据结构课程的实践，特编写此课程设计指导书。1.1 指导思想本次课程设计的指导思想是：1、 学习获取知识的方法；2、 提高发现问题、分析问题和解决实际问题的能力；3、 加强创新意识和创新精神；4、 加强团队的分工与合作；5、 掌握面向实际背景思考问题的方法。1.2 设计任务本次课程设计任务主要分为个人任务和小组任务两种。个人基本任务：完成第2章以及第3章中的设计任务，其中选做题不是必须完成的任务。小组任务：完成第4章和第5章的设计任务，其中选做题不是必须完成的

3、任务。1.3 要求1、 每项目小组人员为35名。2、 每项目小组提交一份课程设计报告，内容包括：课题名称，课题参加人员名单和分工，课题的目的，课题内容，需求分析、概要设计、主要代码分析、测试结果、课题特色和创新之处、收获与体会、使用说明。3、 每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。1.4 参考进度第1天，布置任务。第1、2、3天，完成第2章任务第4、5、6天，开始第3章任务。第7到10天，完成小组任务。1.5

4、 成绩评定采用小组考核和个人考核两级考核方法。1、 小组考核（1）圆满完成第4章和第5章的全部内容的小组成绩为优。（2）第4章选做题任务未完成的小组成绩为良。（3）未通过验收的项目为不及格。2、 个人考核：全部完成并经过良好测试才能评优。个人未完成选做题任务的为良；个人只完成所有个人任务的一半以上的为及格；个人成绩的评定还受项目组成绩影响。3、 小组成绩折算成个人成绩方法：小组交实验报告时同时交一份成员贡献表，表格式如下：学号姓名贡献度101张三120102李四90103王五90104钱六100（总计）400上表中，如果成员数为4，则贡献度总和为400。如果小组成绩为80分，则折算到个人的成绩

5、如下：张三：80*120/100=96分李四：80*90/100=72分王五：80*90/100=72分钱六：80*100/100=80分如果某小组无此表格，则每个成员的贡献度按100计算。如果某小组的贡献度平均值大于100，则降低组长的贡献度，使得平均值为100。1.6 注意事项：1、 迟到3次或缺席一次，成绩下降一个档次，迟到6次或缺席2次，成绩再下降一个档次，依次类推。2、 上机时发现玩游戏一次，成绩下降一个档次，玩游戏二次，成绩再下降一个档次，依次类推。3、 课程设计开始前，各班的同学在班内自由组合，形成小组，每小组自行推荐小组长一人，在课程设计开始的第一天上交组长名单、小组组员名单，

6、名单上注明班级、学号、姓名。1.7 参考书目1 严蔚敏等著， 数据结构（C语言版）， 清华大学出版社 2 顺序表与链表2.1 实验内容1、顺序表的应用(1)对于顺序存储的线性表，请实现以下功能：1）实现二路归并排序算法。2）实现希尔排序算法。3）实现快速排序算法。4）实现堆排序算法。(2)已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。(3)编写一个主函数,调试上述算法。

7、2、链表的应用(1)假设有两个按元素值递增次序排列的线性表A和B，均以单链表形式存储，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等。比如，A中元素为（1,3,5,8,10,13,18），B中元素为（1,3,6,8,9,10,13,15），则删除元素后A、B里的元素为（1,3,8,10,13）。(2)猴子选大王。n只猴子围成一圈，从1到m报数，报m的猴子出局。余下的猴子从第m+1只开始继续从1到m报数，报m的猴子出局。第n只猴子报数后，第1只猴子接着报数（因为围成了圈）。待整个圈只剩下一只猴子时，该猴子即为大王。n和m由

8、用户输入，请输出当选大王的猴子的编号。(3)设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prev（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。(4)对于稀疏矩阵的存储，可不使用二

9、维数组来存储，而使用链表，只存储其中的非0元素。链表中的每个结点包含的域为（行，列，值, next），如以下稀疏矩阵： 02000300060000000700则链表为：012103146327请实现两个稀疏矩阵的相加，并输出结果。要求：相加后原来的两个矩阵仍然存在。(5)在主函数中设计一个简单的菜单，分别调试上述算法。3、选做题(1)对顺序表的快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排序的效率，而且界值也并不一定是被顺序表中的一个元素。例如，我们可以用被划分序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。(2)设有n个待排序元素存放在一个不带表头

10、结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。2.2 实现提示（1）顺序表的第2题：顺序表中删除值为item的元素：并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。（2）选做题的快速排序：保存划分的第一个元素。以平均值作为枢轴，进行普通的快速排序，最后枢轴的位置存入已保存的第一个元素，若此关键字小于平均值，则它属于左半部，否则属于右

11、半部。（3）选做题的二路归并排序：先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。当队列不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。3 树和二叉树3.1 实验内容1.基本题（1）输入字符序列，建立二叉链表。 （2）遍历二叉树输出。（3）请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。请遍历该链

12、表输出所有叶子结点，然后再先序遍历二叉树输出所有叶子结点，并对比两个输出结果，看是否相同。（4）试写一算法判断某二叉树是否是完全二叉树。（5）试写一算法判断某二叉树是否是二叉排序树。（6）在主函数中设计一个简单的菜单，分别调试上述算法。2.选做题（1）在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。3.2 实现提示（1）基本题第3题：叶子结点只有在遍历过程中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。注

13、意：由于此时叶子结点的右指针另有用途，为了区分右指针的两种用途，需要改变结点的结构，在结点中增加一个标志，表示右指针究竟是指向右孩子，还是链表中叶子结点的后继。（2）基本题第4题：判定是否是完全二叉树，可以使用队列进行层次遍历，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女，其后面的结点也不应该有子女”的原则进行判断。（3）基本题第5题：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。（4）选做题第1题：非递归后序

14、遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。4 图4.1 实验内容1.有向图（1）键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。（2）采用邻接表存储实现有向图的深度优先遍历。（3）试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（ij）。（4）已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。（5）在主函数中设计一个简单的菜单，分别调试上述算法。2.无向图 （1）建立一个无向图的邻接表，并输出该邻接表。 （2）采用邻接表存储实现无向图的深度优先遍历。 （3）无向图采用邻接表存储方式，

15、试写出删除边（i，j）的算法，并输出深度优先遍历的结果。（4）在主函数中设计一个简单的菜单，分别调试上述算法。3.选做题：（1）最小生成树问题：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。设无向图的顶点数不超过30个，并为简单起见，图中边的权值设成小于100的整数。步骤： 1)利用PRIM算法求网的最小生成树。 2)以文本形式输出生成树中各条边以及他们的权值.例.测试运行实例：对下图求最小生成树。（2）关键路径问题步骤：1） 建立AOE网的存储结构2） 对AOE网进行拓扑排序，同时按拓扑序列的次序求出各顶点事件的最早

16、发生时间ve。3） 按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。4） 根据各顶点事件的ve值和v1值，求出各活动ai的最早开始时间e(i)和最迟开始时间l(i)。若e(i)=1(i)，则ai为关键活动。5） 求关健路径例.测试运行实例：对下图求出关键路径。4.2 实现提示（1）有向图第4题：以顶点u为起点，非递归深度优先遍历图，当访问到顶点v时，栈中所有元素均为路径上的顶点。5 查找和排序5.1 问题描述对附件中的”RFCdoc.txt”统计单词出现的频率。注意：单词”The”和”the”算同一个单词（也就是不区分大小写）。统计好后，输出出现频率最高的5个单词和它对应的频率。单词的定义为

17、：只包含英文字母的连续字符串。如：“This is RFC document.”，则共包含四个单词，注意，最后一个单词“document”不要把点号包含在内。5.2 问题分析为了做统计操作，每个单词必须保存一个和它相关的频率。算法可以为：扫描一遍文件，对每个单词逐一处理。当扫描到某个单词时，则查看已经统计的该单词出现的频率，将频率加一，再赋给该单词。如果该单词还未出现过，则频率为1。为了保存出现的单词和它的频率，可以采用两种方式保存：线性表和Hash表。如果采用顺序存储的线性表，则线性表的每个元素存储一个单词和对应的频率。对文件扫描时，每扫描到一个单词，可以对该线性表做二分查找（前提是线性表里的单词有序），然后对频率加1。为了加快查找速度，