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

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

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

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

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

4、与分析53.1建立数组53.2 算法思想53.3主要函数63.4主要函数声明63.5 主要变量说明10四程序源代码11五运行结果与分析（测试）18六总结（收获与体会）20七参考文献21引 言本课程设计主要解决几种不同排序方法以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。一算法设计的思想数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的

5、任意序列重新排列成一个按关键字有序的序列。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。 完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点

6、，适合不同的环境。通常，在排序的过程中需进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。二算法的流程图如图2.1建立数组设计main函数建立各排序函数结束开始图2.1 主要设计思想流程图三算法的设计与分析3.1建立数组在程序中建立一个数组data ，用于存储程序运行中的数据。3.2算法思想（1）插入排序 插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。（2）希尔排序 希尔排序的基本思想是先将整个待排记录列分割成若干子序列

7、分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（3）冒泡排序函数 冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。（4）选择排序函数 选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。（5）堆排序 先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。 3.

8、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）将数据调整为堆的函数void adjust(int,int);/*将数据调整为堆树*/3.4主要函数声明插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。void insertio

9、n_sort(int data,int size)/*插入排序*/int base,compare,temp,i,j=0; for(base=1;base0 & datacompare-1temp) datacompare=datacompare-1; compare-; datacompare=temp; printf(第%d 趟排序: ,j); for(i=0;isize;i+) printf(%d ,datai); printf(n); printf(n最终排序结果:);for(i=0;i0)for(i=incr+1;i0) if(datajdataj+incr)/*比较每部分的数据大小

10、顺序不对则交换*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr;else j=0;num+;printf(n第%d 趟排序:,num);for(k=1;ksize;k+) printf(%d ,datak);incr=incr/2;printf(n最终排序结果：);for(i=1;isize;i+) printf(%d ,datai);printf(n);冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。void bubble_so

11、rt(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;isize-1;i+) flag=0; for(j=0;jdataj+1) flag=1; temp=dataj; dataj=dataj+1; dataj+1=temp; num+; printf(n第%d趟排序：,num); for(k=0;ksize;k+) printf(%d ,datak); printf(n); printf(n最终排序结果：);for(i=0;isize;i+) printf(%d ,datai); printf(n); if(flag!

12、=1) break; 选择排序选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。void select_sort(int data,int size)/*选择排序*/int base,compare,min,temp,i,num=0; for(base=0;basesize-1;base+)/*将目前数据与后面数据中最小的对调*/ min=base; for(compare=base+1;comparesize;compare+) if(datacomparedatamin) min=compare; temp=datamin;

13、 datamin=database; database=temp; num+; printf(第%d趟排序：,num); for(i=0;isize;i+) printf(%d ,datai); printf(n); printf(n最终排序结果：);for(i=0;isize;i+) printf(%d ,datai); printf(n);3.5主要变量说明Int data :整型数组，用于储存序列 Int size:整型变量，用于记录序列长度 Int temp:整型变量，用于交换元素 Int m,n,k,i,j,num:一般整型变量四程序源代码*include void insertio

14、n_sort(int,int);/*插入排序*/void shell_sort(int,int);/*希尔排序*/void bubble_sort(int,int);/*冒泡排序*/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 & datacompare-1temp) datacompare=datacompare-1; co

15、mpare-; datacompare=temp; printf(第%d 趟排序: ,j); for(i=0;isize;i+) printf(%d ,datai); printf(n); printf(n最终排序结果:); for(i=0;i0) for(i=incr+1;i0) if(datajdataj+incr)/*比较每部分的数据大小顺序不对则交换*/ temp=dataj; dataj=dataj+incr; dataj+incr=temp; j=j-incr; else j=0; num+; printf(n第%d 趟排序:,num); for(k=1;ksize;k+) pri

16、ntf(%d ,datak); incr=incr/2; printf(n最终排序结果：); for(i=1;isize;i+) printf(%d ,datai); printf(n);void bubble_sort(int data,int size)/*冒泡排序*/int i,j,flag,k,temp,num=0; for(i=0;isize-1;i+) flag=0; for(j=0;jdataj+1) flag=1; temp=dataj; dataj=dataj+1; dataj+1=temp; num+; printf(n第%d趟排序：,num); for(k=0;ksize

17、;k+) printf(%d ,datak); printf(n); printf(n最终排序结果：); for(i=0;isize;i+) printf(%d ,datai); printf(n); if(flag!=1) break; void select_sort(int data,int size)/*选择排序*/int base,compare,min,temp,i,num=0; for(base=0;basesize-1;base+)/*将目前数据与后面数据中最小的对调*/ min=base; for(compare=base+1;comparesize;compare+) if

18、(datacomparedatamin) min=compare; temp=datamin; datamin=database; database=temp; num+; printf(第%d趟排序：,num); for(i=0;isize;i+) printf(%d ,datai); printf(n); printf(n最终排序结果：); for(i=0;isize;i+) printf(%d ,datai); printf(n);void adjust(int i,int n)/*将数据调整为堆树*/int data20,j,k,done=0; k=datai; j=2*i; whil

19、e(j=n)&(done=0) if(jn)&(dataj=dataj)done=1; else dataj/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请输入初始关键字（输入0结束）:n); do scanf(%d,&datasize); m+; while(datasize+!=0); printf(你输入的初始关键字为：);for(j=0;jm-1;j+)printf(%d ,dataj);printf(n排序方法：n);printf(n1、插入排序

20、n);printf(n2、希尔排序n);printf(n3、冒泡排序n);printf(n4、选择排序n);printf(n5、堆排序n);printf(n请选择排序方法：n);scanf(%d,&num);switch(num)case 1: printf(*插入排序*n); for(i=0;i50;i+)printf(-);printf(n); insertion_sort(data,-size); for(i=0;i50;i+)printf(-);printf(n); break;case 2:printf(*希尔排序*n);for(m=0;m50;m+)printf(-); shell

21、_sort(data,-size);for(i=0;i50;i+)printf(-);printf(n); break;case 3:printf(*冒泡排序*n);for(i=0;i50;i+)printf(-);printf(n); bubble_sort(data,-size); for(i=0;i50;i+)printf(-);printf(n); break;case 4:printf(*选择排序*n);for(i=0;i50;i+)printf(-);printf(n); select_sort(data,-size); for(i=0;i50;i+)printf(-);print

22、f(n); break;case 5:size=size-1;printf(*堆排序*n);for(i=0;i0;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;ksize;k+) printf(%d ,datak); pr

23、intf(n); for(i=0;i50;i+)printf(-);printf(n); break;五运行结果与分析（测试）（1）程序开始如图4.1图4.1 程序开始界面（2）输入关键字以后如图4.2图4.2 输入关键字以后界面（3）在输入关键字后的排序方法选择如图4.3图4.3在输入关键字后的排序方法选择界面（4）输入1，输出插入排序结果如图4.4图4.4 插入排序输出结果界面（5）输入2，输出希尔排序结果如图4.5图4.5希尔排序输出结果界面（6）输入3，输出冒泡排序结果如图4.6图4.6 冒泡排序输出结果（7）输入4，输出选择排序结果如图4.7图4.7选择排序输出结果界面 （8）输入5

24、，输出堆排序结果如图4.8图4.7 堆排序输出结果界面六总结（收获与体会）做这个课程设计，我收获了很多。在课程设计中我遇到了一些平时做作业所没遇到、也不可能遇到的问题。在做课程设计的过程中，加深了对书本知识的理解，同时也培养了自己的动手能力。因为上学期做过一次C语言的课程设计，对于课程设计有了一些经验了吧，从总体上来说还算比较顺利，只是之前忙于准备考试，之后做课程设计感觉时间有点紧，应该是我在时间安排上有点问题吧。这次课程设计，是将这一学期学到的论知识用于了实践，在我在实践中得到了很多经验。在看到在自己付出了努力所做出来的成果时，我感到非常的欣慰。最后我还要感谢我的指导老师，感谢在我遇到问题时帮我解决问题的同学，没有你们的帮助我是不可能做好的。我以后还要更加努力，不辜负老师与家人的期望。七参考文献1 数据结构（C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112 数据结构题集（C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.113 数据结构与算法徐绪松 高等教育出版社 2004.74 数据结构殷人昆 编著 清华大学出版社 2001.115 数据结构与程序设计（C语言描述第2版）清华大学出版社 1998.7. v