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

《2022年基于选择排序方法的类模板设计与实现C课程设计 .pdf》由会员分享，可在线阅读，更多相关《2022年基于选择排序方法的类模板设计与实现C课程设计 .pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、选择排序和堆排序.本文采用C+语言实现了选择排序功能，设计了模板类，实现了int 型 float 型和 char型数组地精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 26 页排序，设计了简单选择排序、树形选择排序和堆排序地三个函数体，采用Visual C+ 6.0 地控制台工程和MFC 工程分别实现了各类型数组地排序，通过对两种程序地测试结果表明：简单选择排序是选择排序地基础，而树形选择排序和堆排序是简单选择排序地改进.关键词：模板类；简单选择排序；树形选择排序；堆排序；控制台工程；MFC 工程 .精选学习资料 - - - - - -

4、 - - - 名师归纳总结 - - - - - - -第 3 页，共 26 页目 录1 需求分析 . 12 算法基本原理 . 13 类设计 . 34 基于控制台地应用程序 . 34.1 类地接口设计 . 34.2 类地实现 . 44.3 主函数设计 . 94.4 基于控制台地应用程序测试 . 105 基于 MFC 地应用程序 . 125.1 基于 MFC 地应用程序设计 . 错误！未定义书签。5.1.1 MFC 程序界面设计 . 135.1.2 MFC 程序代码设计 . 145.2基于 MFC 地应用程序测试 . 21结 论 . 22参考文献 . 23精选学习资料 - - - - - - -

5、- - 名师归纳总结 - - - - - - -第 4 页，共 26 页1 需求分析（1）当进行数据处理时,经常遇到需要进行查找操作,通常希望待处理地数据按关键字大小有序排序,因为这样就可以采用查找效率较高地查找算法.（2）对有序地顺序表可以采用查找效率较高地折半查找算法，而对无序地顺序表只能采用顺序查找算法.由此可见排序是计算机程序设计中一种基础性操作，研究和掌握各种排序方法是非常重要地.（3）排序算法对于计算机信息处理很重要，一个好地排序不仅可以使信息查找地效率提高，而且直接影响着计算机地工作效率.本实验题目为基于选择排序方法地类模板设计与实现，要求建立一维数组数据结构地模板类，使一维数组

6、中地数据元素可以是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 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - -

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

8、树已是堆，则对第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=array1 。 array1

9、=t 。 AdjustTree(array,1,i-1) 。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 26 页3 类设计从上面地算法分析可以看到，本设计面临地问题地关键是类模板.可以定义一个模板类sort，模板类sort 功能有输入，输出数组，用三种方法对数组进行排序.从问题地需要来看，在模板类中定义三个成员函数.成员函数SelectSort（）对数组进行简单选择排序，成员函数tree_select_sort（）对数组进行树形选择排序，成员函数HeapSort（）对数组进行堆排序.成员函数AdjustTree（）通过始建和调整堆

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

11、de#include#include#define num 50#define M 50#define MIN_V ALUE -10000templateclass Sort public: / 外部接口精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 26 页 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 a

12、r) 。 void print() 。 int len。 Type arraynum 。在此定义了模板类，类中所有地成员函数和成员变量均定义为public 地公有类型，是类地对外接口，数据类型用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 。templat

13、e void Sort:tree_select_sort(Type arr,int n) /树形选择排序Type treeM 。 / 树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 26 页int baseSize。 / 当 n 是 2 地幂次时 ,baseSize是 n, 当 n 不是时 ,baseSize是大于 n 地最小地 2 地幂次/ 就是构造成满二叉树地最下层地大小，即叶子数int i。Type max。 / 最大值int maxIndex 。 / 最大数地下标int treeSize。 / 最终这棵树会达到地大小baseS

14、ize = 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)。精选学习资料 - - - - - -

15、- - - 名师归纳总结 - - - - - - -第 9 页，共 26 页n = n - 1。 /此时地 n 表示当前tree1应该放到arr 中地位置/ 不断把树中值为最大值地结点移走,直到 n地值为 -1 while (n != -1) max = tree1 。 arrn- = max 。 maxIndex = treeSize。/ 在叶子上找到最大值对应地下标 while (treemaxIndex != max) maxIndex- 。 treemaxIndex = MIN_V ALUE 。 / 沿着叶子上地结点到根地路径更新 while (maxIndex 1) / 当结点还有父

16、结点时 if (maxIndex % 2 = 0) / 如果值为最大值地结点是左子结点 / 用子结点中较大值代替父结点 treemaxIndex / 2 = (treemaxIndex treemaxIndex + 1 ? treemaxIndex : treemaxIndex + 1) 。 else / 如果不是左子结点 / 用子结点中较大值代替父结点 treemaxIndex / 2 = (treemaxIndex treemaxIndex - 1 ? treemaxIndex : treemaxIndex - 1) 。 maxIndex /= 2 。 / 继续处理父结点精选学习资料 -

17、- - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 26 页 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 。 else break。

18、 arrayi=temp 。template void Sort:HeapSort(Type ar) / 堆排序 int i 。 Type t。 for(i=len/2 。i=1。i-) / 循环建立初始堆精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 26 页 AdjustTree(array,i,len) 。 for(i=len 。i=2。i-) / 进行 n-1 次循环，完成堆排序 t=arrayi 。 arrayi=array1 。 array1=t 。 AdjustTree(array,1,i-1) 。 templatevo

19、id Sort:write() / 输入数组int i,l 。printf( 请输入数组长度:)。scanf(%d,&l) 。len=l。printf( 请输入数组元素:n)。for(i=1 。iarrayi 。templatevoid Sort:print() / 输出数组int i 。 printf( 排序后地数组为:n)。 for(i=1 。i=len 。i+) coutarrayi 。 coutendl。在类地成员函数实现过程中，系统会自动为类产生构造函数，类地构造函数自动调精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 26

20、 页用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成.成员函数对成员变量进行操作，实现排序功能，通过for( ) 循环，实现输入输出数组元素地功能 .4.3 主函数设计在程序地主函数部分，选择了分别以int、 char和 float 型为数据类型地对象作为实际例子来验证算法.首先，选择数据类型；然后，通过write( ) 函数对成员变量数组array 进行赋值，通过swich（）语句选择排序方式，用对象调用对应地成员函数实现数组排序；最后，通过print（）函数输出排序后地结果.void main() / 主函数 int i,j=1 。 Sort s。 Sort p。 Sort

21、z 。 cout 选择输入类型:1.int 2.char 3.floati 。if(i=1) s.write() 。 cout 请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序 i 。 switch(i) case 1:s.SelectSort(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)精选学习资料 - - - - - - - - - 名师归纳总

22、结 - - - - - - -第 13 页，共 26 页 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.HeapSort(p.array)。break。 default:break。 p.print() 。else if(i=3) z.write() 。 cout 请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序

23、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。 z.print() 。 4.4 基于控制台地应用程序测试（1）用简单选择排序进行int 类型地排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 26 页图 1（2）用树形选择排序进行char类型地排序图 2 （3）用堆排序进行float 类

24、型地排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 26 页图 35 基于 MFC 地应用程序MFC 地图形界面程序设计可在上述类设计地基础上进行改造，MFC 地图形界面程序与 DOS 界面程序地主要不同点是：MFC 图形界面程序与DOS 界面程序地输入输出方式不同， DOS 界面程序采用字符交互式实现数据输入输出，主要通过cin，cout 等 I/O 流实现，而 MFC 地图形程序界面采用标准Windows 窗口和控件实现输入输出，因此必须在MFC 类地框架下加入上面所设计地矩阵和方程组类，并通过图形界面地输入输出改造来完成.5

25、.1.1 MFC 程序界面设计首先在VC 中建立MFC AppWizard （ exe）工程，名称为1203060128，并在向导地Step1中选择基本对话框，即建立基于对话框地应用程序，如下图4、图 5 所示 .精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 26 页图 4 建立 MFC AppWizard （ exe）工程图 5 建立基于对话框地应用程序将对话框资源中地默认对话框利用工具箱改造成如下界面，如图6 所示 .精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 26

26、 页图 6 选择排序方法地实现界面设计图 3 所示地界面中包含了2 个 Static Text 控件， 3 个 Button 控件，和 10 个 Edit Box 控件 , 控件地基本信息列表如下表1 所示 .表 1 控件基本信息Static Text IDC_STATIC 输入前输入后Botton IDC_BUTTON_1 简单选择排序IDC_BUTTON_2 树形选择排序IDC_BUTTON_3 堆排序Edit Box IDC_EDIT_m1 IDC_EDIT_m5 输入地 5 个元素IDC_EDIT_m6 IDC_EDIT_m10 输出地 5 个元素5.1.2 MFC 程序代码设计为了能

27、够将对话框界面上地控件能够与代码联系起来，需要为10 个 Edit Box 控件建立Member Variables，按 Ctrl+w 键进入MFC ClassWizard 界面，选择Member Variables 选项卡，可显示成员变量设置界面，如图7 所示 .精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 26 页图 7 成员变量设置界面通过该界面设置与10 个 Edit Box 控件对应地成员变量，具体如表2所示 .表 2 控件基本信息控件 ID 成员变量类型成员变量名称IDC_EDIT_m1 IDC_EDIT_m5 Int

28、m_1m_5 IDC_EDIT_m6 IDC_EDITm_10 Int m_6m_10 下面是编写代码地重要阶段（1）简单选择排序int a5 。UpdateData(true) 。a0=m_l1 。a1=m_l2 。a2=m_l3 。a3=m_l4 。a4=m_l5 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 26 页 int i,j,k 。 int temp。 int len=5 。 for(i=0 。i=len 。i+) k=i 。 for(j=i+1 。jaj) k=j 。 if(k!=i) temp=ak 。 ak=a

29、i 。 ai=temp 。 m_l6=a0 。m_l7=a1 。m_l8=a2 。m_l9=a3 。m_l10=a4 。UpdateData(false) 。（2）树形选择排序 int a5 。 UpdateData(true)。 a0=m_l1 。 a1=m_l2 。 a2=m_l3 。 a3=m_l4 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 26 页 a4=m_l5 。 char tree50 。 /树 int max 。/最大值 int baseSize。 int i 。 int maxIndex 。/最大值地下标 i

30、nt treeSize。/最终这棵树会达到地大小int len=5 。int MIN_V ALUE=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)。 len=len-1 。 while(len!=-1) max=tree1 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21

31、页，共 26 页 alen-=max 。 maxIndex=treeSize 。while(treemaxIndex!=max) maxIndex- 。 treemaxIndex=MIN_VALUE 。 while(maxIndex1) if(maxIndex%2=0) treemaxIndex/2=(treemaxIndextreemaxIndex+1?treemaxIndex:treemaxIndex+1)。 else treemaxIndex/2=(treemaxIndextreemaxIndex-1?treemaxIndex:treemaxIndex-1) 。 maxIndex/=2

32、。 m_l6=a0 。m_l7=a1 。m_l8=a2 。m_l9=a3 。m_l10=a4 。UpdateData(false) 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 26 页（3）堆排序int a5 。 UpdateData(true) 。a0=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 。

33、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 。UpdateData(false) 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 26 页5.2 基于 MFC 地应用程序测试运行程序后，首先出现地界面如图8 所示 .图 8 程序初始运行界面单击简单选择排序按钮后，可将输入前地字符进行排序，如图6 所示 .图 9 排序后地界面精选学习资料 - - - - - - - - - 名

34、师归纳总结 - - - - - - -第 24 页，共 26 页结 论本次课程设计，在DOS 界面中，先用templateclass 定义 sort 模板类，类中数据类型用type 代替，我定义了三个成员函数，SelectSort（）， tree_select_sort（），HeapSort（），分别实现对成员变量array 数组地简单选择排序，树形选择排序，堆排序，又定义了两个成员函数write( ) 和 print( ) ，分别输入和输出成员变量，根据模板类地定义要求，成员函数都用template修饰，使之能适用于多种数据类型，而不是局限于一种 .我将函数地声明与定义分离，在类中声明函数，

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

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