1
《数据结构》课程设计报告
实验五 排序
一、需求分析：
本演示程序用C++6.0编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。
（1）分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。
（2）、对存储的函数即输入的数字进行遍历。
（3）、初始化函数对输入的数字进行保存。
（4）、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。
（5）、程序所能达到的功能：完成对输入的数字的生成，并通过对各排序的选择实现 2 数字从小到大的输出。
二、程序主要功能以及基本要求：
（1）、设计一个菜单，格式如下：
1、直接插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、选择排序
6、堆排序
7、退出
（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。
三、系统框架图：
本程序包含了9个函数，它们分别是：
（1）、直接插入排序的算法函数InsertSort（）。
（2）、希尔排序的算法函数ShellSort（）。
（3）、冒泡排序算法函数BubbleSort（）。
（4）、快速排序的算法函数Partition（）。
（5）、选择排序算法函数SelectSort（）。
（6）、堆排序算法函数HeapAdjust（）。
（7）、对存储数字的遍历函数Visit（）。
（8）、初始化函数InitSqList（）。
（9）、主函数main（）。
四、详细设计
实现各个算法的主要内容，下面是各个函数的主要信息：
（1）各个排序函数的算法： 主函数
各个排序算法函数 对输入的数组进行遍历初始化 操作界面的设计，函数的调用。 3 一、直接插入排序
void InsertSort(SqList &L)
{
int i,j;
for( i=2; i<=L.length;i++)
0
课 程 设 计 报 告
课程名称 数据结构
课题名称 拓扑排序
专 业
班 级
学 号
姓 名
指导教师
2011年 6月 16日 1
湖南工程学院
课 程 设 计 任 务 书
一．设计内容：
问题 ：拓扑排序
大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需一定的课时，而各学期的总课时不能超过上限。
测试数据
学期课时上限数：350
各课程所需学时：48
课程先、后修关系如图：
二．设计要求：
课程设计报告内容说明
1)需求分析
程序的功能；输入输出的要求。 1
9 4
2
12
10
11 3
6 5
7
8 2
2)概要设计
程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。
3)详细设计
采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。
4)调试分析以及设计体会
测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。
5)使用说明
用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。
6)书写格式
见附带说明。
7)附录
参考书目； 源程序清单（带注释）
目录 3
封面„„„„„„„„„„„„„„„„„„„„„„„„„„„1
14信计2015-2016（一）
数 据 结 构 课 程 设 计
设计题目 拓扑排序
设计时间 2016.1.11——2016.1.15
学生姓名 冯佳君
学生学号 20140401105
所在班级 14信计1
指导教师 刘 风 华
徐州工程学院数学与物理科学学院
一、 需求分析 成 绩
1.问题描述
本次课程设计题目是：用邻接表构造图 然后进行拓扑排序，输出拓扑排序序列。
拓扑排序的基本思想为：
1)从有向图中选一个无前驱的顶点输出；
2)将此顶点和以它为起点的弧删除；
3) 重复1)、 2)直到不存在无前驱的顶点；
4) 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
2. 拓扑排序 有向图拓朴排序算法的基本步骤如下：
1）从图中选择一个入度为0的顶点，输出该顶点；
2）从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）；
3）重复执行1）、2）直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。
3．基本要求
(1) 输入的形式和输入值的范围；
首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。
数据结构--内部排序算法
1、下列排序算法中，_____________排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
（1）选择 （2）冒泡 （3）归并 （4）堆
2、下列排序算法中，依次将待排序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是___________________。
（1）直接插入排序 （2）冒泡排序 (3)快速排序 （4）直接选择排序
3、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是______________。
（1）直接插入排序列 （2）快速排序 （3）直接选择排序 （4）堆排序
4、依次将待排序序列中的元素和有序子序列合并一个新的有序子序列的算法是______________。
（1）快速排序 （2）插入排序 （3）冒泡排序 （4）堆排序
5、已知数据表A中每个元素距其最终位置不远，则采用_____________排序算法最节省时间。
（1）堆排序 （2）插入排序 （3）快速排序 （4）直接选择排序
6、下列排序算法中，_______________算法可能会出现下面情况，在最后一趟开始之前，所有元素都不在其最终的位置上。
（1）堆排序 （2）冒泡排序 （3）快速排序 （4）插入排序
7、数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________排序算法最节省时间。
（1）堆排序 （2）希尔排序 （3）快速排序 （4）直接选择排序
8、下列算法中，____________每一趟都能选出一个元素放在其最终位置上，并且是不稳定的。
（1）冒泡排序 （2）希尔排序 （3）直接选择排序列 （4）直接插入排序
9、下列排序算法中，某一趟结束后未必能选出一个元素放在其最位置上的是__________________。
