数据结构课程设计指导书计算机科学与技术学院2016年1月目录1前言 (3)2 顺序表与链表 (6)2.1 实验内容 (6)2.2 实现提示 (7)3 树和二叉树 (8)3.1 实验内容 (8)3.2 实现提示 (8)4 图 (9)4.1 实验内容 (9)4.2 实现提示 (10)5 赫夫曼编码 (11)5.1赫夫曼编码的应用 (11)5.2设计要求 (11)5.3 实验内容 (12)5.4 问题分析 (13)5.5 实现提示 (13)1前言《数据结构》是计算机科学与技术专业的一门核心专业基础课程，它主要介绍线性结构、树型结构和图型结构的存储实现与基本操作，尤其是查找与排序算法的实现，并分析相应算法的时间、空间效率。
其主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习，要求学生掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案、设计出简洁、高效、实用的算法，并为后续课程的学习及软件开发打下良好的基础。
为了更好地配合数据结构课程的实践，特编写此课程设计指导书。
1.1指导思想本次课程设计的指导思想是：1、学习获取知识的方法；2、提高发现问题、分析问题和解决实际问题的能力；3、加强创新意识和创新精神；4、加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。
1.2设计任务本次课程设计任务主要分为个人任务和小组任务两种。
个人基本任务：完成第2章以及第3章中的设计任务，其中选做题可不做。
小组任务：完成第4章和第5章的设计任务，其中选做题可不做。
1.3要求1、每项目小组人员为3~5名。
2、每项目小组提交一份课程设计报告，内容包括：课题名称（第4、第5个任务为两个课题），课题参加人员名单和贡献度，课题的目的，课题内容，需求分析、概要设计、主要代码分析、测试结果、课题特色和创新之处、使用说明、收获与体会。
3、每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。
无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。
1.4参考进度第1天，布置任务。
第1、2、3天，完成第2章任务第4、5、6天，开始第3章任务。
第7到10天，完成小组任务。
说明：以上所指的“天”为一个时间段，也就是我们半天的上课时间。
1.5成绩评定采用小组考核和个人考核两级考核方法。
1、小组考核（1）圆满完成第4章和第5章的全部内容的小组成绩为优。
（2）第4章选做题任务未完成的小组成绩为良。
（3）未通过验收的项目为不及格。
2、个人考核：全部完成并经过良好测试才能评优。
个人未完成选做题任务的为良；个人只完成所有个人任务的一半以上的为及格；个人成绩的评定还受项目组成绩影响。
3、小组成绩折算成个人成绩方法：小组交实验报告时同时交一份成员贡献表（该贡献表位于封面的下一页），表格式如下：学号姓名贡献度101张三120102李四90103王五90104钱六100（总计）400上表中，如果成员数为4，则贡献度总和为400。
如果小组成绩为80分，则折算到个人的成绩如下：张三：80*120/100=96分李四：80*90/100=72分王五：80*90/100=72分钱六：80*100/100=80分如果某小组无此表格，则每个成员的贡献度按100计算。
如果某小组的贡献度平均值大于100，则降低组长的贡献度，使得平均值为100。
如果某同学折算的小组成绩超过100分，则按100分计。
1.6注意事项：1、迟到3次或缺席一次，成绩下降一个档次，迟到6次或缺席2次，成绩再下降一个档次，依次类推。
2、上机时发现玩游戏一次，成绩下降一个档次，玩游戏二次，成绩再下降一个档次，依次类推。
3、课程设计开始前，各班的同学在班内自由组合，形成小组，每小组自行推荐小组长一人，在课程设计开始的第一天上交组长名单、小组组员名单，名单上注明班级、学号、姓名。
4、小组成员尽量坐在一起，在电脑正常的情况下，座位需要固定下来。
1.7参考书目[1] 严蔚敏等著，数据结构（C语言版），清华大学出版社2 顺序表与链表2.1 实验内容1、顺序表的应用(1)．对于顺序存储的线性表，请实现以下功能：1）实现二路归并排序算法。
2）实现快速排序算法。
3）实现堆排序算法。
4）实现冒泡排序和选择排序算法(2)．已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。
要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。
(3)．编写一个主函数,调试上述算法。
注：需要额外设计一个线性表初始化的函数。
(4). 对上述五个排序算法，使用两个长度为50万的线性表分别测试其性能，记录其运行时间（生成线性表的时间不计算在内）。
第一个：线性表内的元素值随机生成；第二个：线性表的第i个元素值为i，即本来就有序。
说明：如果算法本身原因导致程序运行出错，可不做改进，在实验报告中说明现象即可。
2、链表的应用(1)．假设有两个按元素值递增次序排列的线性表A和B，均以单链表形式存储，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等(相当于求集合的交集)。
比如，A中元素为（1,3,5,7,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由用户输入，请输出当选大王的猴子的编号。
(3)．设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prev（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。
在链表被起用前，其值均初始化为零。
每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。
试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
(4)．对于稀疏矩阵的存储，可不使用二维数组来存储，而使用链表，只存储其中的非0元素。
链表中的每个结点包含的域为（行，列，值, next），如以下稀疏矩阵：02000300060000000700则链表为：请实现两个稀疏矩阵的相加，并输出结果。
要求：相加后原来的两个矩阵仍然存在。
(5)．在主函数中设计一个简单的菜单，分别调试上述算法。
3、选做题(1)．对顺序表的快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排序的效率，而且界值也并不一定是被顺序表中的一个元素。
例如，我们可以用被划分序列中所有元素的平均值作为界值。
编写算法实现以平均值为界值的快速排序方法。
(2)．设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。
试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。
2.2 实现提示（1）顺序表的第2题：顺序表中删除值为item的元素：并未要求元素间的相对位置不变。
因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。
（2）选做题的快速排序：保存划分的第一个元素。
以平均值作为枢轴，进行普通的快速排序，最后枢轴的位置存入已保存的第一个元素，若此关键字小于平均值，则它属于左半部，否则属于右半部。
（3）选做题的二路归并排序：先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。
当队列不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。
如果队列中退出一个有序子链表后变成空队列, 则算法结束。
这个有序子链表即为所求。
3 树和二叉树3.1 实验内容1.基本题（1）输入字符序列，建立二叉链表。
（2）遍历二叉树输出。
（3）在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。
3.2 实现提示（1）基本题第3题：非递归后序遍历该二叉树，由于最后才访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。
4 图4.1 实验内容1.有向图（1）键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。
（2）采用邻接表存储实现有向图的深度优先遍历。
（3）试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。
（4）已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。
（5）在主函数中设计一个简单的菜单，分别调试上述算法。
2.无向图（1）建立一个无向图的邻接表，并输出该邻接表。
（2）采用邻接表存储实现无向图的深度优先遍历。
（3）无向图采用邻接表存储方式，试写出删除边（i，j）的算法，并输出深度优先遍历的结果。
（4）在主函数中设计一个简单的菜单，分别调试上述算法。
3.选做题：（1）最小生成树问题：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
设无向图的顶点数不超过30个，并为简单起见，图中边的权值设成小于100的整数。
步骤：1)利用普里姆算法求网的最小生成树。
2)以文本形式输出生成树中各条边以及他们的权值.例.测试运行实例：对下图求最小生成树。
（2）关键路径问题步骤：1、建立AOE网的存储结构2、对AOE网进行拓扑排序，同时按拓扑序列的次序求出各顶点事件的最早发生时间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赫夫曼编码的应用赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。