基于选择排序方法的类模板设计与实现c++-毕设论文.doc

《基于选择排序方法的类模板设计与实现c++-毕设论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、成绩评定表学生姓名吴琼班级学号专业通信工程课程设计题目基于选择排序方法的类模板设计与实现评语组长签字：成绩日期20年月日课程设计任务书学院信息科学与工程专业通信工程学生姓名吴琼班级学号课程设计题目基于选择排序方法的类模板设计与实现实践教学要求与任务建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现选择类排序。主要完成如下功能：（1）实现数组数据的输入和输出；（2）实现简单选择排序功能；（3）实现树形选择排序功能；（4）实现堆排序功能；（5）将每种排序功能作为类的成员函数实现，编写主函数测试上

2、述排序功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要计算机中存储的数据，初始时没有任何排列规律，根据实际需求，经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。选择排序是排序法中很经典的算法，选择排序法可以分为简单选择排序、树形选择排序和堆排序。本文采用C++语言实现了选择排序功能，设计了模板类，实现了int型float型和char

3、型数组的排序，设计了简单选择排序、树形选择排序和堆排序的三个函数体，采用VisualC++6.0的控制台工程和MFC工程分别实现了各类型数组的排序，通过对两种程序的测试结果表明：简单选择排序是选择排序的基础，而树形选择排序和堆排序是简单选择排序的改进。关键词：模板类；简单选择排序；树形选择排序；堆排序；控制台工程；MFC工程。目录1需求分析12算法基本原理13类设计34基于控制台的应用程序34.1类的接口设计44.2类的实现44.3主函数设计94.4基于控制台的应用程序测试115基于MFC的应用程序135.1基于MFC的应用程序设计135.1.1MFC程序界

4、面设计135.1.2MFC程序代码设计155.2基于MFC的应用程序测试21结论22参考文献231需求分析（1）当进行数据处理时,经常遇到需要进行查找操作,通常希望待处理的数据按关键字大小有序排序,因为这样就可以采用查找效率较高的查找算法。（2）对有序的顺序表可以采用查找效率较高的折半查找算法，而对无序的顺序表只能采用顺序查找算法。由此可见排序是计算机程序设计中一种基础性操作，研究和掌握各种排序方法是非常重要的。（3）排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且直接影响着计算机的工作效率。本实验题目为基于选择排序方法的类模

5、板设计与实现，要求建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现选择类排序。因此实验采用类模板，可以对不同的数据类型的数据进行排序，并通过函数采用不同的方法进行排序。2算法基本原理（1）简单选择排序从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。//简单选择排序SelectSort(Typear[]){inti,j;Typet;for(i=1;iarray[j]){t=array[i];ar

6、ray[i]=array[j];array[j]=t;}}22（2）树形选择排序树形选择排序的基本思想：树形选择排序又称锦标赛排序（TournamentSort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。（3）．堆排序堆排序由建初始堆和调整堆两个过程组成。再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树，经调整根节点后使之成为堆的过程。建堆时一定要从最后一个非叶子结点开始。堆排序的关键是调整堆，建初始堆时也是要从最后一个非叶子结点开始向根结点方向

7、进行调整建堆。假设完全二叉树的第i个结点的左子树，右子树已是堆，则对第i个结点进行调整时，需要将r[2i].key与r[2i+1].key之中的最大者与r[i].key进行比较，若r[i].key较小则与之交换。这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。如此反复，直到将以第i个结点为根的子树构成堆为止。算法:HeapSort(Typear[]){inti;Typet;//循环建立初始堆for(i=len/2;i>=1;i--)AdjustTree(array,i,len);//进行n-1次循环，完成堆排序for(i=len;i>=

8、2;i--){t=array[i];array[i]