数据结构课程设计五种排序算法

《数据结构课程设计五种排序算法》由会员分享，可在线阅读，更多相关《数据结构课程设计五种排序算法（30页珍藏版）》请在装配图网上搜索。

1、武汉理工大学数据结构课程设计说明书课程设计任务书题 目: 排序码比较次数、记录移动次数的定量分析初始条件：理论：学习了数据结构课程，掌握了一种计算机高级语言。实践：计算机技术系实验中心提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）选择书中35个排序算法，对它们稍作修改，即在算法中插入关于排序码比较次数和元素移动次数的统计语句。用修改后的排序算法对同一个随机数序分别进行排序，统计排序过程中排序码的比较次数和元素的移动次数。 （2）至少分析5组排序码。每组排序码由键盘输入或者随机函数产生。2、数据结构设计；3

2、、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。时间安排： 2012年1月2日6日 （第18周）1月2日 查阅资料1月3日 系统设计，数据结构设计，算法设计1月4日-5日 编程并上机调试1月6日 撰写报告1月7日 验收程序，提交设计报告书。指导教师签名： 2012年1月2日系主任（或责任教师）签名： 年 月 日目录摘要1Abstract21引言 32需求分析 42.1基础分析 4 2.2功能分析 43数据结构设计 5

3、3.1头文件 53.2结构体定义 53.3功能函数与辅助函数的声明 54算法程序的分析设计 64.1定义结构体 64.2输入函数 64.3输出函数 74.4起泡排序的排列和输出函数 74.5直接插入排序的排列和输出函数 84.6简单选择排序的排列和输出函数 94.7快速排序的排列函数 104.8快速排序的输出函数 105程序实现 125.1辅助输出函数 125.2主函数 126运行结果14 6.1初始界面 14 6.2第一次输入长度 14 6.3第一次输入排序码及其所得结果 146.4第二次输入长度 14 6.5第二次输入排序码及其所得结果 156.6第三次输入长度 156.7第三次输入排序码

4、及其所得结果：166.8第四次输入长度 17 6.9第四次输入排序码及其所得结果 18 6.10第五次输入长度 196.11第五次输入排序码及其所得结果 207有关技术的讨论 238设计体会 24结束语25参考文献 26摘要:该程序主要是用来对同一个随机数序分别进行排序，并统计排序过程中排序码的比较次数和元素的移动次数。通过输入不同的随机数序，从而辨别数序对于不同的排序算法而言，其排序的复杂程度，从而选择其中较为简单的方法用于数序的排列。同时可以判断同一组数据在输入的顺序不同时将得到不同的结果，从而证明输入对排序结果和排序复杂度的影响。本程序是以VC+6.0为开发工具，并多用面向对象程序设计语

5、言C+来实现的。关键词：结构体 起泡排序 直接插入排序 简单选择排序 快速排序Abstract：The program is primarily used for the same sequence of random number respectively to sort and statistics in the process of sorting the comparison of the sort code number and element number of moves. Through the input different random sequence in order

6、to identify sequence number for different sort algorithm is concerned, its sort of sophistication, and choosing among the more simple method used in sequence of number. At the same time can judge the same set of data in the order of the input is not the same will get different results, so as to prov

7、e the input to sort results and sort the influence of complexity. The program is based on vc + + 6.0 as a development tool, and multi-purpose object-oriented programming language C+ to fulfill.Keyword: Structure Bubble Sort Bubble Sort simple selection sort Quicksort1 引言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机

8、学科的核心课称，而且已成为其他理工专业的热门选修课。数据结构是一门专业选技术基础科。一方面，它要求我们学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求我们编写的程序结构清楚和正确易读，复合软件工程的规范，并培养我们的数据抽象能力。本次课程设计就是对数据结构中的排序及其算法的应用。排序是计算机程序设计中的一项重要操作，它的功能是讲一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便，我们通常希望计算机中的表是按关

9、键字有序的。因为有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能进行顺序查找，效率很低。因此，学习和研究各种排序算法是计算机工作者的重要课题之一。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序分为内部排序和外部排序两大类。此课程设计的内容是对内部排序的应用。2 需求分析2.1基础分析根据要求，系统应该具备以下两种功能：1选择书中35个内部排序的算法，并对它们稍作修改，即在算法中插入关于排序码比较次数和元素移动次数的统计的语句。并用修改后的排序算法对同一个随机数序分别进行排序，统计在此次排序过程中排序码的比较次数和元素的移动次数。2至少要分析5组排序码，且每组

10、排序码由键盘输入或者随机函数产生。2.2功能分析针对以上两个方面需求，对其仔细分析并得到的解决方案即程序应具备的功能如下：1 要对同一个随机数序分别进行排序，并统计在排序过程中排序码的比较次数和元素的移动次数，就需要建立一个共同的输出函数和输入函数，并且要对数序进行各种排序，从而统一输出。2 对于同一输入的排序码，由于要四次调用，则需要建立一个数组，并用for循环来使其排序时的初始值相同，从而达到比较的目的。3 要至少分析五组排序码，就要在主函数（即main函数）建立一个for循环，借此循环来使每组排序码互不干扰，独立输出。3 数据结构设计3.1头文件：#include <iostrea

11、m>using namespace std;3.2结构体定义：struct RecordNode int key; /排序码字段 int value; /记录的其他字段;struct SortObject int n; /n为文件中的记录个数 RecordNode *record; ;3.3功能函数与辅助函数的声明： void InputData(SortObject *pvector) /*待排序的记录关键码的输入*/void OutputData(SortObject *pvector) /*排序表的输出*/void bubbleSort(SortObject * pvector,i

12、nt &n,int &m) /*起泡排序的排列和输出*/void InsSort(SortObject * pvector,int &n,int &m) /*直接插入排序的排列和输出*/void SelectSort(SortObject * pvector,int &n,int &m)bool road_empty(); /*简单选择排序的排列和输出*/void quitsort(SortObject * pvector,int s,int e,int &n,int &m); /*快速排序的排列*/void quitsort_p

13、rin(SortObject * pvector,int &n,int &m); /*快速排序的输出*/4 算法程序的分析设计 本程序主要方法是函数调用，函数比较多但都比较简短，每次操作都有操作提示并且重新输入以下是函数介绍：4.1定义结构体定义整形结构和指针。struct RecordNode int key; /排序码字段 int value; /记录的其他字段;struct SortObjectint n; /n为文件中的记录个数 RecordNode *record; ;4.2输入函数将输入的数组复制并等待应用。void InputData(SortObject *pv

14、ector)cout<<"输入待排序的"<<pvector0->n<<"个记录关键码："int i;for(i=0;i<pvector0->n;i+) cin>>pvector0->recordi.key;for(int j=1;j<4;+j) pvectorj->recordi.key=pvector0->recordi.key;4.3输出函数利用指针和数组输出。void OutputData(SortObject *pvector)cout<<&qu

15、ot;当前排序表为：" for(int i=0;i<pvector->n;i+) cout<<pvector->recordi.key<<" " cout<<endl;4.4起泡排序的排列和输出函数相邻两个数相互比较，将大一点的数置于后边，直到所有数都符合要求。void bubbleSort(SortObject * pvector,int &n,int &m)n=0,m=0; /n为排序码比较次数，m为元素移动次数:int i, j, noswap; RecordNode temp; for(

16、i=0; i<pvector->n-1; i+) / 做n-1次起泡noswap=1; for(j=0; j<pvector->n-i-1; j+) /置交换标志n+;if(pvector->recordj+1.key<pvector->recordj.key) /从前向后扫描temp=pvector->recordj; / 交换记录 pvector->recordj=pvector->recordj+1; pvector->recordj+1=temp; noswap=0;m+; if(noswap) break; /本趟起泡

17、未发生记录交换，算法结束cout<<"起泡排序法: "cout<<"排序码比较次数: "<<n<<" 元素移动次数: "<<m<<" " OutputData(pvector); 4.5直接插入排序的排列和输出函数依次将后面的数插入前面已排好的序列中，并进行排序。void InsSort(SortObject * pvector,int &n,int &m) n=0,m=0;RecordNode temp;int i,j;for

18、( i=1;i<pvector->n;+i)if(pvector->recordi.key<pvector->recordi-1.key)temp=pvector->recordi;for(j=i-1;temp.key<pvector->recordj.key&&j>-1;-j)pvector->recordj+1=pvector->recordj;m+;n+;pvector->recordj+1=temp;n+;m+;n+;cout<<"直接插入排序: "cout<&

19、lt;"排序码比较次数: "<<n<<" 元素移动次数: "<<m<<" " OutputData(pvector); 4.6简单选择排序的排列和输出函数每次选出最小的数置于未排序的数之前，已排序的数之后。void SelectSort(SortObject * pvector,int &n,int &m)n=0,m=0;int i,j,k; for ( i=0 ; i<pvector-> n; +i) k=i;for ( j=i+1 ; j<pvect

20、or-> n ; +j) if (pvector->recordj.key < pvector->recordk.key ) k=j;n+;if ( k!=i) RecordNode x;x= pvector->recordi; pvector->recordi= pvector->recordk;pvector->recordk=x;m+;cout<<"简单选择排序: "cout<<"排序码比较次数: "<<n<<" 元素移动次数: "&

21、lt;<m<<" " OutputData(pvector);4.7快速排序的排列函数采用递归算法进行排序。void quitsort(SortObject * pvector,int s,int e,int &n,int &m) int l=s,r=e;RecordNode x=pvector->records;if(l>r) return;while(l<r)while(l<r&&pvector->recordr.key>=x.key)r-;n+;pvector->recordl

22、=pvector->recordr;while(l<r&&pvector->recordl.key<=x.key)l+;n+;pvector->recordr=pvector->recordl;m+;pvector->recordl.key=x.key;quitsort(pvector,s,r-1,n,m);quitsort(pvector,r+1,e,n,m);4.8快速排序的输出函数void quitsort_prin(SortObject * pvector,int &n,int &m) n=0,m=0;quits

23、ort(pvector,0,pvector->n-1,n,m);cout<<"快速排序: "cout<<"排序码比较次数: "<<n<<" 元素移动次数: "<<m<<" "OutputData(pvector);5 程序实现5.1辅助输出函数：帮助main函数输入排序表，输出四种排序算法所得到的结果。void Showout(int nn,int mm)SortObject *pvector4;int i,n;for(i=0;i<

24、4;+i)pvectori=new SortObject; cout<<"输入排序表的长度：" cin>>n;for(i=0;i<4;+i)pvectori->n=n;pvectori->record=new RecordNoden; InputData(pvector); bubbleSort(pvector0,nn0,mm0);InsSort(pvector1,nn1,mm1);SelectSort(pvector2,nn2,mm2);quitsort_prin(pvector3,nn3,mm3);5.2主函数此项主要输出页面。

25、void main()cout<<"*"<<endl;cout<<" 欢 迎 进 入 排 序 页 面 !"<<endl;cout<<"*"<<endl;int n4=0;int m4=0;int i;for(i=0;i<5;+i)cout<<"第"<<i+1<<"组排序如下:"<<endl;Showout(n,m);int n_min=0;int m_min=0;for(

26、int j=1;j<4;+j)if(nj<nn_min)n_min=j;if(mj<mm_min)m_min=j;cout<<"这次排序中，排序码比较次数最少的是第"<<n_min+1<<"种排序方法."<<endl;cout<<"这次排序中，元素移动的次数最少的是第"<<m_min+1<<"种排序方法."<<endl;cout<<endl;cout<<"*"

27、<<endl;cout<<" 排 序 结 束， 谢 谢 使 用! "<<endl;cout<<"*"<<endl;6 运行结果6.1初始界面：6.2第一次输入长度：6.3第一次输入排序码及其所得结果：6.4第二次输入长度：6.5第二次输入排序码及其所得结果：6.6第三次输入长度：6.7第三次输入排序码及其所得结果：6.8第四次输入长度：6.9第四次输入排序码及其所得结果：6.10第五次输入长度：6.11第五次输入排序码及其所得结果：7 有关技术的讨论本程序多次地运用函数调用，使程序简洁易懂，并且

28、很好地达到了代码重用的效果，从而减少代码量。在函数调用的同时，利用引用使得数据传递变得更加方便，但其它数据若不小心被修改也会影响到全局，这就是其不足。其次程序里用的比较多的就是for语句和while语句，前者既增加了代码的可读性也让选择操作得到很好的实现，而后者主要用于信息输入错误需重新输入和返回主菜单。对于算法设计这方面，我觉得只需给函数输入的想法比较好，这样既能够无误地达到目的，也可以大大地减少程序使用者的操作量。8 设计体会通过这次课程设计，我不仅提高了自己的编程能力，而且让我学会了编写一个程序应该如何去做才能是程序更加完善，让我懂得写程序时应该戒骄戒躁，要仔细阅读题目利用更为简洁的方法

29、解决问题。其次，从其中我学会了编写程序的比较好的方法就是要分析好题目、设计好程序的整体结构、设计算法并列出所需函数、逐个编写函数的代码、和完善美观函数。通过这次编程，我深深体会到了算法的重要性，算法的好坏直接影响到了程序编写的难易与效率。刚拿到排序码操作题目时，心中暗自窃喜，感觉题目不难，比起其他停车场管理系统、图书馆管理系统等题目，我需要写的代码并不会太繁杂，而且只需要加几个统计语句就可以了。然而在实际编写程序的时候，发现并不是那么简单，因为要达到目标，不仅要学会应用数组，还要学会应用指针，当然，还要考虑其他各个方面的问题，并非只是加几个程序语句局可以完成的。此次课程设计让我的设计能力和调试

30、改错能力大大地增强了，这为我的编程过程节省了不少的时间，更加了解了几种排序方法；还有就是在设计之前要分析好所编软件或系统的实用价值与发展前景，看看它是否值得去实现。最后就是这次课程设计让我清楚地认识到了自己的不足，今后需要在自己的不足之处多加努力。结束语此次课程设计让我感慨良多，让我更加了解了程序编写的不易。让我在以后的编程中要更加努力，以便写出更好的，更为简洁易用的程序。学习数据结构让我更加懂得了软件这一行业在当今社会中，软件的重要性，并增加了我对软件这门行业的认识。了解了数据结构这门计算机程序设计的重要理论技术基础。学会了分析研究计算机加工的数据结构的特性，从而便利于应用涉及的数据选择适当

31、的逻辑结构、存储结构及其相应的算法，并初步掌握了算法的时间分析和空间分析的技术。相信在社会的发展中，计算机应用技术会越来越重要，我们应该更加努力。参考文献： 1严蔚敏, 吴伟名. 数据结构（C语言版） 清华大学出版社 2001年1月 2 谭浩强. C程序设计（第三版） 清华大学出版社 2005年7月3 温秀梅，丁学钧. Visual C+面向对象程序设计教程与实验（第二版） 清华大学出版社 2009年4月4 殷人昆，陶永雷，谢若阳，盛绚华.数据结构（用面向对象方法与C+描述） 清华大学出版社 1999年7月5克尼汗. C程序设计语言 机械工业出版社 2004年1月 6刘志红. C语言程序设计习

32、题解答与实验指导 清华大学出版社 2005年7月 7Mark Allen Weiss. 数据结构与算法分析 清华大学出版社 2005年7月 8 吕兵，曲宝军，王玮.Visual C+从初学到精通 电子工业出版社 2010年6月9 徐士良，马尔妮.实用数据结构 清华大学出版社 2011年7月10 Stanley B.Lippman,Josee Lajoie,Barbara E.Moo(著).李师贤，蒋爱军，梅晓勇，林瑛（译） C+ Primer 中文版 人民邮电出版社 2006年6月袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃

33、羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁

34、羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈

35、芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈29