大 连 科 技 学 院
数据结构课程设计
题 目 排序综合
学生姓名 专业班级
指导教师 职 称 副教授
所在单位 信息科学系软件教研室
教学部主任
完成日期 20##年1月11日
课程设计报告单
数据结构课程设计任务书
一、任务及要求：
1. 设计（研究）任务和要求
研究内容：排序综合
任务和要求：
（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。
（2）对指导教师下达的题目进行系统分析。
（3）根据分析结果完成系统设计。
（4）编程：在计算机上实现题目的代码实现。
（5）完成对该系统的测试和调试。
（6）提交课程设计报告。
要求完成课程设计报告3000字以上(约二十页)。
完成若干综合性程序设计题目，综合设计题目的语句行数的和在100行语句以上。
2.原始依据
结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3.参考题目：
二、工作量
2周（10个工作日）时间
三、计划安排
第1个工作日：查找相关资料、书籍，阅读示例文档，选择题目。
第2个工作日－第3个工作日：设计程序结构、模块图。
第4个工作日－第9个工作日：完成程序的编码，并且自己调试、测试。穿插进行课程设计报告的撰写。
第10个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。
指导教师签字：
20##年12月24日
目 录
排序综合................................................................. 1
1.需求分析............................................................... 1
1.1任务描述....................................................... 1
1.2功能分析....................................................... 1
2.概要设计............................................................... 1
2.1主要全程变量和数据结构.......................................... 1
2.2程序模块结构.................................................... 2
3.详细设计............................................................... 3
3.1程序的主要结构如下图所示。...................................... 3
3.3显示各排序算法排序后的的数据。.................................. 4
3.4函数实现（例如直接插入排序）.................................... 4
4.调试分析............................................................... 5
5.测试结果及运行效果.................................................... 7
参考文献................................................................ 11
附录全部代码........................................................... 12
数据结构课程设计总结................................................... 24
排序综合
1.需求分析
1.1任务描述
至少采用3种方法实现上述问题求解，并把排序后的结果保存在不同的文件中。
1.2功能分析
显示随机数，是调用rand()函数输出数组a[]。数组a[]中保存有随机产生的随机数；直接选择排序，是通过n-1次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之；起泡排序，是如果有n个数，则要进行n-1趟比较，在
将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个排序中的记录“基本有序”时，在对全体记录进行一次直接插入排序；直接插入排序，是将一个记录插入到以排序好的有序表中，从而得到一个新的记录数增1的有序表。设整个排序有n个数，则 进行n-1趟排序，即:先将序列中的第一个记录看成一个有序的子序列，然后第2个记录起逐个进行插入，直接整个序列变成按关键字非递减有序列为止；快速排序，是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；堆排序，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
2.概要设计
2.1主要全程变量和数据结构
(1) 数据结构：
#include "stdlib.h"
#include <stdio.h>
#define s 100
typedef struct record
{int key;};
static struct record a1[s],a2[s],a3[s],a4[s],a5[s],a6[s],rec;
int a[7],b[7];file()
(2) 算法的入口及其说明
#include<stdio.h>
#define s 100 //宏定义命令
typedef struct record //记录声明的结构体
{int key;};//定义变量
static struct record a1[s],a2[s],a3[s],a4[s],a5[s],a6[s],rec;
int a[7],b[7]; //记录静态变量结构体
file() //系统定义
{
printf(" ********************************* \n");
printf(" *** *1. 直接插入排序 *** \n");
printf(" *** *2. 希尔排序 *** \n");
printf(" *** *3. 起泡排序 *** \n");
printf(" *** *4. 快速排序 *** \n");
printf(" *** *5. 简单选择排序 *** \n");
printf(" *** *6. 堆排序 *** \n");
printf(" *** *7. 总结 *** \n");
printf(" *** *0. 退出 *** \n");
printf(" ********************************* \n"); }
以上printf(" ********************************* \n");为系统主菜单输出
2.2程序模块结构
程序划分为以下几个模块（即实现程序功能所需的函数）
主控菜单项选择函数:menu_select()
插入排序函数:InsertSort（）
选择排序函数：StlectSort()
起泡排序函数：BubbleSort()
堆排序函数：heapsort（）
快速排序函数：Quicksort（）
希尔排序：Shell Sort（）
3.详细设计
3.1程序的主要结构如下图所示。
图3-1函数调用关系图
其中main()是主函数，它进行菜单驱动，根据选择项1~0调用相应的函数
3.2数据结构定义
图3-2课程设计流程图
3.3显示各排序算法排序后的的数据。
图3-3程序工作流程图
3.4函数实现（例如直接插入排序）
#include "stdlib.h"
#include <stdio.h>
#define s 100
typedef struct record
{int key;};
static struct record a1[s],a2[s],a3[s],a4[s],a5[s],a6[s],rec;
int a[7],b[7];
file()
{
printf(" ********************************* \n");
printf(" *** *1. 直接插入排序 *** \n");
printf(" *** *0. 退出 *** \n");
printf(" ********************************* \n"); }
void Straight_insert_sort(r,n) /*直接插入*/
struct record r[];
int n;
{ int i,j;
a[1]=0;b[1]=0;
for(i=1;i<=n;i++)
printf("%4d",r[i].key);
printf("\n");
for(i=2;i<=n;i++)
{ r[0]=r[i];
j=i-1;
while((j>=0) && (r[0].key<r[j].key))
{ b[1]++;
r[j+1]=r[j--];
r[j+1]=r[0];
a[1]=a[1]+2;
}
}
printf("************直接插入******************\n");
for(i=1;i<=n;i++)
printf("%4d",r[i]);
printf("\n");
printf("move:%d time, compete:%d time",a[1],b[1]);
printf("\n");
}
4.调试分析
4.1 直接插入排序
将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表
4.2 起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，知道第N-1个和第N个记录的关键字进行过比较为止。上述为第一趟排序。其结果使得关键字的最大被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。
4.3 直接选择排序
每一趟从待排序的记录中选出关键字最小的，顺序放在以排好序的子文件的最后，知道全部记录排序完毕。
4.4 希尔排序
先取一个小于n的整数d，作为第一个增量，把文件全部记录全部分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在个组中进行直接插入排序：然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1）,即所有记录放在同一组中进行直接插入排序为止。
4.5 快速排序
设置两个变量i、j，排序开始的时候：i=0，j=N-1； 以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换；从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
4.6 堆排序
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）。
图4-1时间复杂度分析
5.测试结果及运行效果
（1） 运行程序进入程序开始菜单
图5-1开始菜单
（2）开始菜单中会出现四个选项：①完全有序的情况；②逆序的情况；③随机排序的情况；④退出。运行时选择了③随机排序的情况，得到100个随机数的随机排序，如下图。
图5-2随机排序
（3）得出随机数字后，程序列出七个选项：①冒泡排序；②直接插入排序；③简单选择排序；④快速排序；⑤希尔排序；⑥堆排序；⑦退出。选择①冒泡排序，对100个随机数进行冒泡排序，得到结果如下图。
图5-3起泡排序
（4）为了测试该程序，下面继续尝试进行了其他几种排序方式，结果如下图所示。
图5-4直接插入排序
图5-5简单选择排序
简单选择排序结果如上图
图5-6快速排序
快速排序结果如上图
图5-7希尔排序
希尔排序结果如上图
图5-8堆排序
堆排序结果如上图
以上图片为各种排序的结果，排序结果后显示出各种方式排序所用移动次数和比较次数，以方便比较使用。
参考文献
[1] 严蔚敏 吴伟民著.《数据结构(C语言版).清华大学出版.1999年第一版
[2] 陈一华等编.数据结构---使用C 语言.电子科技大学出版社.1998年第一版
[3] 谭浩强.C语言程序设计（第二版）.北京.高等教育出版社.2002
附录 全部代码
#include "stdlib.h"
#include <stdio.h>
#define s 100
typedef struct record
{int key;};
static struct record a1[s],a2[s],a3[s],a4[s],a5[s],a6[s],rec;
int a[7],b[7];
file()
{
printf(" ********************************* \n");
printf(" *** *1. 直接插入排序 *** \n");
printf(" *** *2. 希尔排序 *** \n");
printf(" *** *3. 冒泡排序 *** \n");
printf(" *** *4. 快速排序 *** \n");
printf(" *** *5. 简单选择排序 *** \n");
printf(" *** *6. 堆排序 *** \n");
printf(" *** *7. 总结 *** \n");
printf(" *** *0. 退出 *** \n");
printf(" ********************************* \n"); }
void Straight_insert_sort(r,n) /*直接插入*/
struct record r[];
int n;
{ int i,j;
a[1]=0;b[1]=0;
for(i=1;i<=n;i++)
printf("%4d",r[i].key);
printf("\n");
for(i=2;i<=n;i++)
{ r[0]=r[i];
j=i-1;
while((j>=0) && (r[0].key<r[j].key))
{ b[1]++;
r[j+1]=r[j--];
r[j+1]=r[0];
a[1]=a[1]+2;
}
}
printf("************直接插入******************\n");
for(i=1;i<=n;i++)
printf("%4d",r[i]);
printf("\n");
printf("move:%d time, compete:%d time",a[1],b[1]);
printf("\n");
}
void Shell_sort(r,n) /* 希 尔 排 序 */
struct record r[];
int n;
{ struct record rec,temp;
int i,j,t,h;
a[2]=0;b[2]=0;
for(i=1;i<=n;i++)
printf("%4d",r[i].key);
printf("\n");
t=n/2;
while(t>=1)
{ h=t;
for(j=h;j<n;j++)
{ rec=r[j];
i=j-h;
while((i>=0) && (r[i].key>rec.key))
{ b[3]++;
temp=r[i+h];
r[i+h]=r[i];
r[i]=temp;
i=i-h;
a[2]=a[2]+3;
}
}
t=t/2;
b[2]++;
}
printf("************************希 尔 排 序**************************\n");
for(i=0;i<n;i++)
printf("%4d",r[i]);
printf("\n");
printf("move:%d time, compete:%d time",a[3],b[3]);
printf("\n");
}
void Bubblle_sort(r,n) /* 冒 泡 排 序 */
struct record r[];
int n;
{ struct record rec;
int i,j,m,flag;
a[3]=0;b[3]=0;
for(i=1;i<=n;i++)
printf("%4d",r[i].key);
printf("\n");
m=n;
flag=1;
for(i=1;i<=m-1;i++)
{ flag=0;
for(j=0;j<=m-i-1;j++)
if(r[j].key>r[j+1].key)
{ b[3]++;
rec.key=r[j].key;
r[j].key=r[j+1].key;
r[j+1].key=rec.key;
a[3]=a[3]+3;
flag=1;
}
if(flag==0) break;
}
printf("*************冒 泡 排 序****************\n");
for(i=0;i<n;i++)
printf("%4d",r[i].key);
printf("\n");
printf("move: %d time, compete: %d time",a[3],b[3]);
printf("\n");
}
int push(h,top,m,n)
int h[];
int top ,m,n;
{ h[++top]=m;
h[++top]=n;
return(top);
}
int pop(h,top,m,n)
int h[], top,*m,*n;
{ *m=h[top--];
*n=h[top--];
return(top);
}
int quick(r,i,j)
struct record r[];
int i,j;
{
rec=r[i];
while(i<j)
{ while((i<j)&&(r[j].key>rec.key))
j--;
b[4]++;
if(i<j)
r[i++]=r[j];
a[4]++;
while((i<j)&&(r[i].key<=rec.key))
i++;
b[4]++;
if(i<j)
r[j--]=r[i];
a[4]++;
}
r[i]=rec;
a[4]++;
return(i);
}
void Quick_sort(r,l,h) /* 快 速 排 序 */
struct record r[];
int l,h;
{ int ss[s];
int top,i,j,k;
for(i=1;i<=s;i++)
printf("%4d",r[i].key);
printf("\n");
i=l;
j=h;
top=-1;
do
{ while(i<j)
{ k=quick(r,i,j);
if(j-k>1)
top=push(ss,top,k+1,j);
j=k-1;
}
if(top>0)
top=pop(ss,top,&j,&i);
}
while((top>=0)||(i<j));
printf("**************************快 速 排 序*************************\n");
for(i=1;i<=s;i++)
printf("%4d",r[i].key);
printf("\n");
printf("move: %d time, compete: %d time",a[4],b[4]);
}
void Simple_select_sort(r,n) /* 简 单 选 择 排 序 */
struct record r[];
int n;
{
int i,j,m;
a[5]=0;b[5]=0;
for(i=1;i<=n;i++)
printf("%4d",r[i].key);
printf("\n");
for(i=1;i<=n-1;i++)
{ m=i;
for(j=i+1;j<=n;j++)
if(r[j].key<r[m].key)
m=j;
b[5]++;
if(i!=m)
{ rec=r[i];
r[i]=r[m];
r[m]=rec;
a[5]=a[5]+3;
}
}
printf("************************简 单 选 择************************\n");
for(i=1;i<=s;i++)
printf("%4d",r[i].key);
printf("\n");
printf("move:%d time, compete:%d time",a[5],b[5]);
printf("\n");
}
void p(r,n) /* 次数排列 */
int r[];
int n;
{ int rec;
int i,j;
for(i=1;i<=n;i++)
{ rec=r[i];
j=i-1;
while((j>0) && (rec<r[j]))
{ r[j+1]=r[j];
j=j-1;
}
r[j+1]=rec;}
if(r==a)
printf("关 键 字 移 动 次 数 排 列:\n");
else
printf("关 键 字 比 较 次 数 排 列:\n");
for(i=1;i<=n;i++)
printf("%8d",r[i]);
printf("\n");
}
void heap(r,l,m) /* 堆的子函数 */
struct record r[];
int l,m;
{ int i,j;
i=l;
j=2*i;
rec=r[i];
while(j<=m)
{ if((j<m)&&(r[j].key>r[j+1].key))
j++;
b[6]++;
if(rec.key>r[j].key)
{ b[6]++;
r[i]=r[j];
i=j;
j=2*i;
a[6]++;
}
else j=m+1;
}
r[i]=rec;
}
void Heap_sort(r,n) /* 堆 排 序 */
struct record r[];
int n;
{
int l;
a[6]=0;b[6]=0;
for(l=1;l<=n;l++)
printf("%4d",r[l].key);
printf("\n");
for(l=n/2;l>=1;l--)
heap(r,l,n);
for(l=n;l>=2;l--)
{ rec=r[1];
r[1]=r[l];
r[l]=rec;
a[6]=a[6]+3;
heap(r,1,l-1);
}
printf("****************************堆 排 序***************************\n");
for(l=n;l>=1;l--)
printf("%4d",r[l].key);
printf("\n");
printf("move: %d time, compete: %d time ",a[6],b[6]);
printf("\n");
}
compete()
{
printf(" ** 内 部 排 序 结 果 汇 总 ** \n");
printf(" -------------------------------------------------------- \n");
printf(" 移动次数 比较次数 \n");
printf(" ---------------------------------------------------------\n");
printf(" 直接插入 %6d %8d \n ",a[1],b[1]);
printf(" 希尔排序 %6d %8d \n ",a[2],b[2]);
printf(" 冒泡排序 %4d %8d \n ",a[3],b[3]);
printf(" 快速排序 %4d %8d \n ",a[4],b[4]);
printf(" 简单选择 %4d %8d \n ",a[5],b[5]);
printf(" 堆的排序 %4d %8d \n ",a[6],b[6]);
printf(" ------------------------------------------------------- \n");
}
main()
{char ch;
int i,j,t,k;
printf("***************************\n ");
printf("请选择初始时数的顺序\n");
printf("1---完全有序的情况\n");
printf("2---逆序的情况\n");
printf("3---随机排序的情况\n");
printf("0---退出\n");
printf("***************************\n");
ch=getch();
switch(ch)
{
case '1': rand();
for(i=0;i<s;i++)
printf("%5d",a[i]=rand(5));
for(i=0;i<s-1;i++)
for(j=i+1;j<s;j++)
if(a[i]>a[j])
{t=a[i];
a[i]=a[j];
a[j]=t;
}
printf("完全有序的数列为:\n");
for(i=0;i<s;i++)
printf("%5d",a[i]);
printf("\n");
for(i=1;i<7;i++)
{
printf("请选择排序算法\n");
printf(" 冒泡排序-------------------1\n");
printf(" 直接插入排序---------------2\n");
printf(" 简单选择排序---------------3\n");
printf(" 快速排序-------------------4\n");
printf(" 希尔排序-------------------5\n");
printf(" 堆排序---------------------6\n");
printf(" 退出-----------------------0\n");
ch=getch();
switch(ch)
{case '0':exit(0);
case'1': Bubblle_sort(a,s);break;
case'2': Straight_insert_sort(a,s);break;
case'3': Simple_select_sort(a,s);break;
case'4': Quick_sort(a,0,s-1);break;
case'5': Shell_sort(a,s);break;
case'6': Heap_sort(a,s);break;
default:exit(0);
}
}break;
case '2': rand();
for(i=0;i<s;i++)
printf("%5d",a[i]=rand(5));
for(i=0;i<s-1;i++)
for(j=i+1;j<s;j++)
if(a[i]<a[j])
{t=a[i];
a[i]=a[j];
a[j]=t;
}
printf("逆序的数列为:\n");
for(i=0;i<s;i++)
printf("%5d",a[i]);
printf("\n");
for(i=0;i<7;i++){
printf("请选择排序算法\n");
printf(" 冒泡排序-------------------1\n");
printf(" 直接插入排序---------------2\n");
printf(" 简单选择排序---------------3\n");
printf(" 快速排序-------------------4\n");
printf(" 希尔排序-------------------5\n");
printf(" 堆排序---------------------6\n");
printf(" 退出-----------------------0\n");
ch=getch();
switch(ch)
{case '0':exit(0);
case'1': Bubblle_sort(a,s);break;
case'2': Straight_insert_sort(a,s);break;
case'3': Simple_select_sort(a,s);break;
case'4': Quick_sort(a,0,s-1);break;
case'5': Shell_sort(a,s);break;
case'6': Heap_sort(a,s);break;
default:exit(0);
}
}break;
case '3':printf("从0到%d获得%d个随机数:\n",100-1,s);
rand();
/*while(k<6)*/
for(i=0;i<s;i++)
printf("%5d",a[i]=rand(5));
for(i=0;i<6;i++){
printf("请选择排序算法\n");
printf(" 冒泡排序-------------------1\n");
printf(" 直接插入排序---------------2\n");
printf(" 简单选择排序---------------3\n");
printf(" 快速排序-------------------4\n");
printf(" 希尔排序-------------------5\n");
printf(" 堆排序---------------------6\n");
printf(" 退出-----------------------0\n");
ch=getch();
switch(ch)
{case '0':exit(0);
case'1': Bubblle_sort(a,s);break;
case'2': Straight_insert_sort(a,s);break;
case'3': Simple_select_sort(a,s);break;
case'4': Quick_sort(a,0,s-1);break;
case'5': Shell_sort(a,s);break;
case'6': Heap_sort(a,s);break;
default:exit(0);
}
}
break;
case '0':exit(0);
default:exit(0);
数据结构课程设计总结
好的算法+编程技巧++高效率=好的程序。
1. 做什么都需要耐心，做设计程序更需要耐心。一开始的时候，我写函数写得很快，可是等到最后调试的时候发现错误很隐蔽，就很浪费时间了。后来我在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。
2. 做任何事情我觉得都应该有个总体规划。之后的工作按照规划逐步展开完成。对一个完整的程序设计，首先要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试，而不是一次一口气写完，然后在花几倍的时间调试。一步步来，走好一步在走下一步。写程序是这样，做项目也是这样，过我们得生活更是应该这样这样。
3. 感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人得综合素质，专业知识，坚定耐心，锲而不舍，真的缺一不可啊。
4. 通过这次课程设计，不仅仅复习了c语言相关知识，巩固了数据结构关于排序的算法等知识，更磨砺了我的意志。