数据结构课程设计
指
导
书
东华大学计算机科学与技术学院
2017年1月
目录
1.前言 (1)
1.1指导思想 (1)
1.2设计任务 (1)
1.3参考进度 (2)
1.4成绩评定 (2)
1.5注意事项 (3)
1.6参考书目 (3)
2．个人任务 (4)
2.1 排序算法设计 (4)
2.2 应用算法设计 (4)
3 小组任务 (6)
3.1 有向图问题 (6)
3.2 最小生成树问题 (6)
3.3 关键路径问题 (6)
1.前言
《数据结构》是计算机科学与技术专业的一门核心专业基础课程，其主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习，要求学生掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案、设计出简洁、高效、实用的算法，并为后续课程的学习及软件开发打下良好的基础。
1.1指导思想
本次课程设计的指导思想是：
1、学习获取知识的方法；
2、提高发现问题、分析问题和解决实际问题的能力；
3、加强创新意识和创新精神；
4、加强团队的分工与合作；
5、掌握面向实际背景思考问题的方法。
1.2设计任务
本次课程设计任务主要分为个人任务和小组任务两种。
个人基本任务：
在DHU-OJ平台上按要求完成“个人任务”部分的设计任务，其中选做题不是必须完成的任务。
小组任务：
完成“小组任务”部分的设计任务，其中选做题不是必须完成的任务。
1.1要求
1、每项目小组人员为3~5名。
2、每项目小组提交一份课程设计报告，内容包括：课题名称，课题参加人
员名单和分工，课题的目的，课题内容，需求分析、概要设计、主要代码
分析、测试结果、课题特色和创新之处、收获与体会、使用说明。
3、每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：
任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试
结果、收获与体会。
无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。
1.3参考进度
第1天，布置任务。
第1-3天，完成个人任务
第3-5天，完成小组任务。
1.4成绩评定
采用小组考核和个人考核两级考核方法。
小组考核
1、圆满完成树形的全部内容的小组成绩为优。
2、树形选做题任务未完成的小组成绩为良。
3、未通过验收的项目为不及格。
个人考核：
1、全部完成并经过良好测试才能评优。
2、个人未完成选做题任务的为良；
3、个人只完成所有个人任务的一半左右的为及格；
4、否则，为不及格；
5、个人成绩的评定还受项目组成绩影响。
小组成绩折算成个人成绩方法：
小组交实验报告时同时交一份成员贡献表，表格式如下页所示。
上表中，如果成员数为4，则贡献度总和为400。
如果小组成绩为80分，则折算到个人的成绩如下：
张三：80*120/100=96分
李四：80*90/100=72分
王五：80*90/100=72分
钱六：80*100/100=80分
如果某小组无此表格，则每个成员的贡献度按100计算。
如果某小组的贡献度平均值大于100，则降低组长的贡献度，使得平均值
为100。
1.5注意事项
1、迟到3次或缺席一次，成绩下降一个档次，迟到6次或缺席2次，成绩
再下降一个档次，依次类推。
2、上机时发现玩游戏一次，成绩下降一个档次，玩游戏二次，成绩再下降
一个档次，依次类推。
3、课程设计开始前，各班的同学在班内自由组合，形成小组，每小组自行
推荐小组长一人，在课程设计开始的第一天上交组长名单、小组组员名单，名单上注明班级、学号、姓名。
1.6参考书目
1、严蔚敏等著，数据结构（C语言版），清华大学出版社
2、翁惠玉等著，数据结构：题解与拓展
3、余腊生等著，数据结构：基于C++模版类的实现
2．个人任务
2.1 排序算法设计
1、对于顺序存储的线性表，请实现以下功能：
1）实现直接插入排序算法；（OJ个人任务1）
2）实现二路归并排序算法；（OJ个人任务2）
3）实现希尔排序算法；（OJ个人任务3）
4）实现快速排序算法；（OJ个人任务4）
5）实现堆排序算法；（OJ个人任务5）
6）实现冒泡排序算法；（OJ个人任务6）
7）实现直接选择排序算法。
（OJ个人任务7）
2、已知一顺序存储的线性表，每个元素都是整数。
在使用顺序表ADT的基础上，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。
（OJ个人任务8）
3、选做题：对上述五个排序算法，使用两个长度为一千万的线性表分别测试其性能，记录其运行时间（生成线性表的时间不计算在内）。
1）线性表内的元素值随机生成；
2）线性表的第i个元素值为i，即本来就有序。
2.2 应用算法设计
1、已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。
要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。
（OJ个人任务9）
2、设带头结点的单链表的头指针为head，结点结构由data和next两个域构成，其中data域为字符型。
在使用单链表ADT的基础上，设计一算法判断该链表的前n个字符是否中心对称。
例如xyx, xyyx都是中心对称。
（OJ个人任务10）
3、在二叉树中查找值为x的结点，在使用二叉树ADT的基础上，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。
算法设计参见OJ平台的“二叉树ADT模板设计”中的题目17。
（OJ个人任务11）
4、要求设计一个非递归算法，在使用二叉树ADT的基础上，实现二叉树的后序遍历。
算法设计参见OJ平台的“二叉树模板简单应用算法设计”中的题目5。
（OJ 个人任务12）
3 小组任务
3.1 有向图问题
1、键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。
（OJ小组任务1）
2、采用邻接表存储实现有向图的深度优先遍历。
（OJ小组任务2）
3、试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj 的路径。
（OJ小组任务3）
4、在使用图的邻接表ADT的基础上，设计一个算法，按照深度优先搜索的思想找出从指定结点出发且长度为m的所有简单路径。
并将此算法加入到邻接表ADT 中，在邻接表ADT中提供一个公有的成员函数FindPath(start, m)。
（OJ小组任务4）
3.2 最小生成树问题
1、若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网，是一个无向网的最小生成树问题。
2、设无向网的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。
3、请参考“图的邻接矩阵ADT模版设计”中的题目3“构造一个有权图”，使用构造函数，构造一个具有结点和边的无向网。
（OJ小组任务5）
4、利用普里姆（Prim）算法求无向网的最小生成树，并以文本形式输出生成树中各条边以及它们的权值。
（OJ小组任务6）
3.3 关键路径问题
1、建立有向网的邻接表存储结构，并对其进行拓扑排序，判断是否为AOE网。
（OJ 小组任务7）
2、在1的基础上，如果建立的有向网为AOE网，按拓扑序列的次序求出各顶点事件的最早发生时间ve，按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。
（OJ小组任务8）
3、在2的基础上，根据各个顶点的Ve和Vl值，求每条弧s（活动）的最早开始时间e[s]和最迟开始时间l[s]。
（OJ小组任务9）
4、在3的基础上，获取关键路径。
（OJ小组任务10）。