数据结构课程设计.docx

武汉理工大学数据结构课程设计说明书课程设计任务书学生姓名： 胡达 专业班级： 计算机0708班 指导教师： 高曙 工作单位： 计算机科学系 题 目: 快速、冒泡排序算法比较 初始条件： 试通过随机数据比较快速排序、起泡排序各算法的关键字比较次数和关键字移动次数。（1）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（2）最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。（3）对冒泡排序应指出进行了多少趟。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月X日X时到计算中心检查程序、交课程设计报告、源程序（CD光盘）。指导教师签名： 2009年07月26日系主任（或责任教师）签名： 年 月 日快速、冒泡排序的算法比较1.问题分析和任务定义1.1问题分析 编程实现快速、冒泡两种排序算法，两者之间的算法好坏比较主要有两个方面：数据比较次数和数据移动次数。在该程序中，首先对两种排序算法进行实现，然后再进行比较。1.2任务定义 1.2.1 快速排序定义 快速排序也叫做分区排序，是目前应用最广泛的排序算法。它采用分治法进行排序。其基本思想是任取待排序元素序列中的某个元素（例如取第一个元素）作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列；左侧子序列中所有元素的排序码都小于基准元素的排序码，右侧子序列中所有元素的排序码都大于或等于基准元素的排序码，基准元素则排在这两个子序列中间。然后分别对这两个子序列重复实行上述方法，直到所有的元素都排在相应的位置上为止。 1.2.2 冒泡排序定义 冒泡排序又称起泡排序，它也是一种简单实用的排序方法。其基本思想是通过相邻记录之间关键字的比较和交换，使关键字值较小的记录逐渐的从底部移向顶部，即从下标较大的单元移向下标较小的单元，就像水底的气泡一样逐渐向上冒；而关键字较大的记录就像石块往下沉一样，每一趟有一块“最大”的石头沉到水底。2.开发平台处 理 器：Intel Pentium 4 2.4GHz物理内存：512M操作系统：Microsoft Windows XP开发环境：Microsoft Visual Studio.NET 20033.程序设计 3.1快速排序 3.1.1排序表的类定义datalist.h#ifndef DATALIST_H#define DATALIST_H#include const int DefaultSize = 100;template class dataList template class Element friend class dataList;private: Type key; /排序码 field otherdata; /其它数据成员 public: Element ( ) : key(0), otherdata(NULL) Type getKey ( ) return key; /提取排序码 void setKey ( const Type x ) key = x; /修改 Element & operator = /赋值 ( Element& x ) key = x-key; otherdata = x-otherdata; int operator = (Element& x ) return key = x-key; /判this = x int operator = (Element& x ) return key key; /判this x int operator (Element& x ) return key key; /判this (Element& x ) return key x-key; /判this x template class dataList private: Element * Vector; /存储向量 int MaxSize, CurrentSize; /最大与当前个数public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSz; void sort ( ); /排序 void swap ( Element & x, /对换 Element & y ) Element temp = x; x = y; y = temp; 3.1.2快速排序算法的描述QuickSort ( List ) if ( List的长度大于1) 将序列List划分为两个子序列LeftList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList合并为一个序列List; 3.1.3快速排序的算法#include”datalisr.h”template void dataList : QuickSort ( const int left,const int right ) /在序列 leftright 中递归地进行快速排序 if ( left right) int pivotpos = Partition ( left, right ); /划分 /对左序列同样处理 QuickSort ( left, pivotpos-1); /对右序列同样处理 QuickSort ( pivotpos+1, right ); template int dataList : Partition ( const int low, const int high ) int pivotpos = low; /基准位置 Element pivot = Vectorlow; for ( int i = low+1; i = high; i+ ) if ( Vectori pivot ) pivotpos+; if ( pivotpos != i ) Swap ( Vectorpivotpos, Vectori ); /小于基准对象的交换到区间的左侧去 Swap ( Vectorlow, Vectorpivotpos ); return pivotpos; 3.2冒泡排序 #include”datalist.h” template void dataList : BubbleSort ( ) int pass = 1; int exchange = 1; while ( pass = pass; j- ) if ( Vectorj-1 Vectorj ) /逆序 Swap ( Vectorj-1, Vectorj ); /交换 exchange = 1; /标志置为1,有交换 pass+; 4.调试报告 4.1调试程序#include#includedatalist.h#includemaopao.h#includequicksort.husing namespace std;int main()int length,i;coutlength;int *a=new intlength+1;Element e;datalist list1;datalist list2;for(i=1;i=length;i+)ai=e.key=e.otherdata=rand();list1.add(e);cout排序前：endl;for(i=1;i=length;i+)coutait;list1.BubbleSort();list1.print(); cout冒泡排序的比较次数为：list1.getTimes()endl;cout冒泡排序的移动到次数：list1.getKeyMove()endl; list2.QuickSort(1,length-1);list2.print(); cout快速排序的比较次数为：list2.getTimes()endl;cout快速排序的移动到次数：list2.getKeyMove()endl;return 0;4.2调试过程中出现的问题在实验过程中，发现了许多容易忽视的问题，例如，在dataList类中未对BubbleSort()进行声明，则无法再调试程序中进行调用；还有在main函数中直接对list1对象中的函数进行调用，则会发生错误等等。 4.3调试程序产生的结果程序运行界面5.算法效率分析 5.1冒泡排序算法的效率分析最坏的情形是算法执行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序码比较, 执行 n-i 次对象交换。这样在最坏情形下总的排序码比较次数KCN和对象移动次数RMN为：5.2快速排序算法的效率分析通过相关公式以及实验可以证明, 函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。6.经验和体会通过此次试验，我明白了两个方面的知识：学与做方面：在做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。理论永远!=实际。在学排序算法的时候，读了书上的算法描述，觉得自己都会了，考试题目也都做出来了，但真的到编程去实现它的时候，却不是一次就成功的，总会出点差错，循环的边界条件啊，排序表的设计啊，等等，只得一次次改，等到程序终于正确运行的时候，才算真正会了这些算法，理论和实际永远差那么一点，不去做是体会不出来的。坐在电脑前才真正知道自己会不会，眼高手低是要不得的。还有一个收获是知道了什么是面向对象的程序设计方法。选择C+作为实现语言而不是自己学过的也熟悉的C，是想深入掌握一门语言，都说C+面向对象，跟C完全不一样，而以前学习C+时就觉得它跟C是一回事，只不过把换成了，把printf()换成了cout，换汤不换药，即使引进了类，也只不过把函数移进C的结构体，换了个关键字而已，现在真正要用它编程了，想要设计一个合理的类，却发现无从下手，然后就看书上的例子，看有关知识点的讲解，然后想如果是C，该怎么写，在尝试了C+的运算符重载、函数重载、类模板、函数模板、错误处理机制后，才发现C+真的跟C有本质的不同，以前把C+当C来学是彻底的错了，C+的这些机制对C来说是质的飞跃，类是数据更安全，数据与对应数据的特定的操作关系更紧密、多态性是编译器为程序员分担了很多工作，程序员再不必仅为不同的数据类型浪费精力写冗余的代码、错误处理机制使程序在出错时得到更适当的处理，而不是程序崩溃甚至是粗暴地结束程序C+对现实的模拟比C