排序算法动态演示系统毕业论文doc

排序算法动态演示系统毕业doc 图书分类号： 密 级： 毕业设计 排序算法研究及动态演示系统开发 SORTING ALGORITHM AND DYNAMIC SYSTEM DEVELOPMENT DEMONSTRATION 学生姓名 学院名称 专业名称 信息与计算科学 指导教师 2009 年 5 月12日 徐州工程学院毕业设计 徐州工程学院学位论文原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用或参考的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标注。 本人完全意识到本声明的法律结果由本人承担。 论文作者签名： 日期： 年 月 日 徐州工程学院学位论文版权书 本人完全了解徐州工程学院关于收集、保存、使用学位论文的规定，即： 本校学生在学习期间所完成的学位论文的知识产权归徐州工程学院所拥有。 徐州工程学院有权保留并向国家有关部门或机构送交学位论文的纸本复印件 和电子文档拷贝，允许论文被查阅和借阅。徐州工程学院可以公布学位论文 的全部或部分内容，可以将本学位论文的全部或部分内容提交至各类数据库 进行发布和检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 论文作者签名： 导师签名： 日期： 年 月 日 日期： 年 月 日 ? 徐州工程学院毕业设计 摘要 排序算法是数据结构这门课程核心内容之一。它是计算机程序设计、数据库、操作系 统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学 习排序算法是为了将实际问题中所涉及的对象在计算机中对它们进行处理。本文首先介绍 排序的一些基本概念和一些常用的排序方法，然后利用VC++开发一个数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法（有冒泡排序、选 择排序、直接插入排序、希尔排序、快速排序、堆排序等）表示出来。该项目在收集各种 排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较， 并以动态演示的方式展示一些经典排序算法运行程。 Visual C++ ； 数据结构排序算法 ；动态演示系统开发 ；算法分析 ? 徐州工程学院毕业设计 Abstract Sorting algorithm is a data structure that one of the core content of courses. It is the design of computer programs, databases, operating systems, compiler theory and an important foundation for artificial intelligence, widely used in information science, various areas of systems engineering. Sorting algorithm is to study the practical problems will be involved in the object expressed in the computer and deal with them. This paper first introduces some basic concepts of sorting and ranking of some commonly used methods, and then use VC + + to develop a data structure of the presentation system; the demonstration system can be operated to the main data structure to sort common sorting algorithm (with bubble sort, select sort, direct insertion sort, Hill sort, quick sort, heap sort, etc.) that come out. The project in order to collect a variety of methods, based on its characteristics, efficiency, applicability to various data sets to do a comprehensive analysis and comparison, and demonstration of the way to the dynamic display of some of the classic run-way sorting algorithm. Keywords VisualC++ Sorting Algorithm Data Structure Dynamic System Development Demonstration Algorithm Analysis ? 徐州工程学院毕业设计 1 绪论 ................................................................................................. 1 1.1研究背景及意义 ......................................................................... 1 1.2研究现状 .................................................................................... 1 1.3本文主要内容 ................................................................................................................ 1 2 排序基本算法..................................................................................................................... 2 2.1排序的基本概念 ............................................................................................................ 2 2.1.1排序 ....................................................................................................................... 2 2.1.2排序分类 ................................................................................................................ 2 2.1.3排序的性能分析 .................................................................................................... 2 2.2内部排序算法简介 ........................................................................................................ 3 2.2.1冒泡排序 ................................................................................................................ 3 2.2.2选择排序 ................................................................................................................ 4 2.2.3插入排序 ............................................................................. 5 2.2.4希尔排序 ................................................................................................................ 6 2.2.5堆排序 .................................................................................................................... 7 2.2.6快速排序 .............................................................................................................. 11 2.3内部排序方法比较 ...................................................................................................... 12 3 软件系统结构设计 ........................................................................................................... 14 3.1性能对比演示功能 ...................................................................................................... 14 3.1.1性能对比演示功能DFD图 ................................................................................... 14 3.1.2性能对比演示功能SC图 ..................................................................................... 15 3.1.3性能对比演示功能具体实现 ............................................................................... 15 3.2算法动画演示功能 ...................................................................................................... 22 3.2.1算法动画演示功能实现 ......................................................................................... 22 3.3 算法代码/伪代码显示功能 ........................................................................................ 24 3.3.1算法代码/伪代码演示功能实现 ............................................................................ 24 4 接口设计 .......................................................................................................................... 26 4.1用户界面原型 .............................................................................................................. 26 4.1.1排序算法性能比较模块 ......................................................................................... 26 4.1.2排序算法动画显示功能模块 ................................................................................. 27 4.1.3排序算法代码/伪代码显示功能模块 .................................................................... 27 5 系统说明 .......................................................................................................................... 28 ? 徐州工程学院毕业设计 6 出错处理设计................................................................................ 29 结论 ................................................................................................... 30 致谢 ................................................................................................... 31 参考文献 ........................................................................................... 32 ? 徐州工程学院毕业设计 1 绪论 1.1 研究背景 排序算法是在整个计算机科学与技术领域上广泛被使用的术语。排序算法是数据结构 这门课程中的主要内容之一。排序算法是计算机程序设计、数据库、操作系统、编译原理 及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。本人在研究各种 算法的过程中，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以 动态演示的方式展示一些经典排序算法运行过程，目的有以下五个方面：做算法的对比研 究，培养研究能力；开发一个独立的软件，培养程序设计和软件开发能力；初步掌握软件 开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学 的理论知识和方法独立分析和解决问题的能力；为教学服务，研究结果可对抽象的《算法 与数据结构》的教学有一定的辅助作用。 1.2 研究现状 随着计算机技术的日益发展，其应用早已不局限于简单的数值运算。而涉及到问题的 分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排 序算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实 的理论、方法和技术基础。近来国内外专家学者们对排序算法又有了新的研究和发现。例 如：我国山东大学的张峰和张金屯两位教授共同研究了《我国植被数量分类和排序研究进 展》这一课题。很值得有关部门去学习和研究。 1.3 本文主要内容 本文首先介绍排序的一些基本概念和一些常用的排序方法，然后利用VC++开发一个 数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法 （有冒泡排序、选择排序、直接插入排序、希尔排序、快速排序、堆排序等）表示出来。 该项目在收集各种排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全 面的分析和比较，并以动态演示的方式展示一些经典排序算法运行程。 1 徐州工程学院毕业设计 排序基本算法 2.1排序的基本概念 2.1.1 排序 排序就是将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。 设个记录的序列为{,,，},其相应关键字序列{,,，},需确定一种？？RKRRKKnnn1212排序,,„,,使其相应的关键字满足递增(升序),或递减(降序)的关系: KPPPp1n12 ,, ,或 ,,,。 KKKKK？？p2pnp1p2pn 2.1.2排序分类 根据排序元素所在位置的不同，排序分为内排序和外排序。 内排序是指在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是 排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、 选择排序、交换排序、归并排序及基数排序等几大类。 外排序是指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存， 只能使用外排序。 2.1.3排序算法的性能评价 （1）执行时间和所需的辅助空间 若排序算法所需的辅助空间并不依赖于问题的规模,即辅助空间是o(1),则称之为n o(n)就地排序(In-Place Sort)。非就地排序一般要求的辅助空间为。 （2）算法本身的复杂程度 排序算法的时间开销：大多数排序算法的时间开销主要是关键字之间的比较和记录的 移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。 2 徐州工程学院毕业设计 2.2内部排序算法简介 这里对以下几种排序方法进行分析和探讨。 2.2.1冒泡排序 1.基本原理 将相邻两个数比较，如果不满足条件（从小到大或从大到小）则交换。 2.排序过程 排序过程如下图2-1所示： 50 40 40 40 40 15 15 40 50 50 50 15 30 30 70 70 70 15 30 40 40 99 75 15 30 50 50 75 15 30 50 50 15 30 50 70 30 50 75 50 99 第 第 第 第 第 第 第 初 一 二 三 四 五 六 始 趟 趟 趟 趟 趟 趟 关 排 排 排 排 排 排 键 序 序 序 序 序 序 字 后 后 后 后 后 后 图2-1 排序过程图 3.算法实现 //冒泡排序的算法实现 void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小 */ {int i,j,temp; for(i=0;ia[j]) { temp=a[i]; a[i]=a [j]; a[j]=temp;}} 4.算法分析 空间效率：仅用了一个辅助单元。 n,1时间效率：总共要进行趟冒泡，对个记录的表进行一趟冒泡需要次关键码jj,1 比较: n1总比较次数= (j,1),n(n,1),2j,2 3 徐州工程学院毕业设计 移动次数： 最好情况下：待排序列已有序，不需移动。 最坏情况下：每次比较后均要进行三次。 n3移动:移动次数= 3(j,1),n(n,1),2,2j 2.2.2 选择排序 1.基本原理 第一趟，从个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个n i记录开始的n,1个记录中再选出关键码最小的记录与第二个记录交换；如此，第趟，则 i从第个记录开始的个记录中选出关键码最小的记录与第 个记录交换，直到整个n,i，1i 序列按关键码有序。 2.排序过程 关键字：12 10 4 20 1 第一趟：1 [10 4 20 12] (将最小值1选出与第一个数12交换位置) 第二趟：1 4 [10 20 12] (剩下的数中找出最小值4与第二个数10交换位) 第三趟：1 4 10 [20 12] (在剩下的数中找出最小值10不要交换) 第四趟：1 4 10 12 20 (在剩下的数中找出最小值12与第四个数20交换位) 3.算法实现 //选择排序的算法实现 void choise(int *a,int n) { int i,j,k,temp; for(i=0;ia[j]) k=j; /*是k总是指向最小元素.*/ if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } } } 4.算法分析 空间效率：仅用了一个辅助单元。 in,1n,i时间效率：总共进行了趟，第趟比较的次数为。 n1(n,i),n(n,1)总比较次数 = ,2i,1 移动次数： 最好情况下：待排序列已有序，不需移动。 3(n,1)最坏情况下：每一趟过程需要移动三次，移动次数=。 4 徐州工程学院毕业设计 2.2.3插入排序 1.基本原理 插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序，再依次把后面 的元素插入适当的位置。把数组元素插完也就完成了排序。 2.排序过程 关键字：[10] 3 25 20 8 第一趟: [3 10] 25 20 8 （将前两个数据排序） 第二趟：[3 10 25] 20 8 （将25放入前面数据中的适当位置） 第三趟：[3 10 20 25] 8 （将20放入适当的位置） 第四趟：[3 8 10 20 25] （将8放入适当的位置） 3.算法实现 //插入排序的算法实现 void insert(int *a,int n) { int i,j,temp; for(i=1;i=0&&temp0&&R[0].key R[j+d]=R[0]； //插入R[i]到正确的位置上 } //endif } //ShellPass void ShellSort(SeqList R) {nt increment=n； //增量初值，不妨设n>0 do { ncrement=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量为increment的Shell插入排序 }while(increment>1) } //ShellSort 6 注意： 徐州工程学院毕业设计 当增量=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环d 中增加了一个循环判定条件“>0”，以防下标越界。 j 4.算法分析 1）增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： ? 最后一个增量必须为1。 ? 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 2）Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因： ?当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 2 ?当值较小时，和的差别也较小，即直接插入排序的最好时间复杂度 nnn 2O()和最坏时间复杂度0()差别不大。 nn ?在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较 快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经di 按-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因di 此，希尔排序在效率上较直接插人排序有较大的改进。 3）稳定性 希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。 2.2.5堆排序 1.基本原理 kk个关键字序列，，，称为堆，当且仅当该序列满足如下性质(简称为堆性？kn12n k,kk,kk,kk,k质)：(1)且 或(2)且。 i2ii2i，1i2ii2i，1 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是 满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 注意： ?堆中任一子树亦是堆。 ?以上讨论的堆实际上是二叉堆，类似地可定义叉堆。 k 7 徐州工程学院毕业设计 2.排序过程 堆排序是一树形选择排序。堆排序的特点是：在排序过程中，将[l]看成是一R？n 棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系， 在当前无序区中选择关键字最大(或最小)的记录。下面将从实际数据中演示其排序中的各 个操作。 原始数组： 22 53 72 11 34 44 11 15 28 3 10 65 第一步，从树顶到树叶把数填充进入，建立堆。红色为下一次交换的两个数（序列）。 22 53 72 11 34 44 11 15 28 3 10 65 使记录递增有序，进一步排序。第一次交换： 22 11 72 53 34 44 11 15 28 3 10 65 第二次交换： 22 11 72 15 34 44 11 53 28 3 10 65 第三次交换： 8 徐州工程学院毕业设计 22 11 72 15 3 44 11 53 28 34 10 65 第四次交换： 22 3 72 15 11 44 11 53 28 34 10 65 第五次交换： 22 3 72 15 10 44 11 第六次交换： 53 28 34 11 65 3 22 72 15 10 44 11 第七次交换： 53 28 34 11 65 9 徐州工程学院毕业设计 3 22 44 15 10 72 11 53 28 34 11 65 第八次交换： 3 22 44 15 10 65 11 53 28 34 11 72 第九次交换： 3 22 11 15 10 65 44 53 28 34 11 72 全程交换完成，得到最小值为3并且输出它。从序列中删除3，重新建立堆。以次循环，直到全部输出完成为止。 3.堆排序与直接插入排序的区别 直接选择排序中，为了从R[1]中选出关键字最小的记录，必须进行-1次比较，？nn R然后在[2]中选出关键字最小的记录，又需要做-2次比较。事实上，后面的-2？nnn 次比较中，有许多比较可能在前面的-1次比较中已经做过，但由于前一趟排序时未保n 留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构 保存部分比较结果，可减少比较次数。 4.算法实现 //堆排序的算法实现 void HeapSort(SeqIAst R) { //对R[1n]进行堆排序，不妨用R[0]做暂存单元 ？10 徐州工程学院毕业设计 int i； BuildHeap(R)； //将R[1-n]建成初始堆 for(i=n;i>1；i--){ //对当前无序区R[1i]进行堆排序，共做n-1趟。 ？ R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1)； //将R[1i-1]重新调整为堆，仅有R[1]可能违反堆性质 ？ } //endfor } //HeapSort 5.算法分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是 通过调用Heapify实现的。堆排序的最坏时间复杂度为o(nlgn)。堆排序的平均性能较接 近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文 件。堆排序是就地排序，辅助空间为，它是不稳定的排序方法。 o(1)2.2.6.快速排序 1.基本原理 首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一 次排序的程序框架。 2.算法实现 void QuickSort(int *pData, int left, int right) {int i, j;nt middle, iTemp;i = left;j = right; middle = pData[(left + right) / 2]; //求中间值 do {while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数 i++; while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数 j--; if (i <= j) //找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++;j--;} } while (i <= j) ; //如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left if(left i)，递归右半边 if(right>i) QuickSort (pData,i,right); } 11 徐州工程学院毕业设计 3.算法分析 (n，logn)6n，logn对于个成员，快速排序法的比较次数大约为次，交换次数大约为n 次。如果为100，冒泡法需要进行4950 次比较，而快速排序法仅需要200 次，快速排n 序法的效率的确很高。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中 间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的 2时间复杂度为，而平均时间复杂度为o(n，logn)。o(n) 2.3内部排序方法比较 在解决实际问题过程中采用的排序算法有很多种，且这些算法各有其优缺点，难以得 出哪个最好，哪个最坏的结论，因此，排序方法的选用应视具体场合而定,下面我们可以 通过一个程序来比较各种排序算法。 #include #include #include main() { int iTest[200],i,temp,j; clock_t lStart,lEnd; double fSeconds; srand((unsigned)time(NULL)); for(i=0;i<=199;i++) iTest[i]=rand()%1000; lStart=clock(); delay(100); //各种排序方法的代码，对iTest[]排序 // lEnd=clock(); fSeconds=(double)(lEnd-lStart)/ CLK_TCK; printf("f=%lf",fSeconds); } 运行程序后，每种排序方法花费的时间保存在fSeconds中。之后只要比较 fSeconds 秒数就可以了。 本程序对各种不同乱序的数据作测试，程序运行正常。分析实测得到的数据，对常用 内部排序的特点作如下的小结如表2-1： 表2-1各种算法时间复杂度比较 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入排O(n2) O(n2 ) O(n ) O(1 ) 稳定 序 12 徐州工程学院毕业设计 直接选择排O(n2) O(n2 ) O(n2 ) O(1 ) 稳定 序 冒泡排序 O(n2) O(n2 ) O(n ) O(1 ) 稳定 快速排序 O(nlog2n) O(n2 ) O(nlog2n ) O(log2n ) 不稳定 堆排序 O(nlog2n) O(nlog2n ) O(nlog2n ) O(1 ) 不稳定 归并排序 O(nlog2n) O(nlog2n ) O(nlog2n ) O(n ) 稳定 3软件系统结构设计 13 软件程序结构图:主要包括三个子模块，分别是性能对比演示功能用户交互模块，算 徐州工程学院毕业设计 法动画演示和算法代码显示功能用户交互模块。如下所示： 用户 算法代码、伪算法动画演示功性能对比功能 代码显示功能能用户交互模块 用户交互模块 用户交互模块 性能对比演算法动画演示功算法代买、伪 示功能逻辑能逻辑处理模块 代码显示功能 处理模块 逻辑处理模块 图3-1 软件结构图 3.1性能对比演示功能 此模块包括两个子模块，分别是排序算法性能对比功能用户交互模块和排序算法性能 对比功能逻辑处理模块。 3.1.1性能对比演示功能DFD图 性能对比演示 用户 功能用户交互 模块 性能对比演示 功能逻辑处理 模块 图3-2 DFD图 14 徐州工程学院毕业设计 3.1.2性能对比演示功能SC图 用户交互模块主要用来提供各种排序算法的选择、数据规模选择、显示排序算法的时 间显示排序前后的数据等功能。而逻辑处理模块主要要来提供自动生成随机测试数据、执 行排序算法、计量排序算法的执行时间的功能。如下图3-3所示： 用户 选择算法种类 列表显示算法运行时间柱状图 显示算法运行时间 选择数据规模 性能对比演示功能用户交互模块 传递算法种类和数据规模 返回各个算法运行后的时间集 性能对比演示功能用户交互模块 排序算法演示系统 图3-3 SC图 3.1.3性能对比演示功能具体实现 1. 设计思想：要求有可视化操作界面，用户与用户交互；用于接收用户的操作信息，包 括： ? 树状控件选择算法种类的选择命令。 ? 单选框选择数据规模的选择命令。 ? 初始化数据的按钮命令。 ? 开始运行算法的按钮命令。 ? 显示排序前/后的测试数据按纽命令。 ? 显示硬件信息的按钮命令。 15 徐州工程学院毕业设计 下面来看具体实现过程： 用一个对话框类来实现用户交互模块。 class ArithmeticSortDialog : public CPropertyPage { DECLARE_DYNCREATE(ArithmeticSortDialog) public: void SetSystemInfo(int IDC_ID, CString ptr_string); void OuttoTree(HTREEITEM m_node); void ShowChart(vector< DWORD > select,vector< Sorttime > sorttime); //柱状图显示排序时间

函数

excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载

int SIZE; vector< DWORD > choice; //存储树形控件选择结果 vector< CString > sortName; //算法的名称 int position; DateProcessModule * pDateProcessModule; //性能对比功能逻辑处理类 ArithmeticSortDialog(); ArithmeticSortDialog(); Dialog Data {{AFX_DATA(ArithmeticSortDialog) enum { IDD = IDD_ARITHMETICSORT_DIALOG }; CListCtrl m_Show_List; //显示测试数据列表控件变量 CListCtrl m_List; //显示排序算法时间列表空间变量 CTreeCtrl m_Sort_Tree; //树状控件变量 CMSChart m_Chart; //柱状图控件变量 }}AFX_DATA Implementation protected: Generated message map functions {{AFX_MSG(ArithmeticSortDialog) virtual BOOL OnInitDialog(); afx_msg void OnInitButton(); //初始化按钮消息相应函数 afx_msg void OnStartButton(); //开始测试按钮消息相应函数 afx_msg void OnShowButton(); //显示数据相应函数 afx_msg void OnStsinfoStatic(); }}AFX_MSG DECLARE_MESSAGE_MAP() }; //初始化树状控件 BOOL ArithmeticSortDialog::OnInitDialog() { CPropertyPage::OnInitDialog(); //将可选的排序算法添加到树状控件之中 //初始化相应排序算法对应的序号 16 徐州工程学院毕业设计 //初始化显示排序算法时间的列表控件 //初始化其他想要的变量 return TRUE; } //数据初始化 void ArithmeticSortDialog::OnInitButton() { //获得用户选择的算法代码集chioce和数据规模SIZE //根据用户选择的排序算法和数据规模 初始化测试数据 //pDateProcessModule = new DateProcessModule(SIZE,choice); //以上调用排序算法性能对比逻辑处理模块 DateProcessModule } //开始测试 void ArithmeticSortDialog::OnStartButton() { //列表框m_List中依次显示排序结果 //根据排序算法时间集pDateProcessModule->m_sorttime //显示直方图控件 ShowChart(choice,pDateProcessModule->m_sorttime); } //显示测试数据 void ArithmeticSortDialog::OnShowButton() //显示内存区数据 { //先清空控件m_Show_List中的数据。 //操作控件m_Show_List显示内存区的测试数据。 } //显示系统及硬件信息 void ArithmeticSortDialog::OnStsinfoStatic() { SystemInfoDialog systemInfo; systemInfo.DoModal(); } //显示排序算法时间的直方图 void ArithmeticSortDialog::ShowChart(vector< DWORD > select,vector< Sorttime > sorttime) { //从参数中得到用户选择的select和性能比较逻辑处理模块返回的sorttime //根据select和sorttime显示直方图 ｝ 2. 设计思想:由上层用户交互模块传递的排序算法种类，由上层用户交互模块传递的排 序算法数据规模。具体实现过程如下： 17 设计类DateProcessModule用于处理性能对比功能逻辑。 class DateProcessModule 徐州工程学院毕业设计 { public: DateProcessModule(int size,vector< DWORD > select); void RandomInit(); //随机数初始化函数 void Perform(int i); //执行函数 //-------------以下是各种排序函数--------------// public: double SelectSort(int *ptr_pData,int ptr_size); double HeapSort(int *ptr_pData, int ptr_size); double BubbleSort(int *ptr_pData, int ptr_size); double Bubble2Sort(int *ptr_pData, int ptr_size); double ExchangeSort(int *ptr_pData, int ptr_size); double ImproveSortBubble(int *ptr_pData, int ptr_size); double QuickSort(int *ptr_pData, int left, int right); double ShellSort(int *ptr_pData, int ptr_size); double DirectSort(int *ptr_pData, int ptr_size); double BInsertSort(int *ptr_pData, int ptr_size); double DeSelsort(int *ptr_pData, int ptr_size); void Merge(int *array, int *arrayTmp, int lPos, int rPos, int rightEnd); void Msort(int *array, int *arrayTmp, int left, int right); void Mergesort(int *array, int size); Timer m_ timer; //记时器 int m_size; //数据规模 int* m_array; //原始数据的首地址 int* m_sparearray; //备份原始数据的首地址 vector< DWORD > m_select; //所选择排序算法代号集合 vector< Sorttime > m_sorttime; //所选排序算法的时间集合 virtual ~DateProcessModule();}; struct Sorttime //记录算法运行时间的结构体 { public: int m_sorttype; //排序算法代号 double m_time; //排序算法时间 int m_size; //数据规模 CString m_sortName; //算法名称 Sorttime(int type, double time, CString name, int size); }; //获取用户交互层传递的数据 Sorttime::Sorttime(int type, double time, CString name, int size) { m_sorttype = type; 18 徐州工程学院毕业设计 m_time = time; m_size = size; m_sortName = name; } //开辟测试存储空间 DateProcessModule::DateProcessModule(int size,vector< DWORD > select) { m_size= ize; m_select =select; m_array =new int[m_size]; m_sparearray =new int[m_size]; RandomInit(); } //初始化测试数据 void DateProcessModule::RandomInit() { int temp; for(int i = 0; i < m_size; i++) { temp = rand()%65535; m_array[i] = temp; m_sparearray[i] = temp; } //根据用户选择参数调用相应的排序算法 void DateProcessModule::Perform(int i) { double t; switch(m_select[i]) { case 1: { //执行Shell排序算法函数 t = ShellSort(m_array, m_size); Sorttime time(m_select[i], t, "Shell排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 2: { //执行直接插入排序算法排序 t = DirectSort(m_array, m_size); Sorttime time(m_select[i], t, "直接插入排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break;} 19 徐州工程学院毕业设计 case 3: { //执行半拆插入排序算法排序 t = BInsertSort(m_array, m_size); Sorttime time(m_select[i], t, "半拆插入排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break;} case 4: { //执行冒泡排序算法函数 t = BubbleSort(m_array, m_size); Sorttime time(m_select[i], t, "冒泡排序（基本）", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 5: { //执行冒泡排序（改进）算法函数 t = ImproveSortBubble(m_array, m_size); Sorttime time(m_select[i], t, "冒泡排序（改进）", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } Case6: { //执行冒泡排序（双向）算法函数 t = Bubble2Sort(m_array, m_size); Sorttime time(m_select[i], t, "冒泡排序（双向）", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 7: { //执行简单交换算法函数 t = ExchangeSort(m_array, m_size); Sorttime time(m_select[i], t, "简单交换", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 8: { //执行快速排序算法函数 m_timer.begin(); 20 徐州工程学院毕业设计 QuickSort(m_array, 0 , m_size-1); t = m_timer.end(); Sorttime time(m_select[i], t, "快速排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 9: { //执行双端选择排序 t = DeSelsort(m_array, m_size); Sorttime time(m_select[i], t, "双端选择排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 10: { //执行堆排序算法函数 t = HeapSort(m_array, m_size); Sorttime time(m_select[i], t, "堆排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 11: { //执行直接选择排序算法函数 t = SelectSort(m_array, m_size); Sorttime time(m_select[i], t, "直接选择排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } Case12: { //执行直接选择排序算法函数 t = SelectSort(m_array, m_size); Sorttime time(m_select[i], t, " 基数排序", m_size); m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } case 13: { m_timer.begin(); Mergesort(m_array, m_size); t= m_timer.end(); Sorttime time(m_select[i], t, "归并排序", m_size); 21 徐州工程学院毕业设计 m_sorttime.push_back(time); //将该算法所用的时间放入算法时间集合中 break; } default: break; } } 3.2算法动画演示功能 输入：用户选择需要动画演示的排序算法。 输出：播放用户选择的排序动画。 功能描述：演示排序算法的动画 3.2.1算法动画演示功能实现 1.算法动画演示功能用户交互模块 用一个对话框类来实现用户交互模块。 class DynamicDemoDialog : public CPropertyPage { DECLARE_DYNCREATE(DynamicDemoDialog) // Construction public: DynamicDemoDialog(); ~DynamicDemoDialog(); // Dialog Data //{{AFX_DATA(DynamicDemoDialog) enum { IDD = IDD_DYNAMICDEMO_DIALOG }; CShockwaveFlash m_swf; //}}AFX_DATA // Overrides // ClassWizard generate virtual function overrides //{{AFX_VIRTUAL(DynamicDemoDialog) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL // Implementation protected: // Generated message map functions //{{AFX_MSG(DynamicDemoDialog) afx_msg void OnBubblesort(); //点击冒泡排序按钮消息相应函数 afx_msg void OnChiocesort(); //点击直接选择排序按钮消息相应函数 afx_msg void OnGuibingsort(); //点击基数排序按钮消息相应函数 afx_msg void OnHeapsort(); //点击堆排序按钮消息相应函数 afx_msg void OnBasesort(); //点击基数排序按钮消息相应函数 22 徐州工程学院毕业设计 afx_msg void OnBarretsort(); //点击桶排序按钮消息相应函数 afx_msg void OnShellsort(); //点击希尔排序按钮消息响应函数 afx_msg void OnQuicksort(); //点击快速排序按钮消息响应哈函数 afx_msg void OnInsertsort(); //点击直接插入排序按钮消息响应函数 //}}AFX_MSG DECLARE_MESSAGE_MAP()}; 2.算法动画演示功能逻辑处理模块 逻辑处理模块由DynamicDemoDialog 的消息处理函数实现： void DynamicDemoDialog::OnBubblesort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnChiocesort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnGuibingsort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnHeapsort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnBasesort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnBarretsort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } 23 徐州工程学院毕业设计 void DynamicDemoDialog::OnShellsort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnQuicksort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 } void DynamicDemoDialog::OnInsertsort() { //读取资源文件中相应的动画资源 //将动画资源文件生成swf格式的动画 //在Flash控件上播放制定的动画 3.3算法代码/伪代码显示功能 输入：用户在树形菜单上选择算法种类；用户选择显示算法代码；用户选择显示算法 伪代码。 输出：显示用户选择的排序算法程序代码；显示用户选择的排序算法伪代码。 功能描述：显示排序算法的程序代码和伪代码。 3.3.1算法代码/伪代码演示功能实现 1.算法代码/伪代码功能用户交互模块 用一个对话框类来实现用户交互模块。 class CShowCodeDialog : public CPropertyPage { DECLARE_DYNCREATE(CShowCodeDialog) // Construction public: CShowCodeDialog(); ~CShowCodeDialog(); DWORD choice; // Dialog Data //{{AFX_DATA(CShowCodeDialog) enum { IDD = IDD_SHOW_CODE_DIALOG }; CTreeCtrl m_tree; //}}AFX_DATA // Overrides // ClassWizard generate virtual function overrides 24 徐州工程学院毕业设计 //{{AFX_VIRTUAL(CShowCodeDialog) protected: virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL // Implementation protected: // Generated message map functions //{{AFX_MSG(CShowCodeDialog) virtual BOOL OnInitDialog(); //初始化树状控件等初始化函数 afx_msg void OnShowPseudoCode(); //显示算法伪代码按钮消息相应函数 afx_msg void OnShowCode(); //显示算法程序代码消息相应函数 afx_msg void OnSelchangedTree1(NMHDR* pNMHDR, LRESULT* pResult); //}}AFX_MSG DECLARE_MESSAGE_MAP()}; 初始化各种排序算法选择的树状控件： BOOL CShowCodeDialog OnInitDialog() { CPropertyPage OnInitDialog(); 1. //将可选的排序算法添加到树状控件之中。 2. //初始化相应排序算法对应的序号。 return TRUE } 2.算法代码/伪代码功能逻辑处理模块 逻辑处理模块由CShowCodeDialog 的消息处理函数实现： //显示排序算法伪代码： void CShowCodeDialog OnShowPseudoCode() { // TODO: Add your control notification handler code here 根据chioce的选择项读取相应的排序算法的伪代码txt文件。 将读取的文本显示在伪代码文本框上 ｝ //显示排序算法程序代码： void CShowCodeDialog::OnShowCode() { // TODO Add your control notification handler code here 根据chioce的选择项读取相应的排序算法的程序代码txt文件。 将读取的文本显示在程序代码文本框上 ｝ 25 徐州工程学院毕业设计 4接口设计 用户界面：采用Windows的通用图形界面，对用户友好，且必须对鼠标键盘提供支持， 界面设计应遵循： 1. 尽量保持一致性：界面

规范

编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载

应遵循MS Windows软件界面的规范。 2. 设计完整的对话过程：系统每次对话都应有明确的次序：开始、中间处理、结束。 3. 提供简单的错误处理机制。 4. 提供信息反馈：信息提示用户当前软件运行状态，软件界面元件的功能。 5. 操作可逆：其动作可以是单个的操作，或者是一个相对独立的操作序列。 4.1用户界面原型 4.1.1排序算法性能比较功能模块 该模块能够提供各种排序算法的选择、数据规模的选择、显示排序算法的时间和显示 测试前后测试数据的功能。 图4-1 性能比较功能模块 26 徐州工程学院毕业设计 4.1.2排序算法动画显示功能模块 该模块能够提供对用户选择的算法进行动画演示的功能。 图4-2 动画显示功能模块图 4.1.3排序算法代码/伪代码显示功能模块 该模块能够提供各种排序算法的选择和显示排序算法的程序代码。 图4-3 伪代码图 27 徐州工程学院毕业设计 5 系统说明 该系统名称：排序算法比较分析及动画演示系统。 该系统组成： 1. 排序算法对比显示模块。 2. 排序算法动画演示模块。 3. 排序算法代码、伪代码演示模块。 本软件主要应用于排序算法课堂上教学，随机生成测试数据，选择数种经常使用排序 算法中的一种的动态演示，还能把该算法的伪代码显示出来；能选择随机生成100、1000、10000、100000、10000000个数据进行各种排序算法需要时间比较，比较的结果通过

表格

关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载

显示和柱状图出来。见表5-1。 表5-1系统模块说明 主模块 模块名称 功能 说明 提供各种排序算法选择 用户可以自行选择需要进行运 行时间对比的排序算法。 提供各种数据规模选择 用户可以自行选择需要排序的 数据规模。 柱状图显示排序算法时间 排序后各个算法的运行时间，以 排序算法性能对柱状图的方式来显示。 比功能用户交互列表框显示排序算法时间 排序后各个算法的运行时间，以 排序算法性模块 列表的方式来显示。 能对比功能 显示原始的测试数据 显示排序前的无序的测试数据 模块 显示排序后的测试数据 显示排序后的有序的测试数据 显示电脑硬件信息 显示当前电脑硬件信息 排序算法性能对自动生成随即测试数据 初始化生成排序测试数据 比功能逻辑处理执行排序算法 依次执行排序算法 模块 计量排序算法运行时间 计量排序算法运行的时间 对用户选择的算法进行动画演可以提供某些算法的动画演示 排序算法动画演示 排序算法动示用户交互模块 画演示功能排序算法动画演读取相应算法的动画 读取动画文件，以供用户交互模 模块 示逻辑处理模块 块来显示 排序算法代码、提供各种排序算法选择 用户可以选择相应的排序算法 伪代码显示用户显示排序算法的伪代码 显示用户选择的排序算法的伪 交互模块 代码 排序算法代显示排序算法的程序代码 显示用户选择的排序算法的程 码、伪代码功序代码 能模块 排序算法代码、读取相应的代码和伪代码 读取代码和伪代码，以供用户交 伪代码显示逻辑互模块来显示 处理模块 28 徐州工程学院毕业设计 6 出错处理设计 以在排序算法性能比较功能模块中出错处理为例：系统运行时，需要人机交互实现用 户所需演示功能。在用户使用时，有时需要输入指定数据。否则，无法执行排序，比较等 功能。在系统设计时，充分考虑了用户误操作的各种可能情况，容错性较好。下面简单介 绍该系统出错处理的设计。 1. 没有选择算法的时候给出错误提示。当用户没有选择排序算法这一选项就进 行下一步操作时，系统会给出错误提示如下图6-1所示： 图6-1 出错提示图 2. 没有选择数据规模的时候给出错误提示。当用户没有选择数据规模这一选项 就进行下一步操作时，系统会给出错误提示如下图6-2所示： 图6-2 出错提示图 29 徐州工程学院毕业设计 结 论 通过几个月的学习和实践，在老师和同学的帮助下我完成了排序算法分析和动态演示 系统。本软件能随机生成测试数据，选择数种经常使用排序算法中的一种的动态演示，还 能把该算法的伪代码显示出来；能选择随机生成数据进行各种排序算法需要时间比较，比 较的结果通过表格显示和柱状图出来。还能够通过动画演示过程将主要排序算法的排序过 程形象的演示出来。从而使学习排序算法变得轻松愉快。对于以上程序在VC++ 6.0中运行正常。通过毕业设计的锻炼，学到了很多东西： ?巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 ?培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问 题、解决问题的能力。 ?过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。 ?够按要求编写毕业设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。 ?通过毕业设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和 全局观念。 毕业设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于 加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固 了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。 30 徐州工程学院毕业设计 致 谢 在这次毕业设计过程中我遇到许多问题和麻烦。例如：论文设计思路不明确，排序软 件无法实现动态演示，论文排版不够合理等。在得到了刘风华老师多次殷切的帮助和指导 下，才能够使得这次毕业设计顺利的进行下去。在刘老师的身上我更是学到了严谨的学术 作风和做研究不怕苦要有韧性的精神。另外，在程序调试过程中，也得到张剑和成飞等多 位同学热心的帮助，给我及时指出错误，帮助我修正并提出许多宝贵的富有建设性的意见。 还有感谢大家网学习论坛的热心网友对于我提出问题的解答。在此对刘老师和同学们以及 热心的网友们表示衷心的感谢！ 31 徐州工程学院毕业设计 参考文献 [1] 严蔚敏.数据结构（C语言版）.北京：清华大学出版社，2005:36-107. [2] Sartaj Sahni. Data Structure Algorithms and Application in C++[J].The McGraw-Hill Company Inc.1998，32（19）：21-58. [3] 朱继红.数据结构算法动态示系统的设计与实现[J].信息工程学院学报，1998,17(14):54-99. [4] 闵联营，何克右.C++程序设计教程[M].武汉：武汉理工大学出版社,2005：28-99. [5] 钟珞.软件工程[M].北京：清华大学出版社，2005：14-23. [6] 张海潘.软件工程导论（第4版）[M].北京：清华大学出版社，2003：103-218. [9] 周靖译.（美）Bruce Eckel .C++面向对象程序设计(第6版).清华大学出版社，2007：32-110. [10] 吕凤翥.C++语言基础教程.清华大学出版社，2000：1-180. [11] 明日科技.Visual C++开发技术大全.人民邮电出版社,2007：49-86. 32 徐州工程学院毕业设计 33