基于选择排序方法的类模板设计与实现C++课程设计

《基于选择排序方法的类模板设计与实现C++课程设计》由会员分享，可在线阅读，更多相关《基于选择排序方法的类模板设计与实现C++课程设计（26页珍藏版）》请在装配图网上搜索。

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

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

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

4、5 基于 MFC 的应用程序.135.1 基于 MFC 的应用程序设计.135.1.1 MFC 程序界面设计.135.1.2 MFC 程序代码设计.155.2 基于 MFC 的应用程序测试.21结 论.22参考文献.2311 需求分析（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=

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

7、叉树的第 i 个结点的左子树，右子树已是堆，则对第 i 个结点进行调整时，需要将 r2i.key 与 r2i+1.key 之中的最大者与 ri.key 进行比较，若 ri.key 较小则与之交换。这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。如此反复，直到将以第 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=

8、array1; array1=t; AdjustTree(array,1,i-1); 33 类设计从上面的算法分析可以看到，本设计面临的问题的关键是类模板。可以定义一个模板类 sort，模板类 sort 功能有输入，输出数组，用三种方法对数组进行排序。从问题的需要来看，在模板类中定义三个成员函数。成员函数SelectSort（）对数组进行简单选择排序，成员函数 tree_select_sort（）对数组进行树形选择排序，成员函数 HeapSort（）对数组进行堆排序。成员函数AdjustTree（）通过始建和调整堆辅助堆排序，而成员函数 write( ) 和 print( ) 输入输出数组。主

9、函数中应用 if( ) 判断语句确定数组数据类型，swich（）语句选择使用的排序方法。定义了两个对象分别是整型和字符型的。类用 template 限定，其中的数据类型用 type 代替，所有的成员函数都用 template 修饰，使之能适用于多种数据类型。4 基于控制台的应用程序整个程序只用一个独立的文档，文件中包含一个模板类，主函数中定义多个对象来实现调用三个成员函数对数组进行简单选择排序，树形选择排序，堆排序这三种排序，在此定义了三个对象分别是整型、字符型和浮点型的。4.1 类的接口设计#include#include#include#include#define num 50#defi

10、ne M 504#define MIN_VALUE -10000templateclass Sort public: /外部接口 void AdjustTree(Type ar,int n,int k); void write(); void SelectSort(Type ar); void tree_select_sort(Type arr,int n); void HeapSort(Type ar); void print(); int len; Type arraynum; ;在此定义了模板类，类中所有的成员函数和成员变量均定义为 public 的公有类型，是类的对外接口，数据类型用

11、type 代替。成员函数在类中只有函数类型，函数名，参数，对函数进行内部声明，函数体在类体外定义4.2 类的实现/简单选择排序template void Sort:SelectSort(Type ar) int i,j; Type t; for(i=1;ilen;i+) for(j=i+1;jarrayj) t=arrayi;arrayi=arrayj;arrayj=t;5template void Sort:tree_select_sort(Type arr,int n) /树形选择排序Type treeM; / 树 int baseSize; / 当 n 是 2 的幂次时,baseSize

12、 是 n, 当 n 不是时,baseSize 是大于 n 的最小的 2 的幂次 / 就是构造成满二叉树的最下层的大小，即叶子数 int i;Type max; / 最大值 int maxIndex; / 最大数的下标 int treeSize; / 最终这棵树会达到的大小 baseSize = 1;while (baseSize n) baseSize *= 2;treeSize = baseSize * 2 - 1;/满二叉树的所有结点个数等于叶子数的 2 倍减一for (i = 0;i n;i+) / 从数组的后面部分开始填充, 不使用 tree0 treetreeSize - i = a

13、rri;for (;i 1;i -= 2)6/ 以 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) ma

14、xIndex-; treemaxIndex = MIN_VALUE; / 沿着叶子上的结点到根的路径更新 while (maxIndex 1) / 当结点还有父结点时 if (maxIndex % 2 = 0) / 如果值为最大值的结点是左子结点 / 用子结点中较大值代替父结点 treemaxIndex / 2 = (treemaxIndex treemaxIndex + 1 ? treemaxIndex : treemaxIndex + 1); else / 如果不是左子结点 7 / 用子结点中较大值代替父结点 treemaxIndex / 2 = (treemaxIndex treemax

15、Index - 1 ? treemaxIndex : treemaxIndex - 1); maxIndex /= 2; / 继续处理父结点 template void Sort:AdjustTree(Type ar,int k,int n) /调整堆 int i,j; i=k; j=2*i; /arrauj是 arrayi的左孩子 Type temp=arrayi; while(j=n) if(jn&arrayjarrayj+1) /若有孩子较大，把 j 指向右孩子 j=j+1; if(temparrayj) arrayi=arrayj; /arrayj调整到双亲结点 i=j; j=2*i;

16、 else break; arrayi=temp;template 8void Sort:HeapSort(Type ar) /堆排序 int i; Type t; for(i=len/2;i=1;i-) /循环建立初始堆 AdjustTree(array,i,len); for(i=len;i=2;i-) /进行 n-1 次循环，完成堆排序 t=arrayi; arrayi=array1; array1=t; AdjustTree(array,1,i-1); templatevoid Sort:write() /输入数组int i,l;printf(请输入数组长度:);scanf(%d,&l

17、);len=l;printf(请输入数组元素:n);for(i=1;iarrayi;templatevoid Sort:print() /输出数组int i; printf(排序后的数组为:n); for(i=1;i=len;i+)9 coutarrayi ; coutendl;在类的成员函数实现过程中，系统会自动为类产生构造函数，类的构造函数自动调用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成。成员函数对成员变量进行操作，实现排序功能，通过 for( ) 循环，实现输入输出数组元素的功能。4.3 主函数设计在程序的主函数部分，选择了分别以 int、char 和 float 型

18、为数据类型的对象作为实际例子来验证算法。首先，选择数据类型；然后，通过 write( ) 函数对成员变量数组 array 进行赋值，通过 swich（）语句选择排序方式，用对象调用对应的成员函数实现数组排序；最后，通过 print（）函数输出排序后的结果。void main() /主函数 int i,j=1; Sort s; Sort p; Sort z; cout选择输入类型:1.int 2.char 3.floati;if(i=1) s.write(); cout请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序i; switch(i) 10 case 1:s.SelectSo

19、rt(s.array);break; case 2:s.tree_select_sort(s.array,s.len+1);break; case 3:s.HeapSort(s.array);break; default:break; s.print();else if(i=2) p.write(); cout请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序i; switch(i) case 1:p.SelectSort(p.array);break; case 2:p.tree_select_sort(p.array,p.len+1);break; case 3:p.HeapS

20、ort(p.array);break; default:break; p.print();else if(i=3) z.write(); cout请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序i; switch(i) case 1:z.SelectSort(z.array);break; case 2:z.tree_select_sort(z.array,z.len+1);break; case 3:z.HeapSort(z.array);break; default:break; 11 z.print();4.4 基于控制台的应用程序测试基于控制台的应用程序测试（1）用简单选

21、择排序进行 int 类型的排序图 1（2） 用树形选择排序进行 char 类型的排序图 2 12（3）用堆排序进行 float 类型的排序图 35 基于 MFC 的应用程序MFC 的图形界面程序设计可在上述类设计的基础上进行改造，MFC 的图形界面程序与 DOS 界面程序的主要不同点是：MFC 图形界面程序与 DOS 界面程序的输入输出方式不同，DOS 界面程序采用字符交互式实现数据输入输出，主要通过 cin，cout 等 I/O 流实现，而 MFC 的图形程序界面采用标准 Windows窗口和控件实现输入输出，因此必须在 MFC 类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入

22、输出改造来完成。5.1.1 MFC 程序界面设计首先在 VC 中建立 MFC AppWizard（exe）工程，名称为 1203060128，并在向导的 Step1 中选择基本对话框，即建立基于对话框的应用程序，如下图 4、图 5 所示。13图 4 建立 MFC AppWizard（exe）工程14图 5 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 6 所示。图 6 选择排序方法的实现界面设计图 3 所示的界面中包含了 2 个 Static Text 控件，3 个 Button 控件，和 10 个 Edit Box 控件, 控件的基本信息列表如下表 1 所

23、示。表 1 控件基本信息输入前Static TextIDC_STATIC输入后IDC_BUTTON_1简单选择排序IDC_BUTTON_2树形选择排序BottonIDC_BUTTON_3堆排序IDC_EDIT_m1 IDC_EDIT_m5输入的 5 个元素Edit BoxIDC_EDIT_m6 IDC_EDIT_m10输出的 5 个元素5.1.2 MFC 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为 10 个 Edit 15Box 控件建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选择 Member Variabl

24、es 选项卡，可显示成员变量设置界面，如图 7 所示。图 7 成员变量设置界面通过该界面设置与 10 个 Edit Box 控件对应的成员变量，具体如表 2 所示。表 2 控件基本信息控件 ID成员变量类型成员变量名称IDC_EDIT_m1 IDC_EDIT_m5Intm_1m_5IDC_EDIT_m6 IDC_EDITm_10Intm_6m_10下面是编写代码的重要阶段（1）简单选择排序int a5;UpdateData(true);a0=m_l1;16a1=m_l2;a2=m_l3;a3=m_l4;a4=m_l5; int i,j,k; int temp; int len=5; for(i

25、=0;i=len;i+) k=i; for(j=i+1;jaj) k=j; if(k!=i) temp=ak; ak=ai; ai=temp; m_l6=a0;m_l7=a1;m_l8=a2;m_l9=a3;m_l10=a4;UpdateData(false);（2）树形选择排序 int a5; UpdateData(true);17 a0=m_l1; a1=m_l2; a2=m_l3; a3=m_l4; a4=m_l5; char tree50; /树 int max;/最大值 int baseSize; int i; int maxIndex;/最大值的下标 int treeSize;/最

26、终这棵树会达到的大小int len=5;int MIN_VALUE=0; baseSize=1; while(baseSizelen)baseSize*=2;treeSize=baseSize*2-1;for(i=0;ilen;i+)treetreeSize-i=ai; for(;i1;i-=2)treei/2=(treeitreei-1?treei:treei-1);18 len=len-1; while(len!=-1)max=tree1; alen-=max; maxIndex=treeSize;while(treemaxIndex!=max) maxIndex-; treemaxInd

27、ex=MIN_VALUE; while(maxIndex1)if(maxIndex%2=0)treemaxIndex/2=(treemaxIndextreemaxIndex+1?treemaxIndex:treemaxIndex+1);elsetreemaxIndex/2=(treemaxIndextreemaxIndex-1?treemaxIndex:treemaxIndex-1);maxIndex/=2;m_l6=a0;m_l7=a1;m_l8=a2;m_l9=a3;m_l10=a4;UpdateData(false);19（3）堆排序int a5; UpdateData(true);a0

28、=m_l1;a1=m_l2;a2=m_l3;a3=m_l4;a4=m_l5; int i=0,j,temp;int p=10;int q=10;int len=5; j=2*p; while(j=q)/堆顶元素下筛 if(jq)&(ajaj)break; ap=aj;p=j; j*=2; ap=temp; temp=a1; a1=ai; ai=temp;m_l6=a0;m_l7=a1;m_l8=a2;m_l9=a3;m_l10=a4;20UpdateData(false);5.2 基于 MFC 的应用程序测试运行程序后，首先出现的界面如图 8 所示。图 8 程序初始运行界面单击简单选择排序按钮

29、后，可将输入前的字符进行排序，如图 6 所示。21图 9 排序后的界面 结 论本次课程设计，在 DOS 界面中，先用 templateclass 定义 sort模板类，类中数据类型用 type 代替，我定义了三个成员函数，SelectSort（） ，tree_select_sort（） ，HeapSort（） ，分别实现对成员变量 array 数组的简单选择排序，树形选择排序，堆排序，又定义了两个成员函数 write( ) 和 print( )，分别输入和输出成员变量，根据模板类的定义要求，成员函数都用 template修饰，使之能适用于多种数据类型，而不是局限于一种。我将函数的声明与定义分离

30、，在类中声明函数，在类体外定义函数，是程序清晰易读。通过努力，程序正确运行，并得到了实验要求的结果，说明本次程序实现了其主要功能。而我通过本次实验学到了如何定义模板类，如何使用多种方法为数组排序。MFC 程序与 DOS 界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面各种排序的设计等问题上，而这些问题在 DOS 界面程序中是不存在的。本次课程设计作为编写 Windows 程序的22初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，编写出一个基于 Windows 界面的程序时，所获得的满足程度远远大于简单的 D

31、OS 界面程序，本次编写的 MFC 程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，主要包括以下几个方面。（1）本次的 MFC 程序只能对整型数组排序，如果改为 char 型、float 型的，需从属性的对话框中重复选择。这样确实很不实用。作者希望选择的类型可以自主进行转换 （2）将类的定义与实现放在同一个头文件中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件。参考文献1 谭浩强. C 程序设计. 北京:清华大学出版社,19912 郑振洁 C+程序设计. 北京:人民邮电出版社,20053 柴欣.C/ C+程序设计. 河北大学出版社,20024 余苏宁、王明福.C+程序设计. 北京:高等教育出版社,20035 李云清、杨庆红、揭安全.数据结构m .人民邮电大学出版社,2004