基于选择排序方法的类模板设计与实现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 需求分析 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 jarray j t array i array i array j array j t 2 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 3 类设计 从上面的算法分析可以看到 本设计面临的问题的关键是类模板 可以定 义一个模板类 sort 模板类 sort 功能有输入 输出数组 用三种方法对数组进 行排序 从问题的需要来看 在模板类中定义三个成员函数 成员函数 SelectSort 对数组进行简单选择排序 成员函数 tree select sort 对数组进 行树形选择排序 成员函数 HeapSort 对数组进行堆排序 成员函数 AdjustTree 通过始建和调整堆辅助堆排序 而成员函数 write 和 print 输入输出数组 主函数中应用 if 判断语句确定数组数据类型 swich 语句 选择使用的排序方法 定义了两个对象分别是整型和字符型的 类用 template 限定 其中的数据类型用 type 代替 所有的成 员函数都用 template 修饰 使之能适用于多种数据类型 4 基于控制台的应用程序 整个程序只用一个独立的文档 文件中包含一个模板类 主函数中定义多 个对象来实现调用三个成员函数对数组进行简单选择排序 树形选择排序 堆 排序这三种排序 在此定义了三个对象分别是整型 字符型和浮点型的 4 1 类的接口设计 include include include include define num 50 define M 50 4 define MIN VALUE 10000 templateclass 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 void Sort SelectSort Type ar int i j Type t for i 1 i len i for j i 1 jarray j t array i array i array j array j t 5 template void Sort 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 1 i 2 6 以 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 如果不是左子结点 7 用子结点中较大值代替父结点 tree maxIndex 2 tree maxIndex tree maxIndex 1 tree maxIndex tree maxIndex 1 maxIndex 2 继续处理父结点 template void Sort 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 if temp array j array i array j array j 调整到双亲结点 i j j 2 i else break array i temp template 8 void Sort 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 void Sort write 输入数组 int i l printf 请输入数组长度 scanf d len l printf 请输入数组元素 n for i 1 i array i template void Sort print 输出数组 int i printf 排序后的数组为 n for i 1 i len i 9 cout array i cout endl 在类的成员函数实现过程中 系统会自动为类产生构造函数 类的构造函 数自动调用 为类动态分配了内存空间 整个调用过程中完全是由系统内部完 成 成员函数对成员变量进行操作 实现排序功能 通过 for 循环 实现输入输 出数组元素的功能 4 3 主函数设计 在程序的主函数部分 选择了分别以 int char 和 float 型为数据类型的对象 作为实际例子来验证算法 首先 选择数据类型 然后 通过 write 函数对 成员变量数组 array 进行赋值 通过 swich 语句选择排序方式 用对象调 用对应的成员函数实现数组排序 最后 通过 print 函数输出排序后的结果 void main 主函数 int i j 1 Sort s Sort p Sort z cout 选择输入类型 1 int 2 char 3 float i if i 1 s write cout 请选择排序方式 1 简单选择排序 2 树形选择排序 3 堆排序 i switch i 10 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 堆排序 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 堆排序 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 11 z print 4 4 基于控制台的应用程序测试基于控制台的应用程序测试 1 用简单选择排序进行 int 类型的排序 图 1 2 用树形选择排序进行 char 类型的排序 图 2 12 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 所示 13 图 4 建立 MFC AppWizard exe 工程 14 图 5 建立基于对话框的应用程序 将对话框资源中的默认对话框利用工具箱改造成如下界面 如图 6 所示 图 6 选择排序方法的实现界面设计 图 3 所示的界面中包含了 2 个 Static Text 控件 3 个 Button 控件 和 10 个 Edit Box 控件 控件的基本信息列表如下表 1 所示 表 1 控件基本信息 输入前 Static TextIDC STATIC 输入后 IDC BUTTON 1简单选择排序 IDC BUTTON 2树形选择排序Botton IDC BUTTON 3堆排序 IDC EDIT m1 IDC EDIT m5输入的 5 个元素 Edit Box IDC EDIT m6 IDC EDIT m10输出的 5 个元素 5 1 2 MFC 程序代码设计 为了能够将对话框界面上的控件能够与代码联系起来 需要为 10 个 Edit 15 Box 控件建立 Member Variables 按 Ctrl w 键进入 MFC ClassWizard 界面 选 择 Member Variables 选项卡 可显示成员变量设置界面 如图 7 所示 图 7 成员变量设置界面 通过该界面设置与 10 个 Edit Box 控件对应的成员变量 具体如表 2 所示 表 2 控件基本信息 控件 ID成员变量类型成员变量名称 IDC EDIT m1 IDC EDIT m5Intm 1 m 5 IDC EDIT m6 IDC EDITm 10Intm 6 m 10 下面是编写代码的重要阶段 1 简单选择排序 int a 5 UpdateData true a 0 m l1 16 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 ja 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 17 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 i1 i 2 tree i 2 tree i tree i 1 tree i tree i 1 18 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 19 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 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 20 UpdateData false 5 2 基于 MFC 的应用程序测试 运行程序后 首先出现的界面如图 8 所示 图 8 程序初始运行界面 单击简单选择排序按钮后 可将输入前的字符进行排序 如图 6 所示 21 图 9 排序后的界面 结 论 本次课程设计 在