2011级面向对象课设范例-通信工程要点.docx

《2011级面向对象课设范例-通信工程要点.docx》由会员分享，可在线阅读，更多相关《2011级面向对象课设范例-通信工程要点.docx（28页珍藏版）》请在三一文库上搜索。

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

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

3、种程序的测试结果表明：三种选择排序算法原理正确，两种程序均能正确对给定数组排序。关键词：模板类；简单选择排序；树形选择排序；堆排序； MFC 工程。1 需求分析 1.2 算法基本原理 1.3 类设计 3.4 基于控制台的应用程序 3.4.1 类的接口设计 4.4.2 类的实现4.4.3 主函数设计 9.4.4 基于控制台的应用程序测试1.15基于MFC勺应用程序135.1 基于MFC勺应用程序设计 135.1.1 MFC 程序界面设计135.1.2 MFC 程序代码设计155.2 基于MFC勺应用程序测试 21结论 2.2.参考文献 2.3.1 需求分析排序是现实世界中经常进行的一种操作。 计

4、算机中存储的数据， 初始时没有任何排列规律， 根据实际需求， 经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。本此实验题目为 基于选择排序方法的类模板设计与实现，要求建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char, int, float 等多种数据类型，并对数组元素实现选择类排序。 因此实验采用类模板， 可以对不同的数据类型的 数据进行排序，并通过函数采用不同的方法进行排序。2 算法基本原理( 1)简单选择排序从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。/简单选择排序SelectSort(Type ar)int i,j;Type t

5、;for(i=1;i<len;i+)for(j=i+1;j<=len;j+)if(arrayi>arrayj)t=arrayi;arrayi=arrayj;arrayj=t; ( 2)树形选择排序树形选择排序是一种借助于锦标赛方式的选择排序方法。锦标赛的本思想是通过分组淘汰决出冠军， 亚军一定是从输给冠军的选手中选手中产生， 季军定是从输给亚军的选手中产生的树形选择排序使用近似为完全二叉树的树形， 所有记录均为叶子节点从叶子结点开始， 通过两两比较填到树顶结点是对应关键字最小的记录， 然后将该叶子结点关键字置成最大关键字， 继续选出第二个最小值。如此重复进行，直到排序结束。(

6、 3) 堆排序堆排序就是利用堆的特性对记录序列进行排序的一种方法。具体做法是：先建一个大顶堆， 即先选的一个关键字最大的记录， 然后与序列中最后一个记录交换，再对序列中前n-1 条记录进行“筛选” ，重新将它调整成为一个大顶堆，再将堆顶记录和第 n-1 个记录交换。如此反复进行，直到所有记录有序为止。实质上， 堆排序由建初始堆和调整堆两个过程组成。再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树， 经调整根节点后使之成为堆的过程。 建堆时一定要从最后一个非叶子结点开始。堆排序的关键是调整堆， 建初始堆时也是要从最后一个非叶子结点开始向根结点方向进行调整建堆。 假设完全二叉树的第 i 个结点的

7、左子树， 右子树已是堆，则对第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

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

9、组数据类型，swich ()语句选择使用的排序方法。 定义了两个对象分别是整型和字符型的。类用template<class Type>限定，其中的数据类型用type代替，所有的成员 函数都用template<class Type>修饰，使之能适用于多种数据类型。4 基于控制台的应用程序整个程序只用一个独立的文档， 文件中包含一个模板类， 主函数中可以定义多个对象来实现调用成员函数对数组进行排序， 在此举例定义了两个对象分别是 整型和字符型的。4.1 类的接口设计#include<stdio.h>#include<string.h>#include

10、<stdlib.h>#include<iostream.h># define num 50# define M 50# define MIN_VALUE -10000template<class Type>class Sortpublic:/外部接口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;

11、Type arraynum;在此定义了模板类， 类中所有的成员函数和成员变量均定义为 public 的公有类型，是类的对外接口，数据类型用type代替。成员函数在类中只有函数类型，函数名，参数，对函数进行内部声明，函数体在类体外定义4.2 类的实现/简单选择排序template <class Type>void Sort<Type>:SelectSort(Type ar)int i,j;Type t;for(i=1;i<len;i+)for(j=i+1;j<=len;j+)if(arrayi>arrayj) t=arrayi;arrayi=arrayj

12、;arrayj=t;template <class Type>void Sort<Type>:tree_select_sort(Type arr,int n) /树形选择排序Type treeM; / 树int baseSize; / 当 n 是 2 的幕次时，baseSizeH n,当 n 不是时,baseSize!大于n 的最小的 2 的幂次/ 就是构造成满二叉树的最下层的大小，即叶子数int i;Type max; / 最大值int maxIndex; / 最大数的下标int treeSize; / 最终这棵树会达到的大小baseSize = 1;while (b

13、aseSize < n)baseSize *= 2;treeSize = baseSize * 2 - 1;/满二叉树的所有结点个数等于叶子数的/2倍减一for (i = 0;i < n;i+)/ 从数组的后面部分开始填充 , 不使用 tree0treetreeSize - i = arri;for (;i < baseSize;i+) / 用 MIN_VALUE 填充 tree,直到一共有 baseSize个treetreeSize - i = MIN_VALUE;/ 构造一棵树for (i = treeSize;i > 1;i -= 2)/ 以 arri 和 arr

14、i + 1 为子结点的数的根是arri 和 arri + 1 中的较大者treei / 2 = (treei > treei - 1 ? treei : treei - 1);n = n - 1; 此时的n表示当前tree1应该放到arr中的位置/ 不断把树中值为最大值的结点移走,直到 n 的值为 -1while (n != -1)max = tree1;arrn- = max;maxIndex = treeSize;/ 在叶子上找到最大值对应的下标while (treemaxIndex != max)maxIndex-;treemaxIndex = MIN_V ALUE;/ 沿着叶子上

15、的结点到根的路径更新while (maxIndex > 1) / 当结点还有父结点时if (maxIndex % 2 = 0) / 如果值为最大值的结点是左子结点/ 用子结点中较大值代替父结点treemaxIndex / 2 = (treemaxIndex > treemaxIndex + 1 treemaxIndex : treemaxIndex + 1);else / 如果不是左子结点/ 用子结点中较大值代替父结点treemaxIndex / 2 = (treemaxIndex > treemaxIndex - 1 treemaxIndex : treemaxIndex

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

17、2*i;else break;arrayi=temp;template <class Type>void Sort<Type>: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);template<class Type>void Sort<Ty

18、pe>:write() /输入数组int i,l;printf(" 请输入数组长度:");scanf("%d",&l);len=l;printf(" 请输入数组元素 :n");for(i=1;i<=l;i+)cin>>arrayi;template<class Type>void Sort<Type>:print()/输出数组int i;printf(" 排序后的数组为 :n");for(i=1;i<=len;i+)cout<<arrayi&

19、lt;<" "cout<<endl;在类的成员函数实现过程中， 系统会自动为类产生构造函数， 类的构造函数自动调用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成。成员函数对成员变量进行操作，实现排序功能，通过for( ) 循环，实现输入输出数组元素的功能。4.3 主函数设计void main()/主函数 int i,j=1;Sort<int> s;Sort<char> p;cout<<”选择输入类型:1 int 2 char"cin>>i;if(i=j)s.write();cout&l

20、t;<"请选择排序方式：1.简单选择排序2.树形选择排序3.堆排序”;cin>>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();elsep.write();cout<<"请选择排序方式：1.简单选择排序2.树形选择排序3.堆排序”;cin>>i;switch(i)case 1:p.

21、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();在程序的主函数部分，选择了分别以int和char型为数据类型的对象作为实际例子来验证算法。首先，选择数据类型，然后，通过write( ) 函数对成员变量数组array进行赋值，通过swich ()语句选择排序方式，用对象调用对应的成员函数实现数组排序，最后，通过print ()函数输出排序后的结果。4.4 基于控制台的应用程序测试图1

22、程序运行结果图1为简单选择排序运行结果，数据类型为int型图2程序运行结果图2为树形选择排序运行结果，数据类型为int型图3程序运行结果图3为堆排序运行结果，数据类型为int型。图4程序运行结果图4为简单选择排序运行结果，数据类型为char-o图5程序运行结果图5为树形选择排序运行结果，数据类型为char。图6程序运行结果图6为堆排序运行结果，数据类型为 char型5基于MFC勺应用程序MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程 序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，

23、主 要通过cin, cout等I/O流实现，而MFC的图形程序界面采用标准 Windows窗 口和控件实现输入输出，因此必须在 MFC类的框架下加入上面所设计的矩阵和 方程组类，并通过图形界面的输入输出改造来完成。5.1 基于MFC勺应用程序设计5.1.1 MFC程序界面设计首先在VC中建立 MFC AppWizard (exe)工程，名称为sort,并在向导的Step1中选择Dialog based,即建立基于对话框的应用程序，如下图 78所示图 7 建立 MFC AppWizard (exe)工程24图8建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图9所示

24、图9数组排序程序界面设计An ab| O lx 国国 EE图 奉mi O-i 隰 国展 B 脑目 H旧图9所示的界面中包含了 2个Static Text控件，3个Button控件，和8个EditBox控件，控件的基本信息列表如下表 1所示。表1控件基本信息控件类别控彳ID控件 Caption说明Static TextIDC_STATIC数组排序后数组BottonIDC_BUTTON_Read简单选择排序IDC_BUTTON_CALC树形选择排序IDC_BUTTON_Exit堆排序Edit BoxIDC EDIT A00IDC EDIT A07数组A的8个元素5.1.2 MFC程序代码设计为了能

25、够将对话框界面上的控件能够与代码联系起来，需要为8个Edit Box控件建立 Member Variables,按 Ctrl+w 键进入 MFC ClassWizard 界面，选择Member Variables选项卡，可显示成员变量设置界面，如图 10所示图10成员变量设置界面通过该界面设置与8个Edit Box控件对应的成员变量，具体如表 2所示表2控件基本信息控件ID成员变量类型成员变量名称IDC EDIT A00 IDC EDIT A33intm A00m A08DOS 界面的控制台应用程序的代码，并将其作必要的改写，具体程序如下：void CSortDlg:OnButton1()/

26、TODO: Add your control notification handler code here int a4;UpdateData(true);a0=m_A00;a1=m_A01;a2=m_A02;a3=m_A03;int i,j,k;int temp;int len=4;for(i=0;i<=len;i+) k=i;for(j=i+1;j<=len;j+)if(ak>aj)k=j;if(k!=i)temp=ak;ak=ai;ai=temp;m_A04=array 0;m_A05=array 1;m_A06=array 2;m_A07=array 3;Update

27、Data(false);void CSortDlg:OnButton2()/ TODO: Add your control notification handler code hereint a4;UpdateData(true);a0=m_A00;a1=m_A01;a2=m_A02;a3=m_A03;Type treeM; / 树int baseSize; / 当 n 是 2 的幕次时，baseSizeH n,当 n 不是时,baseSize!大于 n 的最小的 2 的幂次/ 就是构造成满二叉树的最下层的大小，即叶子数int i;Type max; / 最大值int maxIndex; /

28、最大数的下标int treeSize; / 最终这棵树会达到的大小baseSize = 1;while (baseSize < n)baseSize *= 2;treeSize = baseSize * 2 - 1;/满二叉树的所有结点个数等于叶子数的/2倍减一for (i = 0;i < n;i+)/ 从数组的后面部分开始填充 , 不使用 tree0treetreeSize - i = arri;for (;i < baseSize;i+) / 用 MIN_VALUE 填充 tree直到一共有 baseSize4V treetreeSize - i = MIN_VALUE;

29、/ 构造一棵树for (i = treeSize;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 的值为 -1while (n != -1)max = tree1;arrn- = max;maxIndex = treeSize;/ 在叶子上找到最大值对应的下标while (treemaxI

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

31、ndex > treemaxIndex - 1 treemaxIndex : treemaxIndex - 1);maxIndex /= 2; / 继续处理父结点m_A04=a 0;m_A05=a 1;m_A06=a 2;m_A07=a 3;UpdateData(false);void CSortDlg:OnButton3()/ TODO: Add your control notification handler code hereint a4;UpdateData(true);a 0=m_A00;a 1=m_A01;a2=m_A02;a 3=m_A03;int i,j;i=k;j=2

32、*i; /arrauj 是 arrayi 的左孩子Type temp=arrayi; while(j<=n)if(j<n&&arrayj<arrayj+1)/若有孩子较大，把j 指向右孩子j=j+1;if(temp<arrayj)arrayi=arrayj; /arrayj 调整到双亲结点i=j;j=2*i;else break;arrayi=temp;Type t;for(i=len/2;i>=1;i-)/循环建立初始堆AdjustTree(array,i,len);for(i=len;i>=2;i-)/进行n-1 次循环，完成堆排序t=a

33、rrayi;arrayi=array1;array1=t;AdjustTree(array,1,i-1);m_A04=a0;m_A05=a 1;m_A06=a 2;m_A07=a 3;UpdateData(false);5.2基于MFC勺应用程序测试运行程序后，首先出来的界面是如图 11所示:图11程序初始运行界面输入数据后，单击排序按钮后，数组排序后的数据在界面上显示出来，如图11所示。图12读入数据后的界面结论我本次课程设计，在DOS界面中，先用template<class Type>clasSt义sort模板类，类中数据类型用 type 代替，我定义了三个成员函数，Selec

34、tSort()，tree_select_sort() , HeapSort(),分别实现对成员变量 array数组的简单选择排序，树形选择排序，堆排序，又定义了两个成员函数write( ) 和 print( ) ，分别输入和输出成员变量， 根据模板类的定义要求， 成员函数都用 template<class Type>修饰，使之能适用于多种数据类型，而不是局限于一种。 我将函数的声明与定义分离，在类中声明函数，在类体外定义函数，是程序清晰易读。通过努力，程序正确运行，并得到了实验要求的结果，说明本次程序实现了其主要功能。 而我通过本次实验学到了如何定义模板类，如何使用多种方法为数组排

35、序。我本次实验同样采用了 MFC 程序，通过对MFC 程序的编写与运行，得到相同的结果， 也证明了程序的正确性。 本此编写的 MFC 程序虽然能实现所需功能， 但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足， 主要包括以下几个方面：( 1) 员均为public 公有类型，使程序安全性变差，违背了面向对象程序设计理念，应该把数据定义为私有类型。( 2) 将类的定义与实现放在同一个文件中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件。( 3) 程序界面中图 12 显示没有格式化，导致界面看起来不够规范，应该统一框的高度和宽度。参考文献1 刘勇 郭韶升 张炜 周丽雅 数据结构试验与实训教程 国防工业出版社 20112郑莉,董渊，张瑞丰.C+语言程序设计（第 3版）.北京：清华大学出版 社,2007:25-603钱能.C+程序设计教程（第二版）.北京精华大学出版社,2007:100-1304 陈志泊 , 王春玲 . 面向对象的程序设计语言 C+. 北京 : 人民邮电出版 社,2002:115-1305 秦玉平 马靖善 数据结构（ c 语言版） （第 2 版）清华大学出版社2012