排序算法集成-杉杉

1、数 据 结 构课程设计说明书题 目排序算法集成学 号1376807439姓 名赵杉杉指导教师王丽颖日 期2015年6月28日内蒙古科技大学课程设计任务书课程名称数据结构与算法课程设计设计题目排序算法集成指导教师王丽颖时间2015.6.222015.7.2一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师

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

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

4、章 总体设计5第3章 抽象数据类型定义63.1 排序抽象数据类型的设计6第4章 详细设计74.1 工程视图74.2 类图视图74.3 函数的调用关系84.4 主程序流程图94.5 主要算法的流程图10第5章 测试16第6章 总结20附录：程序代码21第1章 需求分析排序算法集成：定义动态数组类（或类模板）以表示待排序数据，在此基础上实现多种排序算法。要求设计函数模板来实现下列排序算法：v 直接插入排序v 冒泡排序v 简单选择排序v 希尔排序v 快速排序v 堆排序 并设计主函数测试动态数组类（或类模板），测试各排序算法的函数模板。第2章 总体设计本系统是输入待排序的数据，通过人为的选择是利用哪种

5、排序进行运算，运算之后，将排好序的结果输出，并且可以进行多组数据的操作。系统功能希尔排序堆排序直接插入排序冒泡排序快速排序简单选择排序显示排序结果图2.1 主要设计思想流程图第3章 抽象数据类型定义定义格式如下：3.1 排序抽象数据类型的设计Class Sort基本操作：void intput()操作结果：初始化动态申请的数。int get_len()操作结果：返回申请数组的大小。void display()操作结果：排序菜单的显示。void sel_sort()操作结果：执行简单选择排序。void par_sort(int l,int r)初始条件：动态数组的第一个元素的下标，和最后一个元素

6、的下标。操作结果：执行快速排序。void bub_sort()操作结果：执行冒泡排序。void insert_sort()操作结果：执行插入排序。void xier_sort()操作结果：执行希尔排序。void heap_rebuild(int data,int root,int size)操作结果：建立堆。void heap_sort()操作结果：执行堆排序 ；第4章 详细设计4.1 工程视图图 4.1.1 源代码文件显示4.2 类图视图图 4.2.1 类图视图显示4.3 函数的调用关系Main()清屏clearOutput()Input()六种排序函数菜单显示图 4.3.1 函数调用关系4

7、.4 主程序流程图开始输入数据菜单显示排序选择简单选择排序堆排序快速排序冒泡排序直接插入排序希尔排序是否对其他数据排序 是结束图 4.4.1 主程序流程图4.5 主要算法的流程图i =0,datai+i < len- 1 是K=i , j = i+1j<len j+ 否 是dataj < datak 否 是K = jK=i 否b = datai,datai = datak ,datak = b 是结束图4.4.1选择排序流程图图 4.4.2 快速排序流程图i=0,datai+i < len -1j=i,j<len-1 是 否 是dataj+1<datajK=

8、dataj+1,dataj+1,dataj=k.结束图 4.4.3 冒泡排序流程图i=1,i<len i+ 否 是temp=data 是j<i 否 j+ 是datai<dataj 否 是K=i 是K<j K- 否 是datak = datak-1dataj = temp 结束 图4.4.4 直接插入排序流程图 图 4.4.5 希尔排序流程例图i=len-1i>=0 否 i- 是构建堆 j = 1j<=len 否temp=data0, data0=datalast, datalast=temp, heap_rebuild(data,0,last); 是 结束

9、图4.4.6 堆排序流程图第5章 测试图 5.1 开始界面图 5.2 输入数据及菜单显示图 5.3 简单选择排序结果显示图5.4 快速排序结果显示图5.5 冒泡排序结果显示图5.6 直接插入排序结果显示图5.7 希尔排序结果显示图5.8 堆排序结果显示第6章 总结经过了两个星期的课程设计，我体会颇多，学到很多东西。利用设计排序算法集成系统的机会，我加强了对数据结构的理解，复习了自己以前的知识，提高了逻辑思考能力。在这次课程设计中，我还懂得了做程序的一些比较重要的步骤，比如总体设计、程序模块设计、包括功能需求、用户界面设计、程序代码设计与分析、运行结果等。在课程设计中我遇到了一些平时做作业所没遇

10、到的问题。在做课程设计的过程中，加深了对书本知识的理解，同时也培养了自己的动手能力。因为上学期做过两次课程设计，对于课程设计有了一些经验了吧，从总体上来说还算比较顺利，只是之前忙于准备考试，之后做课程设计感觉时间有点紧，应该是我在时间安排上有点问题吧。这次课程设计，是将这一学期学到的论知识用于了实践，在我在实践中得到了很多经验。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。在看到在自己付出了努力所做出来的成果时，我感到非常的欣慰。最后我还要感谢我的指导老师，感谢在我遇到问题时

11、帮我解决问题的同学，没有你们的帮助我是不可能做好的。我以后还要更加努力，不辜负老师与家人的期望。从这段时间，我获得了知识，学到了研究的坚持与韧性，这不仅仅是交出了一份作业，还对自己有了新的认识，实在是难得的机遇与经历。附录：程序代码#include<iostream>#include<cstdlib>using namespace std;class Sortpublic:void input()int i,n;cout<<endl<<" 欢迎来到排序系统"cout<<endl<<""

12、;cout<<endl<<" 请输入申请数组的大小："cin>>n;len = n;data = new intn;for(i = 0;i<n;i+)cout<<" 请输入第"<<i+1<<"个数："cin>>datai;int get_len()return len;void output();void display();void sel_sort();/选择void par_sort(int l,int r); /快排void bub_so

13、rt(); /冒泡void insert_sort(); /插入排序void xier_sort();/希尔排序void heap_rebuild(int data,int root,int size); /堆得建立void heap_sort(); /堆排序private:int * data;int len;void Sort:sel_sort()int i,j,k,b;for(i=0;i<len-1;i+)k = i;for(j = i+1;j<len;j+)if(dataj<datak)k=j;if(k != i)b = datai;datai = datak;dat

14、ak = b;void Sort:par_sort(int l,int r)if (l< r) int i = l, j = r, x = datal;while (i < j)while(i < j && dataj>= x) / 从右向左找第一个小于x的数j-;if(i < j)datai+ = dataj;while(i < j && datai< x) / 从左向右找第一个大于等于x的数i+;if(i < j)dataj- = datai;datai = x; par_sort(l, i - 1); / 递

15、归调用par_sort(i + 1, r); void Sort:bub_sort()int i,j,k;for(i=0;i<len-1;i+)for(j=i;j<len-1;j+)if(dataj+1<dataj)k = dataj+1;dataj+1 = dataj;dataj = k;void Sort:insert_sort()int i,j,k;int temp;for(i=1;i<len;i+)temp=datai;for(j=0;j<i;j+)if(datai<dataj)for(k=i;k>j;k-)datak=datak-1;data

16、j=temp;void Sort:xier_sort()int j, temp,d;d = len / 2;while(d > 0)for ( int i = d; i < len; i+)temp = datai;j = i - d;while (j >= 0 && dataj>temp)dataj+d = dataj;j -= d;dataj + d = temp;d /= 2;void Sort:heap_rebuild(int data,int root,int size) int child=2*root+1; if(child<=siz

17、e-1) int rightChild=child+1; if(rightChild<=size-1) if(datachild<datarightChild) child=rightChild; if(dataroot<datachild) int temp=datachild; datachild=dataroot; dataroot=temp; heap_rebuild(data,child,size); void Sort:heap_sort()int i; for(i=len-1;i>=0;i-) heap_rebuild(data,i,len); int l

18、ast=len-1; for(int j=1;j<=len;j+,last-) int temp=data0; data0=datalast; datalast=temp; heap_rebuild(data,0,last); void Sort:output()int i;cout<<endl<<" 排序后的结果显示："for(i = 0;i < len; i+)cout<<" "<<datai;cout<<endl;void Sort:display()cout<<endl<<""cout<<endl<<" 1.简单选择排序"cout<<endl<<" 2.快速排序"cout<<endl<<" 3.冒泡排序"cout<<endl<<" 4.直接插入排序"cout<<endl<<" 5.希尔排序"cout<<endl<<" 6.堆排序&