数据结构课程设计-排序算法集成

《数据结构课程设计-排序算法集成》由会员分享，可在线阅读，更多相关《数据结构课程设计-排序算法集成（21页珍藏版）》请在金锄头文库上搜索。

1、xx 大学本科生课程设计论文题 目：排序算法集成学生姓名：学 号：专 业：计算机班 级： 指导教师：2013 年年 5 月月 20 日日xx 大学课程设计任务书课程名称数据结构课程设计设计题目排序算法集成指导教师时间2013.5.20-2013.5.30一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方 法和作风 二、设计资料及参数

2、每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。 排序算法集成 定义动态数组类（或类模板）以表示待排序数据，在此基础上实现多种排序算法。 要求设计函数模板来实现下列排序算法： 直接插入排序 冒泡排序 简单选择排序 希尔排序 快速排序 堆排序并设计主函数测试动态数组类（或类模板） ，测试各排序算法的函数模板。 三、设计要求及成果 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 四、进度安排 资料查阅与讨论（1 天） 系统分析（2 天） 系统的开发

3、与测试（5 天） 编写课程设计说明书和验收（2 天） 五、评分标准 1. 根据平时上机考勤、表现和进度，教师将每天点名和检查 2. 根据课程设计完成情况，必须有可运行的软件。 3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。 4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问 六、建议参考资料 1 数据结构 （C 语言版） 严蔚敏、吴伟民 主编 清华大学出版社 2004.11 2 数据结构课程设计案例精编（用 C/C+描述） ，李建学 等 编著，清华大学出版社 2007.2 3.数据结构:用面向对象方法与 C+语言描述 ，殷人昆 主

4、编， 清华大学出版社 2007.6目目 录录目 录3引言4一算法的设计思想4二算法的流程图4三算法的设计与分析53.1建立数组53.2 算法思想.53.3主要函数63.4主要函数声明63.5 主要变量说明.10四程序源代码11五运行结果与分析（测试）18六总结（收获与体会）20七参考文献21引引 言言本课程设计主要解决 几种不同排序方法 以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。一算法设计的思想一算法设计的思想数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下

5、一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列 。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函

6、数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境。通常，在排序的过程中需进行两种基本操作：（1）比较两个关键字的大小；（ 2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。二算法的流程图二算法的流程图如图 2.1图 2.1 主要设计思想流程图三算法的设计与分析三算法的设计与分析3.1 建立数组建立数组在程序中建立一个数组 data ，用于存储程序运行中的数据。3.2 算法思想算法思想（1）插入排序插入排序的主要算法思想

7、是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增 1 的有序表。（2）希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进建立数组设计 main 函数建立各排序函数结束开始行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（3）冒泡排序函数 冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。（4）选择排序函数选择排序的基本思想是：每一趟在 n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第 i 个记录。（5）堆排序先将

8、一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换） ，再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆） ，依次类推。 3.3 主要函数主要函数（1）插入排序函数void insertion_sort(int,int);/*插入排序*/（2）希尔排序函数void shell_sort(int,int);/*希尔排序*/（3）冒泡排序函数void bubble_sort(int,int);/*冒泡排序*/（4）选择排序函数void select_sort(int,int);/*选择排序*/（5）将数据调整为堆的函数vo

9、id adjust(int,int);/*将数据调整为堆树*/3.43.4 主要函数声明主要函数声明插入排序插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增 1 的有序表。void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0;for(base=1;base0 compare-;datacompare=temp;printf(“第%d 趟排序:“ ,j);for(i=0;i0)for(i=incr+1;i0)if(datajdataj+incr)/*比较每部分

10、的数据大小顺序不对则交换*/ temp=dataj;dataj=dataj+incr;dataj+incr=temp;j=j-incr;elsej=0;num+;printf(“n 第%d 趟排序:“,num);for(k=1;kdataj+1)flag=1;temp=dataj;dataj=dataj+1;dataj+1=temp;num+;printf(“n 第%d 趟排序：“,num);for(k=0;k void insertion_sort(int,int);/*插入排序*/void shell_sort(int,int);/*希尔排序*/void bubble_sort(int,i

11、nt);/*冒泡排序*/void select_sort(int,int);/*选择排序*/void adjust(int,int);/*将数据调整为堆树*/void insertion_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0;for(base=1;base0 compare-;datacompare=temp;printf(“第%d 趟排序:“ ,j);for(i=0;i0)for(i=incr+1;i0)if(datajdataj+incr)/*比较每部分的数据大小顺序不对则交换*/ temp=dataj;dat

12、aj=dataj+incr;dataj+incr=temp;j=j-incr;elsej=0;num+;printf(“n 第%d 趟排序:“,num);for(k=1;kdataj+1) flag=1;temp=dataj;dataj=dataj+1;dataj+1=temp;num+;printf(“n 第%d 趟排序：“,num);for(k=0;k=dataj)done=1;elsedataj/2=dataj;j=2*j;dataj/2=k;void main()int data20;int size=0,m=0,i,j,num,k,temp,n=0;printf(“n 请输入初始关键

13、字（输入 0 结束）:n“);doscanf(“%d“,m+;while(datasize+!=0);printf(“你输入的初始关键字为：“);for(j=0;j0;i-)adjust(i,size);printf(“n 堆：“);for(k=1;k0;i-)temp=datai+1;datai+1=data1;data1=temp;/*将树根和最后的节点交换*/adjust(1,i);/*再重新调整为堆树*/n+;printf(“n 第%d 趟排序：“,n);for(k=1;ksize;k+)printf(“%d “,datak);printf(“n 最终排序结果：“);for(k=1;k

14、size;k+)printf(“%d “,datak);printf(“n“);for(i=0;i50;i+)printf(“-“);printf(“n“);break;五运行结果与分析（测试）五运行结果与分析（测试）（1 1）程序开始如图）程序开始如图 4.14.1图 4.1 程序开始界面（2 2）输入关键字以后如图）输入关键字以后如图 4.24.2图 4.2 输入关键字以后界面（3 3）在输入关键字后的排序方法选择如图）在输入关键字后的排序方法选择如图 4.34.3图 4.3 在输入关键字后的排序方法选择界面（4 4）输入）输入 1 1，输出插入排序结果如图，输出插入排序结果如图 4.44

15、.4图 4.4 插入排序输出结果界面（5 5）输入）输入 2 2，输出希尔排序结果如图，输出希尔排序结果如图 4.54.5图 4.5 希尔排序输出结果界面（6 6）输入）输入 3 3，输出冒泡排序结果如图，输出冒泡排序结果如图 4.64.6图 4.6 冒泡排序输出结果（7 7）输入）输入 4 4，输出选择排序结果如图，输出选择排序结果如图 4.74.7图 4.7 选择排序输出结果界面 （8 8）输入）输入 5 5，输出堆排序结果如图，输出堆排序结果如图 4.84.8图 4.7 堆排序输出结果界面六总结（收获与体会）六总结（收获与体会）做这个课程设计，我收获了很多。在课程设计中我遇到了一些平时做作业所没遇到、也不可能遇到的问题。在做课程设计的过程中，加深了对书本知识的理解，同时也培养了自己的动手能力。因为上学期做过一次 C 语言的课程设计，对于课程设计有了一些经验了吧，从总体上来说还算比较顺利，只是之前忙于准备考试，之后做课程设计感觉时间有点紧，应该是我在时间安排上有点问题吧。这次课程设计，是将这一学期学到的论知识用于了实践，在我在实践中得到了很多经验。在看到在自己付出了努力所做出来的成果时，我感到非常的欣慰。最后我还要感谢我的指导老师，感谢在我遇到问题时帮我解决问题的同学，没有你们的帮助我是不可能做好的。我以后还要更加努力，不