精品基于选择排序方法的类模板设计与实现C++毕业论文.docx
《精品基于选择排序方法的类模板设计与实现C++毕业论文.docx》由会员分享，可在线阅读，更多相关《精品基于选择排序方法的类模板设计与实现C++毕业论文.docx（24页珍藏版）》请在冰点文库上搜索。
精品基于选择排序方法的类模板设计与实现C++毕业论文
成绩评定表
学生姓名
吴琼
班级学号
专业
通信工程
课程设计题目
基于选择排序方法的类模板设计与实现
评
语
组长签字：
成绩
日期
20年月日
课程设计任务书
学院
信息科学与工程
专业
通信工程
学生姓名
吴琼
班级学号
课程设计题目
基于选择排序方法的类模板设计与实现
实践教学要求与任务
建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现选择类排序。
主要完成如下功能：
（1）实现数组数据的输入和输出；
（2）实现简单选择排序功能；
（3）实现树形选择排序功能；
（4）实现堆排序功能；
（5）将每种排序功能作为类的成员函数实现，编写主函数测试上述排序功能。
工作计划与进度安排
第17周：
分析题目，查阅课题相关资料，进行类设计、算法设计；
第18周：
程序的设计、调试与实现；
第19周：
程序测试与分析，撰写课程设计报告，进行答辩验收。
指导教师：
201年月日
专业负责人：
201年月日
学院教学副院长：
201年月日
摘要
计算机中存储的数据，初始时没有任何排列规律，根据实际需求，经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。
选择排序是排序法中很经典的算法，选择排序法可以分为简单选择排序、树形选择排序和堆排序。
本文采用C++语言实现了选择排序功能，设计了模板类，实现了int型float型和char型数组的排序，设计了简单选择排序、树形选择排序和堆排序的三个函数体，采用VisualC++6.0的控制台工程和MFC工程分别实现了各类型数组的排序，通过对两种程序的测试结果表明：
简单选择排序是选择排序的基础，而树形选择排序和堆排序是简单选择排序的改进。
关键词：
模板类；简单选择排序；树形选择排序；堆排序；控制台工程；MFC工程。
目录
1需求分析1
2算法基本原理1
3类设计3
4基于控制台的应用程序3
4.1类的接口设计4
4.2类的实现4
4.3主函数设计9
4.4基于控制台的应用程序测试11
5基于MFC的应用程序13
5.1基于MFC的应用程序设计13
5.1.1MFC程序界面设计13
5.1.2MFC程序代码设计15
5.2基于MFC的应用程序测试21
结论22
参考文献23
1需求分析
（1）当进行数据处理时,经常遇到需要进行查找操作,通常希望待处理的数据按关键字大小有序排序,因为这样就可以采用查找效率较高的查找算法。
（2）对有序的顺序表可以采用查找效率较高的折半查找算法，而对无序的
顺序表只能采用顺序查找算法。
由此可见排序是计算机程序设计中一种基础性操
作，研究和掌握各种排序方法是非常重要的。
（3）排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且直接影响着计算机的工作效率。
本实验题目为基于选择排序方法的类模板设计与实现，要求建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现选择类排序。
因此实验采用类模板，可以对不同的数据类型的数据进行排序，并通过函数采用不同的方法进行排序。
2算法基本原理
（1）简单选择排序
从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。
简单选择排序
SelectSort（Typear[]）
{
inti,j;
Typet;
for（i=1;ifor（j=i+1;j<=len;j++）
if（array[i]>array[j]）
{t=array[i];array[i]=array[j];array[j]=t;}
}
（2）树形选择排序
树形选择排序的基本思想：
树形选择排序又称锦标赛排序（TournamentSort），是一种按照锦标赛的思想进行选择排序的方法。
首先对n个记录的关键字进行两两比较，然后在n2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。
（3）．堆排序
堆排序由建初始堆和调整堆两个过程组成。
再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树，经调整根节点后使之成为堆的过程。
建堆时一定要从最后一个非叶子结点开始。
堆排序的关键是调整堆，建初始堆时也是要从最后一个非叶子结点开始向根结点方向进行调整建堆。
假设完全二叉树的第i个结点的左子树，右子树已是堆，则对第i个结点进行调整时，需要将r[2i].key与r[2i+1].key之中的最大者与r[i].key进行比较，若r[i].key较小则与之交换。
这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。
如此反复，直到将以第i个结点为根的子树构成堆为止。
算法:
HeapSort（Typear[]）
{
inti;
Typet;循环建立初始堆
for（i=len2;i>=1;i--）
AdjustTree（array,i,len）;
进行n-1次循环，完成堆排序
for（i=len;i>=2;i--）
{t=array[i];
array[i]=array[1];
array[1]=t;
AdjustTree（array,1,i-1）;
}
}
3类设计
从上面的算法分析可以看到，本设计面临的问题的关键是类模板。
可以定义一个模板类sort，模板类sort功能有输入，输出数组，用三种方法对数组进行排序。
从问题的需要来看，在模板类中定义三个成员函数。
成员函数SelectSort（）对数组进行简单选择排序，成员函数tree_select_sort（）对数组进行树形选择排序，成员函数HeapSort（）对数组进行堆排序。
成员函数AdjustTree（）通过始建和调整堆辅助堆排序，而成员函数write（）和print（）输入输出数组。
主函数中应用if（）判断语句确定数组数据类型，swich（）语句选择使用的排序方法。
定义了两个对象分别是整型和字符型的。
类用template限定，其中的数据类型用type代替，所有的成员函数都用template修饰，使之能适用于多种数据类型。
4基于控制台的应用程序
整个程序只用一个独立的文档，文件中包含一个模板类，主函数中定义多个对象来实现调用三个成员函数对数组进行简单选择排序，树形选择排序，堆排序这三种排序，在此定义了三个对象分别是整型、字符型和浮点型的。
4.1类的接口设计
#includevoidwrite（）;
voidSelectSort（Typear[]）;
voidtree_select_sort（Typearr[],intn）;
voidHeapSort（Typear[]）;
voidprint（）;
intlen;
Typearray[num];
};
在此定义了模板类，类中所有的成员函数和成员变量均定义为public的公有类型，是类的对外接口，数据类型用type代替。
成员函数在类中只有函数类型，函数名，参数，对函数进行内部声明，函数体在类体外定义
4.2类的实现
简单选择排序
template
voidSort:
:
SelectSort（Typear[]）
{
inti,j;
Typet;
for（i=1;ifor（j=i+1;j<=len;j++）
if（array[i]>array[j]）
{t=array[i];array[i]=array[j];array[j]=t;}
}
template
voidSort:
:
tree_select_sort（Typearr[],intn）树形选择排序
{
Typetree[M];树
intbaseSize;当n是2的幂次时,baseSize是n,当n不是时,baseSize是大于n的最小的2的幂次
就是构造成满二叉树的最下层的大小，即叶子数
inti;
Typemax;最大值
intmaxIndex;最大数的下标
inttreeSize;最终这棵树会达到的大小
baseSize=1;
while（baseSize{
baseSize*=2;
}
treeSize=baseSize*2-1;满二叉树的所有结点个数等于叶子数的2倍减一
for（i=0;i{
tree[treeSize-i]=arr[i];
}
for（;i{
tree[treeSize-i]=MIN_VALUE;
}
构造一棵树
for（i=treeSize;i>1;i-=2）
{
以arr[i]和arr[i+1]为子结点的数的根是arr[i]和arr[i+1]中的较大者
tree[i2]=（tree[i]>tree[i-1]?
tree[i]:
tree[i-1]）;
}
n=n-1;此时的n表示当前tree[1]应该放到arr中的位置
不断把树中值为最大值的结点移走,直到n的值为-1
while（n!
=-1）
{
max=tree[1];
arr[n--]=max;
maxIndex=treeSize;
在叶子上找到最大值对应的下标
while（tree[maxIndex]!
=max）
{
maxIndex--;
}
tree[maxIndex]=MIN_VALUE;
沿着叶子上的结点到根的路径更新
while（maxIndex>1）当结点还有父结点时
{
if（maxIndex%2==0）如果值为最大值的结点是左子结点
{
用子结点中较大值代替父结点
tree[maxIndex2]=（tree[maxIndex]>tree[maxIndex+1]?
tree[maxIndex]:
tree[maxIndex+1]）;
}
else如果不是左子结点
{
用子结点中较大值代替父结点
tree[maxIndex2]=（tree[maxIndex]>tree[maxIndex-1]?
tree[maxIndex]:
tree[maxIndex-1]）;
}
maxIndex=2;继续处理父结点
}
}
}
template
voidSort:
:
AdjustTree（Typear[],intk,intn）调整堆
{
inti,j;
i=k;
j=2*i;arrau[j]是array[i]的左孩子
Typetemp=array[i];
while（j<=n）
{if（jj=j+1;
if（temp{
array[i]=array[j];array[j]调整到双亲结点
i=j;
j=2*i;
}
elsebreak;
}
array[i]=temp;
}
template
voidSort:
:
HeapSort（Typear[]）堆排序
{
inti;
Typet;
for（i=len2;i>=1;i--）循环建立初始堆
AdjustTree（array,i,len）;
for（i=len;i>=2;i--）进行n-1次循环，完成堆排序
{t=array[i];
array[i]=array[1];
array[1]=t;
AdjustTree（array,1,i-1）;
}
}
template
voidSort:
:
write（）输入数组
{
inti,l;
printf（"请输入数组长度:
"）;
scanf（"%d",&l）;
len=l;
printf（"请输入数组元素:
\n"）;
for（i=1;i<=l;i++）
cin>>array[i];
}
template
voidSort:
:
print（）输出数组
{inti;
printf（"排序后的数组为:
\n"）;
for（i=1;i<=len;i++）
cout<cout<}
在类的成员函数实现过程中，系统会自动为类产生构造函数，类的构造函数自动调用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成。
成员函数对成员变量进行操作，实现排序功能，通过for（）循环，实现输入输出数组元素的功能。
4.3主函数设计
在程序的主函数部分，选择了分别以int、char和float型为数据类型的对象作为实际例子来验证算法。
首先，选择数据类型；然后，通过write（）函数对成员变量数组array[]进行赋值，通过swich（）语句选择排序方式，用对象调用对应的成员函数实现数组排序；最后，通过print（）函数输出排序后的结果。
voidmain（）主函数
{inti,j=1;
Sorts;
Sortp;
Sortz;
cout<<"选择输入类型:
1.int2.char3.float"<cin>>i;
if（i==1）
{s.write（）;
cout<<"请选择排序方式:
1.简单选择排序2.树形选择排序3.堆排序"<cin>>i;
switch（i）
{
case1:
s.SelectSort（s.array）;break;
case2:
s.tree_select_sort（s.array,s.len+1）;break;
case3:
s.HeapSort（s.array）;break;
default:
break;
}
s.print（）;}
elseif（i==2）
{p.write（）;
cout<<"请选择排序方式:
1.简单选择排序2.树形选择排序3.堆排序<cin>>i;
switch（i）
{
case1:
p.SelectSort（p.array）;break;
case2:
p.tree_select_sort（p.array,p.len+1）;break;
case3:
p.HeapSort（p.array）;break;
default:
break;
}
p.print（）;}
elseif（i==3）
{z.write（）;
cout<<"请选择排序方式:
1.简单选择排序2.树形选择排序3.堆排序<cin>>i;
switch（i）
{
case1:
z.SelectSort（z.array）;break;
case2:
z.tree_select_sort（z.array,z.len+1）;break;
case3:
z.HeapSort（z.array）;break;
default:
break;
}
z.print（）;}
}
4.4基于控制台的应用程序测试
（1）用简单选择排序进行int类型的排序
图1
（2）用树形选择排序进行char类型的排序
图2
（3）用堆排序进行float类型的排序
图3
5基于MFC的应用程序
MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：
MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等IO流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。
5.1.1MFC程序界面设计
向导的Step1中选择基本对话框，即建立基于对话框的应用程序，如下图4、图5所示。
图4建立MFCAppWizard（exe）工程
图5建立基于对话框的应用程序
将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6所示。
图6选择排序方法的实现界面设计
图3所示的界面中包含了2个StaticText控件，3个Button控件，和10个EditBox控件,控件的基本信息列表如下表1所示。
表1控件基本信息
StaticText
IDC_STATIC
输入前
输入后
Botton
IDC_BUTTON_1
简单选择排序
IDC_BUTTON_2
树形选择排序
IDC_BUTTON_3
堆排序
EditBox
IDC_EDIT_m1~IDC_EDIT_m5
输入的5个元素
IDC_EDIT_m6~IDC_EDIT_m10
输出的5个元素
5.1.2MFC程序代码设计
为了能够将对话框界面上的控件能够与代码联系起来，需要为10个EditBox控件建立MemberVariables，按Ctrl+w键进入MFCClassWizard界面，选择MemberVariables选项卡，可显示成员变量设置界面，如图7所示。
图7成员变量设置界面
通过该界面设置与10个EditBox控件对应的成员变量，具体如表2所示。
表2控件基本信息
控件ID
成员变量类型
成员变量名称
IDC_EDIT_m1~IDC_EDIT_m5
Int
m_1~m_5
IDC_EDIT_m6~IDC_EDITm_10
Int
m_6~m_10
下面是编写代码的重要阶段
（1）简单选择排序
inta[5];
UpdateData（true）;
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
inti,j,k;
inttemp;
intlen=5;
for（i=0;i<=len;i++）
{k=i;
for（j=i+1;j<=len;j++）
if（a[k]>a[j]）
k=j;
if（k!
=i）
{
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
m_l6=a[0];
m_l7=a[1];
m_l8=a[2];
m_l9=a[3];
m_l10=a[4];
UpdateData（false）;
（2）树形选择排序
inta[5];
UpdateData（true）;
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
chartree[50];树
intmax;最大值
intbaseSize;
inti;
intmaxIndex;最大值的下标
inttreeSize;最终这棵树会达到的大小
intlen=5;
intMIN_VALUE=0;
baseSize=1;
while（baseSize{
baseSize*=2;
}
treeSize=baseSize*2-1;
for（i=0;i{
tree[treeSize-i]=a[i];
}
for（;i{
tree[treeSize-i]=MIN_VALUE;
}构造一棵树
for（i=treeSize;i>1;i-=2）
{
tree[i2]=（tree[i]>tree[i-1]?
tree[i]:
tree[i-1]）;
}
len=len-1;
while（len!
=-1）
{
max=tree[1];
a[len--]=max;
maxIndex=treeSize;
while（tree[maxIndex]!
=max）
{
maxIndex--;
}
tree[maxIndex]=MIN_VALUE;
while（maxIndex>1）
{
if（maxIndex%2==0）
{
tree[maxIndex2]=（tree[maxIndex]>tree[maxIndex+1]?
tree[maxIndex]:
tree[maxIndex+1]）;
}
else
{
tree[maxIndex2]=（tree[maxIndex]>tree[maxIndex-1]?
tree[maxIndex]:
tree[maxIndex-1]）;
}
maxIndex=2;
}
}
m_l6=a[0];
m_l7=a[1];
m_l8=a[2];
m_l9=a[3];
m_l10=a[4];
UpdateData（false）;
（3）堆排序
inta[5];
UpdateData（true）;
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
inti=0,j,temp;
intp=10;
intq=10;
intlen=5;
j=2*p;
while（j<=q）堆顶元素下筛
{if（（j++j;
temp=a[i];
if（temp>a[j]）break;
a[p]=a[j];p=j;
j*=2;}
a[p]=temp;
{temp=a[1];
a[1]=a[i];
a[i]=temp;}
m_l6=a[0];
m_l7=a[1];
m_l8=a[2];
m_l9=a[3];
m_l10=a[4];
UpdateData（false）;
5.2基于MFC的应用程序测试
运行程序后，首先出现的界面如图8所示。
图8程序初始运行界面
单击简单选择排序按钮后，可将输
升级会员 