级面向对象课设范例通信工程文档格式.docx

级面向对象课设范例通信工程文档格式.docx

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

摘要

计算机中存储的数据，初始时没有任何排列规律，根据实际需求，经常要排列成有规律的数据序列也就是将数据序列按关键字升序或降序规律排列。

本文采用C++语言实现了选择排序功能，设计了模板类，采用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需求分析

排序是现实世界中经常进行的一种操作。

本此实验题目为基于选择排序方法的类模板设计与实现，要求建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现选择类排序。

因此实验采用类模板，可以对不同的数据类型的数据进行排序，并通过函数采用不同的方法进行排序。

2算法基本原理

（1）简单选择排序

从无序的记录序列中选出一个关键字值最小的记录存入到指定的位置。

//简单选择排序

SelectSort（Typear[]）

{

inti,j;

Typet;

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）树形选择排序

树形选择排序是一种借助于锦标赛方式的选择排序方法。

锦标赛的本思想是通过分组淘汰决出冠军，亚军一定是从输给冠军的选手中选手中产生，季军一定是从输给亚军的选手中产生的。

树形选择排序使用近似为完全二叉树的树形，所有记录均为叶子节点从叶子

结点开始，通过两两比较填到树顶结点是对应关键字最小的记录，然后将该叶子结点关键字置成最大关键字，继续选出第二个最小值。

如此重复进行，直到排序结束。

（3）．堆排序

堆排序就是利用堆的特性对记录序列进行排序的一种方法。

具体做法是：

先建一个大顶堆，即先选的一个关键字最大的记录，然后与序列中最后一个记录交换，再对序列中前n-1条记录进行“筛选”，重新将它调整成为一个大顶堆，再将堆顶记录和第n-1个记录交换。

如此反复进行，直到所有记录有序为止。

实质上，堆排序由建初始堆和调整堆两个过程组成。

再次，所谓筛选是指对一棵左右子树均为堆的完全二叉树，经调整根节点后使之成为堆的过程。

建堆时一定要从最后一个非叶子结点开始。

堆排序的关键是调整堆，建初始堆时也是要从最后一个非叶子结点开始向根结点方向进行调整建堆。

假设完全二叉树的第i个结点的左子树，右子树已是堆，则对第i个结点进行调整时，需要将r[2i].key与r[2i+1].key之中的最大者与r[i].key进行比较，若r[i].key较小则与之交换。

这有可能破坏下一级的堆，因此，需要继续采用上述方法调整构造下一级的堆。

如此反复，直到将以第i个结点为根的子树构成堆为止。

算法:

//堆排序

HeapSort（Typear[]）

inti;

//循环建立初始堆

for（i=len/2;

i>

=1;

i--）

AdjustTree（array,i,len）;

//进行n-1次循环，完成堆排序

for（i=len;

=2;

{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<

classType>

限定，其中的数据类型用type代替，所有的成员函数都用template<

修饰，使之能适用于多种数据类型。

4基于控制台的应用程序

整个程序只用一个独立的文档，文件中包含一个模板类，主函数中可以定义多个对象来实现调用成员函数对数组进行排序，在此举例定义了两个对象分别是整型和字符型的。

4.1类的接口设计

#include<

stdio.h>

string.h>

stdlib.h>

iostream.h>

#definenum50

#defineM50

#defineMIN_VALUE-10000

template<

classSort

public:

//外部接口

voidAdjustTree（Typear[],intn,intk）;

voidwrite（）;

voidSelectSort（Typear[]）;

voidtree_select_sort（Typearr[],intn）;

voidHeapSort（Typear[]）;

voidprint（）;

intlen;

Typearray[num];

};

在此定义了模板类，类中所有的成员函数和成员变量均定义为public的公有类型，是类的对外接口，数据类型用type代替。

成员函数在类中只有函数类型，函数名，参数，对函数进行内部声明，函数体在类体外定义

4.2类的实现

template<

voidSort<

Type>

:

tree_select_sort（Typearr[],intn）//树形选择排序

Typetree[M];

//树

intbaseSize;

//当n是2的幂次时,baseSize是n,当n不是时,baseSize是大于n的最小的2的幂次

//就是构造成满二叉树的最下层的大小，即叶子数

inti;

Typemax;

//最大值

intmaxIndex;

//最大数的下标

inttreeSize;

//最终这棵树会达到的大小

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（;

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-1]?

tree[maxIndex-1]）;

maxIndex/=2;

//继续处理父结点

AdjustTree（Typear[],intk,intn）//调整堆

i=k;

j=2*i;

//arrau[j]是array[i]的左孩子

Typetemp=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;

elsebreak;

array[i]=temp;

HeapSort（Typear[]）//堆排序

for（i=len/2;

i--）//循环建立初始堆

for（i=len;

i--）//进行n-1次循环，完成堆排序

write（）//输入数组

inti,l;

printf（"

请输入数组长度:

"

）;

scanf（"

%d"

&

l）;

len=l;

请输入数组元素:

\n"

for（i=1;

=l;

cin>

>

array[i];

print（）//输出数组

{inti;

printf（"

排序后的数组为:

cout<

<

array[i]<

"

;

endl;

在类的成员函数实现过程中，系统会自动为类产生构造函数，类的构造函数自动调用，为类动态分配了内存空间，整个调用过程中完全是由系统内部完成。

成员函数对成员变量进行操作，实现排序功能，通过for（）循环，实现输入输出数组元素的功能。

4.3主函数设计

voidmain（）//主函数

{inti,j=1;

Sort<

int>

s;

char>

p;

选择输入类型:

1int2char"

cin>

i;

if（i==j）

{s.write（）;

请选择排序方式:

1.简单选择排序2.树形选择排序3.堆排序"

switch（i）

case1:

s.SelectSort（s.array）;

break;

case2:

s.tree_select_sort（s.array,s.len+1）;

case3:

s.HeapSort（s.array）;

default:

s.print（）;

else

{p.write（）;

p.SelectSort（p.array）;

p.tree_select_sort（p.array,p.len+1）;

p.HeapSort（p.array）;

p.print（）;

在程序的主函数部分，选择了分别以int和char型为数据类型的对象作为实际例子来验证算法。

首先，选择数据类型，然后，通过write（）函数对成员变量数组array[]进行赋值，通过swich（）语句选择排序方式，用对象调用对应的成员函数实现数组排序，最后，通过print（）函数输出排序后的结果。

4.4基于控制台的应用程序测试

图1程序运行结果

图1为简单选择排序运行结果，数据类型为int型。

图2程序运行结果

图2为树形选择排序运行结果，数据类型为int型。

图3程序运行结果

图3为堆排序运行结果，数据类型为int型。

图4程序运行结果

图4为简单选择排序运行结果，数据类型为char。

图5程序运行结果

图5为树形选择排序运行结果，数据类型为char。

图6程序运行结果

图6为堆排序运行结果，数据类型为char型。

5基于MFC的应用程序

MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：

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

5.1基于MFC的应用程序设计

5.1.1MFC程序界面设计

首先在VC中建立MFCAppWizard（exe）工程，名称为sort，并在向导的Step1中选择Dialogbased，即建立基于对话框的应用程序，如下图7~8所示。

图7建立MFCAppWizard（exe）工程

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

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

图9数组排序程序界面设计

图9所示的界面中包含了2个StaticText控件，3个Button控件，和8个EditBox控件，控件的基本信息列表如下表1所示。

表1控件基本信息

控件类别

控件ID

控件Caption

说明

StaticText

IDC_STATIC

数组

排序后数组

Botton

IDC_BUTTON_Read

简单选择排序

IDC_BUTTON_CALC

树形选择排序

IDC_BUTTON_Exit

堆排序

EditBox

IDC_EDIT_A00~IDC_EDIT_A07

数组A的8个元素

5.1.2MFC程序代码设计

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

图10成员变量设置界面

通过该界面设置与8个EditBox控件对应的成员变量，具体如表2所示。

表2控件基本信息

成员变量类型

成员变量名称

IDC_EDIT_A00~IDC_EDIT_A33

int

m_A00~m_A08

下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体程序如下：

voidCSortDlg:

OnButton1（）

//TODO:

Addyourcontrolnotificationhandlercodehere

inta[4];

UpdateData（true）;

a[0]=m_A00;

a[1]=m_A01;

a[2]=m_A02;

a[3]=m_A03;

inti,j,k;

inttemp;

intlen=4;

for（i=0;

{k=i;

if（a[k]>

a[j]）

k=j;

if（k!

=i）

temp=a[k];

a[k]=a[i];

a[i]=temp;

m_A04=array[0];

m_A05=array[1];

m_A06=array[2];

m_A07=array[3];

UpdateData（false）;

OnButton2（）

inta[4];

UpdateData（true）;

Typetree[M];

for（;

//构造一棵树

n=n-1;

while（n!

tree[maxI