基于选择排序方法的类模板设计与实现c--课程设计毕设论文.doc

成 绩 评 定 表
学生姓名
吴琼
班级学号

专 业
通信工程
课程设计题目
基于选择排序方法的类模板设计与实现
评

语

组长签字：

成绩

日期

20 年 月 日

课程设计任务书
学 院
信息科学与工程
专 业
通信工程
学生姓名
吴琼
班级学号

课程设计题目
基于选择排序方法的类模板设计与实现
实践教学要求与任务

建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char, int, float等多种数据类型，并对数组元素实现选择类排序。主要完成如下功能：
（1） 实现数组数据的输入和输出；
（2） 实现简单选择排序功能；
（3） 实现树形选择排序功能；
（4） 实现堆排序功能；
（5） 将每种排序功能作为类的成员函数实现，编写主函数测试上述排序功能。

工作计划与进度安排

第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；
第18周：程序的设计、调试与实现；
第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。
指导教师：

201 年 月 日
专业负责人：

201 年 月 日
学院教学副院长：

201 年 月 日

摘 要
计算机中存储的数据，初始时没有任何排列规律，根据实际需求，经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。
选择排序是排序法中很经典的算法，选择排序法可以分为简单选择排序、树形选择排序和堆排序。
本文采用C++语言实现了选择排序功能，设计了模板类，实现了int型float型和char型数组的排序，设计了简单选择排序、树形选择排序和堆排序的三个函数体，采用Visual C++ 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.1 MFC程序界面设计 13
5.1.2 MFC程序代码设计 15
5.2基于MFC的应用程序测试 21
结 论 22
参考文献 23

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

2 算法基本原理
（1）简单选择排序
从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。
//简单选择排序
SelectSort(Type ar[])
{
int i,j;
Type t;
for(i=1;i<len;i++)
for(j=i+1;j<=len;j++)
if(array[i]>array[j])
{t=array[i];array[i]=array[j];array[j]=t;}
}

（2）树形选择排序
树形选择排序的基本思想：树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

（3）．堆排序
堆排序由建初始堆和调整堆两个过程组成。再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树，经调整根节点后使之成为堆的过程。建堆时一定要从最后一个非叶子结点开始。
堆排序的关键是调整堆，建初始堆时也是要从最后一个非叶子结点开始向根结点方向进行调整建堆。假设完全二叉树的第i个结点的左子树，右子树已是堆，则对第i个结点进行调整时，需要将r[2i].key与r[2i+1].key之中的最大者与r[i].key进行比较，若r[i].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=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<class Type> 限定，其中的数据类型用type代替，所有的成员函数都用template<class Type> 修饰，使之能适用于多种数据类型。
4 基于控制台的应用程序
整个程序只用一个独立的文档，文件中包含一个模板类，主函数中定义多个对象来实现调用三个成员函数对数组进行简单选择排序，树形选择排序，堆排序这三种排序，在此定义了三个对象分别是整型、字符型和浮点型的。

4.1 类的接口设计
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream.h>
#define num 50
#define M 50
#define MIN_VALUE -10000
template<class Type>class 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 array[num];
};
在此定义了模板类，类中所有的成员函数和成员变量均定义为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(array[i]>array[j])
{t=array[i];array[i]=array[j];array[j]=t;}
}

template <class Type>
void Sort<Type>::tree_select_sort(Type arr[],int n) //树形选择排序
{
Type tree[M]; // 树
int baseSize; // 当n是2的幂次时,baseSize是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++) // 从数组的后面部分开始填充, 不使用tree[0]
{
tree[treeSize - i] = arr[i];
}

for (;i < baseSize;i++) // 用MIN_VALUE填充tree,直到一共有baseSize个
{
tree[treeSize - i] = MIN_VALUE;
}
// 构造一棵树
for (i = treeSize;i > 1;i -= 2)
{
// 以arr[i]和arr[i + 1]为子结点的数的根是arr[i]和arr[i + 1]中的较大者
tree[i / 2] = (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[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]);
}
else // 如果不是左子结点
{
// 用子结点中较大值代替父结点
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]);
}
maxIndex /= 2; // 继续处理父结点
}
}
}

template <class Type>
void Sort<Type>::AdjustTree(Type ar[],int k,int n) //调整堆
{
int i,j;
i=k;
j=2*i; //arrau[j]是array[i]的左孩子
Type temp=array[i];
while(j<=n)
{if(j<n&&array[j]<array[j+1]) //若有孩子较大，把j指向右孩子
j=j+1;
if(temp<array[j])
{
array[i]=array[j]; //array[j]调整到双亲结点
i=j;
j=2*i;
}
else break;
}
array[i]=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=array[i];
array[i]=array[1];
array[1]=t;
AdjustTree(array,1,i-1);
}
}

template<class Type>
void Sort<Type>::write() //输入数组
{
int i,l;
printf("请输入数组长度:");
scanf("%d",&l);
len=l;
printf("请输入数组元素:\n");
for(i=1;i<=l;i++)
cin>>array[i];
}

template<class Type>
void Sort<Type>::print() //输出数组
{int i;
printf("排序后的数组为:\n");
for(i=1;i<=len;i++)
cout<<array[i]<<" ";
cout<<endl;
}

在类的成员函数实现过程中，系统会自动为类产生构造函数，类的构造函数自动调用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成。
成员函数对成员变量进行操作，实现排序功能，通过for( ) 循环，实现输入输出数组元素的功能。

4.3 主函数设计
在程序的主函数部分，选择了分别以int、char和float型为数据类型的对象作为实际例子来验证算法。首先，选择数据类型；然后，通过write( ) 函数对成员变量数组array[ ] 进行赋值，通过swich（）语句选择排序方式，用对象调用对应的成员函数实现数组排序；最后，通过print（）函数输出排序后的结果。

void main() //主函数
{ int i,j=1;
Sort<int> s;
Sort<char> p;
Sort<float> z;
cout<<"选择输入类型:1.int 2.char 3.float"<<endl;
cin>>i;
if(i==1)
{s.write();
cout<<"请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序"<<endl;
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();}
else if(i==2)
{p.write();
cout<<"请选择排序方式:1.简单选择排序 2.树形选择排序 3.堆排序<<endl";
cin>>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.堆排序<<endl";
cin>>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类型的排序

图1

（2） 用树形选择排序进行char类型的排序

图2

（3）用堆排序进行float类型的排序

图3

5 基于MFC的应用程序
MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。

5.1.1 MFC程序界面设计
首先在VC中建立MFC AppWizard（exe）工程，名称为1203060128，并在向导的Step1中选择基本对话框，即建立基于对话框的应用程序，如下图4、图5所示。

图4建立MFC AppWizard（exe）工程

图5 建立基于对话框的应用程序

将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6所示。

图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程序代码设计

为了能够将对话框界面上的控件能够与代码联系起来，需要为10个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设置界面，如图7所示。

图7 成员变量设置界面

通过该界面设置与10个Edit Box控件对应的成员变量，具体如表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） 简单选择排序
int a[5];
UpdateData(true);
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
int i,j,k;
int temp;
int len=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） 树形选择排序
int a[5];
UpdateData(true);
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
char tree[50]; //树
int max;//最大值
int baseSize;
int i;
int maxIndex;//最大值的下标
int treeSize;//最终这棵树会达到的大小
int len=5;
int MIN_VALUE=0;
baseSize=1;
while(baseSize<len)
{
baseSize*=2;
}
treeSize=baseSize*2-1;
for(i=0;i<len;i++)
{
tree[treeSize-i]=a[i];
}
for(;i<baseSize;i++)
{
tree[treeSize-i]=MIN_VALUE;
}//构造一棵树
for(i=treeSize;i>1;i-=2)
{
tree[i/2]=(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[maxIndex/2]=(tree[maxIndex]>tree[maxIndex+1]?tree[maxIndex]:tree[maxIndex+1]);
}
else
{
tree[maxIndex/2]=(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） 堆排序
int a[5];
UpdateData(true);
a[0]=m_l1;
a[1]=m_l2;
a[2]=m_l3;
a[3]=m_l4;
a[4]=m_l5;
int i=0,j,temp;
int p=10;
int q=10;
int len=5;
j=2*p;
while(j<=q)//堆顶元素下筛
{if((j<q)&&(a[j]<a[j+1]))//确定下筛位置
++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 程序初始运行界面

单击简单选择排序按钮后，可将输入前的字符进行排序，如图6所示。

图9 排序后的界面

结 论
本次课程设计，在DOS界面中，先用template<class Type>class定义sort模板类，类中数据类型用type代替，我定义了三个成员函数，SelectSort（），tree_select_sort（），HeapSort（），分别实现对成员变量array[ ]数组的简单选择排序，树形选择排序，堆排序，又定义了两个成员函数write( ) 和print( )，分别输入和输出成员变量，根据模板类的定义要求，成员函数都用template<class Type>修饰，使之能适用于多种数据类型，而不是局限于一种。我将函数的声明与定义分离，在类中声明函数，在类体外定义函数，是程序清晰易读。通过努力，程序正确运行，并得到了实验要求的结果，说明本次程序实现了其主要功能。而我通过本次实验学到了如何定义模板类，如何使用多种方法为数组排序。
MFC程序与DOS界面程序编写的最大不同是程序员需要将编程精力放在图形界面设计、图形界面输入输出以及界面各种排序的设计等问题上，而这些问题在DOS界面程序中是不存在的。本次课程设计作为编写Windows程序的初步尝试，能够实现程序的主要功能，可以说是取得了成功，然而好的程序绝不仅仅是只有功能性这一个指标，编写出一个基于Windows界面的程序时，所获得的满足程度远远大于简单的DOS界面程序，本次编写的MFC程序虽然能实现所需功能，但从面向对象程序设计理念和图形界面设计要求来说，尚存在不足，主要包括以下几个方面。
（1） 本次的MFC程序只能对整型数组排序，如果改为char型、float型的，需从属性的对话框中重复选择。这样确实很不实用。作者希望选择的类型可以自主进行转换
（2）将类的定义与实现放在同一个头文件中也违背了面向对象程序设计理念，需要将二者分开成定义文件和实现文件。

参考文献
[1] 谭浩强. C程序设计. 北京:清华大学出版社,1991
[2] 郑振洁C++程序设计. 北京:人民邮电出版社,2005
[3] 柴欣.C/ C++程序设计. 河北大学出版社,2002
[4] 余苏宁、王明福.C++程序设计. 北京:高等教育出版社,2003
[5] 李云清、杨庆红、揭安全.数据结构[m] .人民邮电大学出版社,2004

22