数据结构课程设计内部排序算法

课程设计(论文)任务书

软 件 学 院 学 院 软 件+桥梁 专 业 2013—2 班

一、课程设计(论文)题目 内部排序算法比较 二、课程设计(论文)工作自 2014 年 12 月 22 日起至 2014 年 12 月 26 日止

三、课程设计(论文) 地点: 创新大楼软件实训中心机房 四、课程设计(论文)内容要求： 1．本课程设计的目的

⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识， 编写程序求解指定问题；

⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学 生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求：

⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽 象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求

⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式 进行书写和装订；

⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码 实现、调试分析、课设总结、谢辞、参考文献、附录等；

⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分；

1 页 第 1

⑷回答问题：20分； ⑸论文撰写：30分。 4）参考文献：

⑴严蔚敏,吴伟民. 数据结构(C语言版)[M]. 清华大学出版社. 2010.3 ⑵严蔚敏,吴伟民. 数据结构题集(C语言版)[M]. 清华大学出版社. 1999.2 ⑶何钦铭,冯燕等. 数据结构课程设计[M]. 浙江大学出版社. 2007.8 5）课程设计进度安排

⑴准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料； ⑵程序模块设计分析阶段（4学时）：程序概要设计、详细设计； ⑶代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；

⑷撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。

学生签名：

2014 年 12 月 22 日

6）课程设计题目具体要求： 问题描述：

试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感 受。 基本要求：

⑴至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排 序、起泡排序、快速排序、选择排序、堆排序、归并排序）。

⑵待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用 5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次 数（关键字交换计为3次移动）。

⑶最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。

课程设计(论文)评审意见

（1）学习态度（10分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （2）系统设计（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （3）编程调试（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；

1 页 第 2

（4）回答问题（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （5）论文撰写（30分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （6）格式规范性及考勤是否降等级：是（ ）、否（ ）

评阅人： 王英华 职称： 讲师

2014 年 12 月 18 日

1 页 第 3

目录

一、设计任务 .............................. 2

二、需求分析 .............................. 2

三、系统设计 .............................. 3

四、编码的实现 ............................ 4

五、调试分析 .............................. 9

六、课设总结 ............................. 11

七、参考文献 ............................. 12

1 页 第 1

一、设计任务

内部排序算法比较

试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

⑴至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。

⑵待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数。

⑶最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。

二、需求分析

1、界面需求：为了使用户使用起来简洁，要设计一个界面来供用户选择需求的功能，这样用户可根据自己的需求来得到结果，界面帮助用户明白本程序的3种功能。

2、数据需求：用户需要输入随机种子，待排序列就会自动生成，再从3种不同的算法功能中选择一项来得出关键字的比较次数和移动次数。

3、设计需求：使用数据结构中C语言函数来实现3种不同算法的功能以及伪随机数的产生，待排序数用线性表结构来存储，需要求的数据可以根据表示不同范围变量名表示出来或者用特定的符号表示出来。

系统用到的数据：

数据要用伪随机数程序产生

系统要用的函数：

long My_Rand(long b,long c,long m)； //产生随机数记录，再生成伪随机数 long gcd1(long m,long n); //求最大公约数

long gcd(long m); //解决算法的限制因素 Status InitList_Sq（）; //构造一个空的线性表 void CreatList_Sq(SqList &L); //为线性表的各个元素赋值 void InsertSort(SqList &L); //直接插入排序 void ShellSort(SqList &L,int t); //希尔排序

int Partition(SqList &L,int low,int high); //快速排序

1 页 第 2

三、系统设计

3.1系统功能的模块图

系统只要是通过随机数据比较3种算法的关键字比较次数和关键字移动次数，来取得直观感受。用户进入界面需要输入随机种子，待排序列就会自动生成，再通过选择3种排序方式来比较。

请输入一个随机种子整数型 主界面 2.希尔排序 1.直接插入排序 3.快速排序

图3.1系统功能的模块图

3.2概要设计

3种算法功能用3个数据结构中的C语言函数来实现，首先设定随机种子为全局变量，用函数来解决随机数据产生时需考虑的因素，再对用到的函数结果状态代码和函数类型做定义，对线性表结构也定义，对于记载算法中关键字比较的次数和关键字移动的次数，设定为全局变量，在算法功能函数中使用for循环以及while循环来实现算法的递进，也使用if和else的判断语句来判定关键字的大小，在主函数中使用了switch选择结构来给用户提供不同的选择。

1 页 第 3

3.3各个函数的设计

1.实现随机待排序列的产生：设随机种子为全局变量，待排序列根据不同的随机种子数而不同，编写My_Rand（）函数产生随机数，并记录下来，再用来产生下一个伪随机数，编写gcd1（）函数求最大公约数，再编写gcd（）函数解决算法的限制因素。

2．构造线性表：定义线性表的结构，编写InitList_Sq（）函数构造一个空的线性表，在CreatList_Sq（）函数里用My_Rand（）函数为线性表的各个元素赋值。

3．直接插入排序功能：编写InsertSort（）函数对顺序表作直接插入排序，先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

4．希尔排序功能：编写ShellInsert（）函数对顺序表作一趟希尔插入排序和ShellSort（）函数按增量序列对顺序表作希尔排序，基本思想是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序，希尔排序中的一个特点是：子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列，因此关键字较小的记录就不是一步一步地往前挪动，而是跳跃式地往前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。

6．快速排序功能：编写Partition（）函数交换顺序表中子表r [low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它，再编写Qsort（）函数对顺序表中的子序列L.r[low..high]作快速排序和QuickSort（）函数对顺序表作快速排序，它的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序，一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey得记录和枢轴记录互相交换，重复这两步直至low=high为止。

四、编码的实现

4.1随机待排序列的产生模块 long My_Rand(long b,long c,long m)

1 页 第 4

{ }

long gcd1(long m,long n) { long r;

while((r=m%n)!=0) { }

m=n; n=r; return d=(b*d+c)%m;

return n; }

long gcd(long m) { long i=2;

while(gcd1(i,m)!=1)

i++;

return i;

}

4.2直接插入排序功能模块 void InsertSort(SqList &L) {

int i,j,q=0,p=0; for(i=2;i<=L.length;++i) {

q+=1;

if(LT(L.r[i].key,L.r[i-1].key)) {

L.r[0]=L.r[i]; L.r[i]=L.r[i-1];

for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)

1 页 第 5

}

{ }

L.r[j+1]=L.r[0]; p+=3;

L.r[j+1]=L.r[j]; p+=1;

q+=i-2;

}

cout<<\直接插入排序关键字比较次数:\cout<<\直接插入排序关键字移动次数:\

}

4.3希尔排序功能模块 int t=3;

int dlta[]={5,3,1}; int k; int m=0,n=0;

void ShellInsert(SqList &L,int dk) {

int i,j;

for(i=dk+1;i<=L.length;++i) {

n++;

if(LT(L.r[i].key,L.r[i-dk].key)) {

L.r[0]=L.r[i];

for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk) {

L.r[j+dk]=L.r[j];

1 页 第 6

m++;

}

}

n+=(i-dk)/dk; L.r[j+dk]=L.r[0];

m+=2; }

void ShellSort(SqList &L,int t) {

for(k=0;k

ShellInsert(L,dlta[k]); }

cout<<\希尔排序关键字总比较次数:\ }

cout<<\希尔排序关键字总移动次数:\

4.4快速排序功能模块

int x=0,y=0;

int Partition(SqList &L,int low,int high) {

long pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low

while(low=pivotkey) { --high;

1 页 第 7

}

}

}

x++;

L.r[low]=L.r[high];

while(low

L.r[high]=L.r[low]; x+=2; y+=2;

++low; x++;

L.r[low]=L.r[0]; y+=3; return low;

void QSort(SqList &L,int low,int high) { }

void QuickSort(SqList &L) {

int pivotloc; if(low

pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high);

QSort(L,1,L.length);

1 页 第 8

}

cout<<\快速排序关键字总比较次数:\cout<<\快速排序关键字总移动次数:\

五、调试分析

5.1进入界面

进入界面先输入一个随机种子整数型，好生成伪随机数

如图5.1进入界面

5.2选择界面

进入选择的界面，可以任意的选择1.直接插入排序 2.希尔排序 3.快速排序

如图5.2选择界面

1 页 第 9

5.3直接插入排序的比较 选1进入直接插入排序

如图5.3直接插入排序的比较

5.4希尔排序的比较

1 页 第 10

如图5.4希尔排序的比较 5.5快速排序的比较

选3进入快速排序的比较

如图5.5快速排序的比较

六、课设总结

在内部排序算法比较的程序的所有排序方法中，没有哪一种是绝对最优的，有的适用于待排序序列较大的情况，有的适用于待排序序列较小的情况，因此，在实用时需根据不同情况适当选用，甚至可将多种方法结合起来使用，本程序3种排序算法是在顺序存储结构上实现的，因此在排序过程中需进行大量记录的移动，当记录很大时，时间耗费很大，此时可采用静态链表作存储结构。

通过这次课程设计，使我对数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；课程设计，使我懂得了做什么事情只要专心去做，就能够克服各种困难，达到自己的说想要的结果。当然了， 1 页 第 11

同学们和老师的帮助必不可少。从理论中得出结论。此次课程设计使我对自己的专业有了更深刻的认识，从而提高了自己实际动手能力和独立思考问题的能力，总而言之，此次课程设计让我受益颇丰。

在编程过程中，可能在实际应用中有些功能不到位，对更多的功能也未能实现。我将不断提高自己，尤其在相关结点知识方面多努力去学习，多看书，多实践，争取今后在编制程序时，能够认真努力编写出有个性且可读性和应用性较强的数据结构系统。

七、参考文献

⑴严蔚敏,吴伟民. 数据结构(C语言版)[M]. 清华大学出版社. 2010.3 ⑵严蔚敏,吴伟民. 数据结构题集(C语言版)[M]. 清华大学出版社. 1999.2 ⑶何钦铭,冯燕等. 数据结构课程设计[M]. 浙江大学出版社. 2007.8

1 页 第 12

本文来源：https://www.bwwdw.com/article/v5g8.html