《基于选择排序方法的类模板设计与实现C++课程设计》由会员分享，可在线阅读，更多相关《基于选择排序方法的类模板设计与实现C++课程设计（26页珍藏版）》请在金锄头文库上搜索。
1、 成 绩 评 定 表学生姓名吴琼班级学号专 业通信工程课程设计题目基于选择排序方法的类模板设计与实现评语组长签字：成绩日期 20 年 月 日课程设计任务书学 院信息科学与工程专 业通信工程学生姓名吴琼班级学号课程设计题目基于选择排序方法的类模板设计与实现实践教学要求与任务建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char, int, float等多种数据类型，并对数组元素实现选择类排序。主要完成如下功能：（1）实现数组数据的输入和输出；（2）实现简单选择排序功能；（3）实现树形选择排序功能；（4）实现堆排序功能；（5）将每种排序功能作为类的成员函数实现，编写主函数测试上述排序功
2、能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘 要计算机中存储的数据，初始时没有任何排列规律，根据实际需求，经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。选择排序是排序法中很经典的算法，选择排序法可以分为简单选择排序、树形选择排序和堆排序。本文采用C+语言实现了选择排序功能，设计了模板类，实现了int型float型和char型数组的排序，设计了简单
3、选择排序、树形选择排序和堆排序的三个函数体，采用Visual C+ 6.0的控制台工程和MFC工程分别实现了各类型数组的排序，通过对两种程序的测试结果表明：简单选择排序是选择排序的基础，而树形选择排序和堆排序是简单选择排序的改进。关键词：模板类；简单选择排序；树形选择排序；堆排序；控制台工程；MFC工程。目 录1 需求分析12 算法基本原理13 类设计34 基于控制台的应用程序34.1 类的接口设计44.2 类的实现44.3 主函数设计94.4 基于控制台的应用程序测试115 基于MFC的应用程序135.1 基于MFC的应用程序设计135.1.1 MFC程序界面设计135.1.2 MFC程序代
4、码设计155.2基于MFC的应用程序测试21结 论22参考文献231 需求分析（1）当进行数据处理时,经常遇到需要进行查找操作,通常希望待处理的数据按关键字大小有序排序,因为这样就可以采用查找效率较高的查找算法。（2）对有序的顺序表可以采用查找效率较高的折半查找算法，而对无序的顺序表只能采用顺序查找算法。由此可见排序是计算机程序设计中一种基础性操作，研究和掌握各种排序方法是非常重要的。（3）排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息 查找的效率提高，而且直接影响着计算机的工作效率。本实验题目为基于选择排序方法的类模板设计与实现，要求建立一维数组数据结构的模板类，使一维数组中的
5、数据元素可以是char, int, float等多种数据类型，并对数组元素实现选择类排序。因此实验采用类模板，可以对不同的数据类型的数据进行排序，并通过函数采用不同的方法进行排序。2 算法基本原理（1）简单选择排序从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。/简单选择排序SelectSort(Type ar) int i,j; Type t; for(i=1;ilen;i+) for(j=i+1;jarrayj) t=arrayi;arrayi=arrayj;arrayj=t;（2）树形选择排序树形选择排序的基本思想：树形选择排序又称锦标赛排序（Tournament Sort
6、），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。 （3）堆排序堆排序由建初始堆和调整堆两个过程组成。再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树，经调整根节点后使之成为堆的过程。建堆时一定要从最后一个非叶子结点开始。堆排序的关键是调整堆，建初始堆时也是要从最后一个非叶子结点开始向根结点方向进行调整建堆。假设完全二叉树的第i个结点的左子树，右子树已是堆，则对第i个结点进行调整时，需要将r2i.key与r2i+1.key之中的最大者与ri.key进行比较，若ri.key较小则与之交换。
7、这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。如此反复，直到将以第i个结点为根的子树构成堆为止。算法:HeapSort(Type ar) int i; Type t; /循环建立初始堆for(i=len/2;i=1;i-) AdjustTree(array,i,len); /进行n-1次循环，完成堆排序for(i=len;i=2;i-) t=arrayi; arrayi=array1; array1=t; AdjustTree(array,1,i-1); 3 类设计从上面的算法分析可以看到，本设计面临的问题的关键是类模板。可以定义一个模板类sort，模板类sort功能有
8、输入，输出数组，用三种方法对数组进行排序。从问题的需要来看，在模板类中定义三个成员函数。成员函数SelectSort（）对数组进行简单选择排序，成员函数tree_select_sort（）对数组进行树形选择排序，成员函数HeapSort（）对数组进行堆排序。成员函数AdjustTree（）通过始建和调整堆辅助堆排序，而成员函数write( ) 和print( ) 输入输出数组。主函数中应用if( ) 判断语句确定数组数据类型，swich（）语句选择使用的排序方法。定义了两个对象分别是整型和字符型的。类用template 限定，其中的数据类型用type代替，所有的成员函数都用template 修
9、饰，使之能适用于多种数据类型。4 基于控制台的应用程序整个程序只用一个独立的文档，文件中包含一个模板类，主函数中定义多个对象来实现调用三个成员函数对数组进行简单选择排序，树形选择排序，堆排序这三种排序，在此定义了三个对象分别是整型、字符型和浮点型的。4.1 类的接口设计#include#include#include#include#define num 50#define M 50#define MIN_VALUE -10000templateclass Sort public: /外部接口 void AdjustTree(Type ar,int n,int k); void write()
10、; void SelectSort(Type ar); void tree_select_sort(Type arr,int n); void HeapSort(Type ar); void print(); int len; Type arraynum; ;在此定义了模板类，类中所有的成员函数和成员变量均定义为public的公有类型，是类的对外接口，数据类型用type代替。成员函数在类中只有函数类型，函数名，参数，对函数进行内部声明，函数体在类体外定义4.2 类的实现/简单选择排序template void Sort:SelectSort(Type ar) int i,j; Type t;
11、for(i=1;ilen;i+) for(j=i+1;jarrayj) t=arrayi;arrayi=arrayj;arrayj=t;template void Sort:tree_select_sort(Type arr,int n) /树形选择排序Type treeM; / 树 int baseSize; / 当n是2的幂次时,baseSize是n, 当n不是时,baseSize是大于n的最小的2的幂次 / 就是构造成满二叉树的最下层的大小，即叶子数 int i;Type max; / 最大值 int maxIndex; / 最大数的下标 int treeSize; / 最终这棵树会达到
12、的大小 baseSize = 1;while (baseSize n) baseSize *= 2;treeSize = baseSize * 2 - 1;/满二叉树的所有结点个数等于叶子数的2倍减一for (i = 0;i n;i+) / 从数组的后面部分开始填充, 不使用tree0 treetreeSize - i = arri;for (;i 1;i -= 2)/ 以arri和arri + 1为子结点的数的根是arri和arri + 1中的较大者 treei / 2 = (treei treei - 1 ? treei : treei - 1);n = n - 1; /此时的n表示当前tree1应该放到arr中的位置 / 不断把树中值为最大值的结点移走,直到n的值为-1 while (n != -1) max = tree1; arrn- = max; maxIndex = treeSize;/ 在叶子上找到最大值对应的下标 while (treemaxIndex != max) maxIndex-; treemaxIndex = MIN_VALUE; / 沿着叶子上的结点到根的路径更新 while (maxIndex 1) / 当结点还有父结点时 if (maxIndex % 2 = 0) / 如果值为最大值的结点是左子结点 / 用子结点中较大值代替父结点
