C++课程设计任务书 沈理工

1、成成 绩绩 评评 定定 表表学生姓名班级学号专 业课程设计题目基于插入排序方法的类模板设计与实现评语组长签字：成绩日期 20 年 月 日课程设计任务书课程设计任务书学 院信息科学与工程专 业学生姓名班级学号课程设计题目 基于插入排序方法的类模板设计与实现实践教学要求与任务实践教学要求与任务建立一维数组数据结构的模板类，使一维数组中的数据元素可以是 char, int, float等多种数据类型，并对数组元素实现插入类排序。主要完成如下功能：（1） 实现数组数据的输入和输出；（2） 实现直接插入排序功能；（3） 实现 2-路插入排序功能；（4） 实现希尔排序功能；（5） 将每种排序功能作为类的成

2、员函数实现，编写主函数测试上述排序功能。工作计划与进度安排工作计划与进度安排第 17 周：分析题目，查阅课题相关资料，进行类设计、算法设计；第 18 周：程序的设计、调试与实现；第 19 周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日 摘 要排序是计算机程序设计中的一种重要运算，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。简言之，所谓排序就是根据关键字值的非递减或非递增次序，把文件中的各记录依次排列起来，可使一个无序文件变成有序文件的一种操作。有一个已经有序的数

3、据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法。插入排序包括：直接插入排序，折半插入排序，2-路插入排序，表插入排序，希尔排序。关键词：直接插入排序法；2路插入排序法；希尔排序法；MFC 工程目 录1 需求分析.12 算法基本原理.23 类设计.34 基于控制台的应用程序.44.1 类的接口设计.44.2 类的实现.54.3 主函数设计.74.4 基于控制台的应用程序测试.95 基于 MFC 的应用程序 .125.1 基于 MFC 的应用程序设计.125.1.1 MFC 程序界面设计 .105.1.2 MFC 程序代

4、码设计 .135.2 基于 MFC 的应用程序测试.17结 论.21参考文献.22沈阳理工大学课程设计01 需求分析需求分析（1）有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法。插入排序包括：直接插入排序，折半插入排序，2-路插入排序，表插入排序，希尔排序。（2）插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，知道将所有待排记录全部插入为止。这很像打扑克牌时，没抓一张牌，插入到合适位置，知道抓完牌为止，即可得到一个有序序列。（3）

5、直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增 1 的有序表。设整个排序有 n 个数，则进行 n-1 趟插入，即：先将序列中的第 1 个记录看成是一个有序的子序列，然后从第 2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。（4）2-路插入排序是在折半插入排序的基础上的发展。其目的是减少排序过程中记录移动的次数，但为此需 n 个记录的辅助空间。具体做法是：另设一个和 L. r 同类型的数组 d，首先将 L. r 1赋值给 d1，将 d1看成是排好序的序列中处于中间位置的记录，然后从 L. r 中第 2 个记录起依次插入到 d1之前或之后的有序序列

6、中。先将待排序记录的关键字和 d1的关键字比较，若 L.ri.key d1 .key ，则将 L.ri插入到 d1之前的有序表中。反之，将 L.ri插入到 d1之后的有序表中。在实现算法时，将 d 看成一个循环向量，并设两个指针 first 和 final 分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。(5)希尔排序又称“缩小增量排序”，它属于插入排序类。它的基本思想是：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。沈阳理工大学课程设计12 算法基本原理算法基本原理（1）直接插入

7、排序算法：排序过程为：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增 1 的有序表。设整个排序有 n 个数，则进行 n-1 趟插入，即：先将序列中的第 1个记录看成是一个有序的子序列，然后从第 2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。直接插入排序过程如图 2.1 所示：（2）2-路插入排序算法：排序过程为：另设一个和 L. r 同类型的数组 d，首先将 L. r 1赋值给 d1，将 d1看成是排好序的序列中处于中间位置的记录，然后从 L. r 中第 2 个记录起依次插入到 d1之前或之后的有序序列中。先将待排序记录的关键字和 d1的关键字比较，若 L

8、.ri.key d1 .key ，则将 L.ri插入到 d1之前的有序表中。反之，将 L.ri插入到 d1之后的有序表中。在实现算法时，将 d 看成一个循环向量，并设两个指针 first 和final 分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。 2-路插入排序过程如图 2.2 所示：（3）希尔排序算法： （3）希尔排序算法: 初始关键字 ( 49 ) 38 65 97 76 13 27 49 i=2: ( 38 49 ) 65 97 76 13 27 49 i=3: ( 38 49 65 ) 97 76 13 27 49 i=4: ( 38 49 65 97

9、 ) 76 13 27 49 i=5: ( 38 49 65 76 97 ) 13 27 49 i=6: ( 13 38 49 65 76 97 ) 27 49 i=7: ( 13 27 38 49 65 76 97 ) 49 i=8: ( 13 27 8 49 49 65 76 97 ) 图 2.1 直接插入排序过程图初始关键字 45 62 35 77 92 55 14 35 排序过程中 d 的状态如下： 初始状态 （45） final=1 first=9 i =2 （45 62） final=2 first=9 i =3 （45 62） （35） final=2 first=8 i =4

10、（45 62 77） （35） final=3 first=8 i =5 （45 62 77 92） （35） final=4 first=8 i =6 （45 55 62 77 92） （35） final=5 first=8 i =7 （45 55 62 77 92） （14 35） final=5 first=7 i =8 （45 55 62 77 92） （14 35 35） final=5 first=6 图 2.2 2-路插入排序过程图沈阳理工大学课程设计2（3）希尔排序算法：基本思想是：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序” ，待整个序列中的记录”基本有序“

11、时，再对全体记录进行一次直接插入排序。希尔排序过程如下图 2.3：初始关键字： 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 图 2.3 希尔排序过程图3 类设计从上面的过程分析可以看到，本设计的关键所在是对所输入数据分别进行三种不同的排序，所输入的数据有两种类型，分别为 int 型和 char 型。对于两种不同的数据类型，可以先建立一个类模板，虚拟类型名为 Type 型，类模板名为 Sort。在主函数main（）中建立两个对象，分别制定对象类型为 int 型和 char 型。在虚拟类中声明各成员函数：void writ

12、e（）读入数组函数；void InsertionSort（）直接插入排序函数；void Srsort（Type mi)二路排序；void ShellSort（Type da,int k）void Shellinsert（Type dk）希尔排序。Void print（）输出排序结果函数。分别在类模板外声明各成员函数。 一趟排序结果： 二趟排序结果：13 04 49 38 27 49 55 65 97 76 三趟排序结果： 04 13 27 38 49 49 55 65 76 97沈阳理工大学课程设计34 基于控制台的应用程序整个程序三部分。首先是声明类模板，其中包括输入输出数据成员函数的声明以

13、及直接插入排序，2路排序，希尔排序的成员函数声明。其次是在类外对所有成员函数进行定义。最后在主函数中实现数据的排序操作。4.1 类的接口设计 #include#include#include#include#define num 50template /声明一个模板，虚拟类型名为 Typeclass Sort /类模板名为 Sort private: int len; public: void write(); /声明读入数组函数void InsertionSort(); /声明直接插入排序函数 void Srsort(Type mi); /声明 2-路插入排序函数void ShellSort

14、(Type da,int t); void Shellinsert(Type dk); /声明希尔排序函数void print(); /声明输出结果函数Type arraynum; ;Template 的意思是“模板” ，是声明类模板时必须写的关键字。在 template 后面的尖括号内的内容为累的参数列表，关键字 class 表示其后面的是类型参数。在本程序中Type 就是一个类型参数名，它只是一个虚拟类型参数名，在之后的主函数中将被实际的类型名取代。沈阳理工大学课程设计44.2 类的实现template /直接插入排序 void Sort:InsertionSort() int i,j;

15、for(i=2;i=len;+i) if(arrayiarrayi-1) array0=arrayi; for(j=i-1;array0arrayj;-j) arrayj+1=arrayj; arrayj+1=array0; template /2-路插入排序void Sort:Srsort(Type mi) int i,j; Type m,first,final,low,high; Type d100; d1=array1; first=1;final=1;m=1; for(i=2;i=len;+i) m=(first+final)/2; if(arrayidm) low=first;hig

16、h=m-1; else low=m;high=final; while(low=high) /查找插入位置 m=(low+high)/2; 沈阳理工大学课程设计5 if(arrayidm) m+; for(j=final+1;jm;j-) dj=dj-1; dm=arrayi; final+; j=first; for(i=1;i=len;+i) arrayi=dj;+j; template /希尔排序void Sort:Shellinsert(Type dk) int i,j; for(i=dk+1;i=len;+i) if(arrayi0&(array0arrayj);j-=dk)

17、 arrayj+dk=arrayj; arrayj+dk=array0; templatevoid Sort:ShellSort(Type da,int t)int k; k=len/2; while(k) 沈阳理工大学课程设计6 Shellinsert(k); k=k=2?1:k/2;template /读入数组void Sort:write() int i,l;printf(请输入数组长度:); scanf(%d,&l); len=l; printf(请输入数组元素:n); for(i=1;iarrayi;template /显示结果void Sort:print() int i;

18、 printf(排序后的数组为:n); for(i=1;i=len;i+) coutarrayi ; coutendl;在类模板外定义成员函数时，应写成类模板形式。不论成员函数在类内定义还是在类外定义，成员函数的代码段都用同一种方式储存，即都不占用对象的存储空间。一个对象所占的空间大小只取决于该对象中数据成员所占的空间，而与成员函数无关。函数代码是存储在对象空间之外的。4.3 主函数设计void main() int i,j; Sort s; Sort p; couti;if(i=j) s.write(); couti; switch(i) case 1:s.InsertionSort();b

19、reak; case 2:s.Srsort(s.array);break; case 3:s.ShellSort(s.array,3);break; default:break; s.print(); else p.write(); couti; switch(i) case 1:p.InsertionSort();break; case 2:p.Srsort(p.array);break; case 3:p.ShellSort(p.array,3);break; default:break; p.print();在程序的主函数部分，建立了两个实际的类对象 s 和 p，实际类型参数分别为 in

20、t型和 char 型。首先通过选择参数类型来调用读入数组函数，进行数据的输入。其次选择排序类型，根据所选的类型调用相应的排序函数进行排序。最后通过输出函数输出排序之后的数据，完成整个程序的编译。沈阳理工大学课程设计84.4 基于控制台的应用程序测试程序运行结果如图 4.1 所示。 图 4.1 数组长度为 10 的 int 型数据直接插入排序图 上述结果所应用的排序方法是直接插入排序，接下来下图 4.2，图 4.3 是分别运用2-路插入排序和希尔排序的结果。沈阳理工大学课程设计9 图 4.2 数据长度为 10 的 char 型数据 2-路插入排序图 图 4.3 数组长度为 8 的 int 型数据

21、希尔排序图沈阳理工大学课程设计10从上述三个图中很容易看出三种排序方法程序运行的正确性。无论是 int 型还是char 型都能通过所选的排序方法进行正确的排序。5 基于 MFC 的应用程序MFC 是一个界面开发系统，它提供的类绝大部分界面开发，关联一个窗口的动作。MFC 是 WindowsAPI 的封装，大大简化了我们的工作。DOS 界面程序采用字符交互式实现数据输入输出，主要通过 cin，cout 等 I/O 流实现，而 MFC 的图形程序界面采用标准 Windows 窗口和控件实现输入输出，因此必须在 MFC 类的框架下加入上面所设计的排序算法程序，并通过图形界面的输入输出改造来完成。5.

22、1 基于 MFC 的应用程序设计5.1.1 MFC 程序界面设计首先在 VC 中建立 MFC AppWizard（exe）工程，名称为 PaixuMFC，并在向导的Step1 中选择基本对话框，即建立基于对话框的应用程序，如下图 5.1，图 5.2 所示。沈阳理工大学课程设计11 图 5.1 建立 MFC AppWizard（exe）工程，名称为 PaixuMFC 图 5.2 建立基于对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 5.3 所示。 图 5.3 利用工具箱建立基本界面图 5.3 所示的界面中包含了 3 个 Static Text 控件，3 个 Butto

23、n 控件，和 10 个 Edit Box 控件，控件的基本信息列表如下表 5.1 所示。沈阳理工大学课程设计12 表 5.1 控件的基本信息5.1.2 MFC 程序代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为 10 个 Edit Box 控件建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选择 Member Variables 选项卡，可显示成员变量设置界面，如图 5.4 所示控件类别控件 ID控件 Caption说明课程设计-插入排序输入数组数据Static TextIDC_STATIC输出排序结果IDC_BUTTON

24、1直接插入排序IDC_BUTTON22-路插入排序BottonIDC_BUTTON3希尔排序IDC_EDIT1 IDC_EDIT5输入的五个数据Edit BoxIDC_EDIT6 IDC_EDIT10输出排序之后的五个数据沈阳理工大学课程设计13 图 5.4 设置成员变量通过该界面设置与 10 个 Edit Box 控件对应的成员变量，具体如表 5.2 所示。 表 5.2 控件基本信息控件 ID成员变量类型成员变量名称IDC_EDIT1 IDC_EDIT5intm_w1m_w5IDC_EDIT6 IDC_EDIT10intm_w6m_10下面是编写代码的重要阶段，可以借鉴在设计基于 DOS 界

25、面的控制台应用程序的代码，并将其作必要的改写，具体内容如下。编写直接插入排序按钮的消息处理函数，实现数据排序，具体代码如下：void CPaixuMFCDlg:OnButton1() int a10;int len=5; int i,j; UpdateData(true);a1=m_w1;a2=m_w2; a3=m_w3; a4=m_w4; a5=m_w5; for(i=2;i=len;+i) if(aiai-1) a0=ai; for(j=i-1;a0aj;-j) aj+1=aj; aj+1=a0; for(i=0;i=len;i+)printf(%d,ai); m_w6=a1; m_w7=

26、a2; m_w8=a3; m_w9=a4;沈阳理工大学课程设计14 m_w10=a5; UpdateData(false);编写 2-路插入排序按钮的消息处理函数，实现数据排序，具体代码如下：void CPaixuMFCDlg:OnButton2() int a10; int len=5; int i,j; UpdateData(true);a1=m_w1;a2=m_w2; a3=m_w3; a4=m_w4; a5=m_w5;int low,high;int d100; d1=a1; int first=1;int final=1;int m=1; for(i=2;i=len;+i) m=(f

27、irst+final)/2; if(aidm) low=first;high=m-1; else low=m;high=final; while(low=high) m=(low+high)/2; if(aidm) m+; for(j=final+1;jm;j-) dj=dj-1; dm=ai; final+; j=first; for(i=1;i=len;+i) ai=dj;+j; for(i=1;i=len;i+)printf(%d,ai); m_w6=a1; m_w7=a2; m_w8=a3; m_w9=a4; m_w10=a5; UpdateData(false);编写希尔排序按钮的消

28、息处理函数，实现数据排序，具体代码如下：void CPaixuMFCDlg:OnButton3() int a10;int len=5; int i,j; UpdateData(true); a1=m_w1;a2=m_w2; a3=m_w3;沈阳理工大学课程设计16 a4=m_w4; a5=m_w5; int k=len/2; while(k) for(i=k+1;i=len;+i) if(ai0&(a0aj);j-=k) aj+k=aj; aj+k=a0; k=k=2?1:k/2;for(i=1;i=len;i+)printf(%d,ai);m_w6=a1;m_w7=a2; m_w8

29、=a3; m_w9=a4; m_w10=a5;UpdateData(false);5.25.2 基于基于 MFCMFC 的应用程序测试的应用程序测试运行程序后，首先出现的界面如图 5.5 所示。沈阳理工大学课程设计17 图 5.5 程序运行界面然后再输入数据如图 5.6 图 5.6 输入排序数据 单击直接插入排序按钮，实现排序并将排序结果显示出来，如图 5.7 所示。沈阳理工大学课程设计18 图 5.7 显示直接插入排序结果 第二次输入数据，单击希尔排序按钮，实现排序并将排序结果显示出来，如图 5.8所示。 图 5.8 希尔排序结果图沈阳理工大学课程设计19 图 5.9 直接插入排序结果图单击

30、确定或取消按钮后，程序能够正常实现退出。 由于是初次进行 MFC 方面的设计，所以在程序实现过程中遇到了不少问题，比如在希尔排序过程中利用到了函数的调用，这一点在刚开始时连续出错，但是最终还是解决了问题，成功运行了程序，实现了三种插入排序。通过这次课程设计，对 MFC 相关的只是也掌握了不少。沈阳理工大学课程设计20结结 论论 程序的关键在于建立一个虚拟类模板，然后再类模板中声明各成员函数，这些成员函数在类模板外进行定义，这里要特别注意在类模板外定义成员函数的方法。除了类模板的基本特征之外，结合问题的实际需要，三种排序方法的算法要具备正确性，可读性，健壮性。在类模板外定义成员函数时，应写成类模板形式。不论成员函数在类内定义还是在类外定义，成员函数的代码段都用同一种方式储存，即都不占用对象的存储空间。一个对象所占的空间大小只取决于该对象中数据成员所占的空间，而与成员函数无关。函数代码是存储在对象空间之外的。