数据结构课程设计各种排序算法比较精品资料.doc

《数据结构课程设计各种排序算法比较精品资料.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计各种排序算法比较精品资料.doc（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 程 设 计 课程：数据结构 题目：排序算法比较 专业班级： 姓名： 学号： 设计时间： 指导教师：一、 设计题目排序算法比较二、 运行环境（软、硬件环境）操作系统windows运行环境vc6.0三、 算法设计的思想大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。总体算法思想为按功能分块，依照预想功能实现顺序拼装。具体思想请见流程图。四、 流程图开始功能流程图请用户输入将要生成随机数的上下限，按照上下限生成30000个随机数并输出随机生成

2、随机数并输出请用户选择想要使用的排序方法计算其使用的排序时间并输出询问用户是否继续运行程序否是输出结束语句结束程序编写流程图开始定义全局变量a30000,aaaa3000,结构体数组aa30000用来存放随机数，choice，choice1编写各个子算法子函数，和时间选择函数，既菜单选择函数，部分需要声明的函数在头文件下声明。各模块依据功能流程图组装结束算法流程图开始局部变量l，h收集上下限，sjs（）将用户选择数值赋值于choice，将choice作为参数调用time（），用if语句判断选择将要调用的算法子函数main1（）menu（）choice1=1Choice1=2结束五、 算法设计分

3、析 程序总体采用模块化设计，程序间通过传参和调用进行有机组合。这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。六、 源代码#include#include#includeint a30000;int choice;int choice1;struct xlxint key;int link; aa30000;int aaa300000;void main1();/*直接插入排序函数*/void direct(in

4、t a)printf(n现在使用直接插入排序法进行排序:n);int i,j,w; for(i=0;i=0;j-) if(aj=aj+1) w=aj; aj=aj+1; aj+1=w; /*冒泡排序函数*/void bubble_sort(int a) printf(n下面使用冒泡排序法进行排序:); int i,j,w; for(i=0;i30000;i+) for(j=0;jaj+1) w=aj; aj=aj+1; aj+1=w; /*选择排序*/void choices_sort(int a) printf(n现在使用选择排序法进行排序:n); int i,j,k,t; for(i=0;

5、i30000;i+) k=i; for(j=i+1;jaj) k=j; t=ai; ai=ak; ak=t; /*快速排序*/ quick(int first,int end,int L) int left=first,right=end,key; key=Lfirst; while(leftright) while(left=key) right-; if(leftright) Lleft+=Lright; while(leftright)&(Lleft=key) left+; if(leftright)Lright-=Lleft; Lleft=key; return left; void

6、quick_sort(int L,int first,int end) int split; if(firstend) split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); /*堆排序*/void sift(int *x, int n, int s) int t, k, j; t = *(x+s); /*暂存开始元素*/ k = s; /*开始元素下标*/ j = 2*k + 1; /*右子树元素下标*/ while (jn) if (jn-1 & *(x+j) *(x+j+1) /*

7、判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/ j+; if (t=0; i-) sift(x,n,i); /*初始建堆*/ for (k=n-1; k=1; k-) t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /*剩下的数再建堆*/ /*归并排序*/int listmerge(struct xlx list,int first,int second)/*递归传递*/int start=30000;while(first!=-1&second!=-1)if(listfirst.key=upper)

8、return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*时间计算函数*/void timer(int choice)double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=3) choices_sort(a);if(choice=4) printf(n现在使用快速排序法

9、进行排序:n); quick_sort(a,0,29999); if(choice=5) heap_sort(a,30000);if(choice=6) rmerge(aa,0,29999);t2=(double) clock();t=difftime(t2,t1)/1000;for(i=0;i30000;i+) printf(%d ,ai);printf(n排序结束您所用排序时间为：%f秒n,t);/*菜单函数*/void menu(int choice1) int i;if (choice1=1) for(i=0;i=30000;i+)ai=aaai;aai.key=aaai;main1(

10、);if (choice1=2)printf(谢谢使用，再见！);/*生成随机数函数*/void sjs()int i=0,j,b,h,l;printf(请输入你所期望的将要生成随机数的取值范围：n);printf(最小值（不能为负数）：);scanf(%d,&l);printf(最大值（无上限）：);scanf(%d,&h);srand( (int) time(0);for(j=0;i=l&b=h)ai=b;aai.key=b;aaai=b;i+;for(i=0;i=1; k-) t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift

11、(x,k,0); /*剩下的数再建堆*/ /*归并排序*/int listmerge(struct xlx list,int first,int second)/*递归传递*/int start=30000;while(first!=-1&second!=-1)if(listfirst.key=upper)return lower;elsemiddle=(lower+upper);return listmerge(list,rmerge(list,lower,middle), rmerge(list,middle+1,upper); /*时间计算函数*/void time(int choice

12、) double t1,t2,t;int i;t1=(double) clock(); if(choice=1) direct(a);if(choice=2) bubble_sort(a);if(choice=3) choices_sort(a);if(choice=4) printf(n现在使用快速排序法进行排序:n); quick_sort(a,0,29999); if(choice=5) heap_sort(a,30000);if(choice=6) rmerge(aa,0,29999);t2=(double) clock();t=difftime(t2,t1)/1000;for(i=0

13、;i30000;i+) printf(%d ,ai);printf(n排序结束您所用排序时间为：%f秒n,t);/*菜单函数*/void menu(int choice1) int i;if (choice1=1) for(i=0;i=30000;i+)ai=aaai;aai.key=aaai;main1();if (choice1=2)printf(谢谢使用，再见！); void main1()printf(nn请选择你所希望使用的排序方法：nn1。直接插入排序n2。冒泡排序n3。选择排序n4。快速排序n5。堆排序n6。归并排序n);scanf(%d,&choice);time(choice

14、);printf(nn排序完毕，请选择下一步您要完成的工作：nn1.返回选择另一种排序方法排序n2.退出n);scanf(%d,&choice1);menu(choice1);/*主函数*/void main()sjs();main1();七、 运行结果分析生成30000个随机数选择使用排序算法直接排序排序所用时间冒泡排序所用时间选择排序所用时间快速排序所用时间 堆排序所用时间各排序排序时间分别为：直接排序：3.448秒冒泡排序：3.76秒选择排序：1.575秒快速排序：0.00秒堆排序：0.016秒归并排序：7.487秒（注：此处快速排序并非排序时间为0，而是时间很短在表示范围外，当实验数据

15、扩大到一定数值后会有相应时间显示）通过数据不难看出6种排序方法处理一组相同数据时，快速排序处理速度最快堆排序次之，归并排序最慢。六课设心得整个程序前前后后整整用了一个星期，每天只要有空闲时间就在翻书本，画流程图，写代码，反反复复一点一点。一个星期的编写让我进步不少，心得也不少，但是说实话让我认识最深的是四点，刻骨铭心：1. 对于编程来说看书很重要，但实实在在的动手去编才是王道！2. 任何程序想要写起来不被自己搞晕，就一定要画流程图，省时省事！3. 编程一定养成良好的编程习惯，无论命名还是结构！4. 任何程序算法是灵魂，程序的好坏很大部分取决于算法，只是一组数的排序差别就如此之大，跟别说一个比排

16、序负责多倍的排序！附录资料:不需要的可以自行删除 libxml2应用实例Libxml2 是一个xml的c语言版的解析器，本来是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或f

17、tp(ftp.xmlsoft.org)站点下载libxml压缩包(libxml2-xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvzf libxml2-xxxx.tar.gz3) 进入解压缩后的文件夹中运行 ./configure -prefix /home/user/myxml/xmlinst(此处为待安装的路径)或者直接使用 ./configure make make install 4) 添加路径 export PATH=/home/user/myxml/xmlinst/bin:$PATH 说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单

18、的代码解析XML文件，包括本地和远程的文件，但是在编码上有一些问题。Libxml默认只支持UTF8的编码，无论输入输出都是UTF-8，所以如果你解析完一个XML得到的结果都是UTF8的，如果需要输出GB2312或者其它编码，需要ICONV来做转码(生成UTF8编码的文件也可以用它做),如果系统中没有安装iconv的话，需要安装libiconv。 1) 下载libiconv压缩包(例如libiconv-1.11.tar.gz) 2) 对压缩包进行解压缩tar xvzf libiconv-1.11.tar.gz 3) 进入解压缩后的文件夹中运行 ./configure make make inst

19、all三、关于XML：在开始研究 Libxml2 库之前，先了解一下XML的相关基础。XML 是一种基于文本的格式，它可用来创建能够通过各种语言和平台访问的结构化数据。它包括一系列类似 HTML 的标记，并以树型结构来对这些标记进行排列。例如，可参见清单 1 中介绍的简单文档。为了更清楚地显示 XML 的一般概念，下面是一个简化的XML文件。清单 1. 一个简单的 XML 文件 root delete 10清单 1 中的第一行是 XML 声明，它告诉负责处理 XML 的应用程序，即解析器，将要处理的 XML 的版本。大部分的文件使用版本 1.0 编写，但也有少量的版本 1.1 的文件。它还定义

20、了所使用的编码。大部分文件使用 UTF-8，但是，XML 设计用来集成各种语言中的数据，包括那些不使用英语字母的语言。接下来出现的是元素。一个元素以开始标记 开始(如 )，并以结束标记 结束(如 )，其中使用斜线 (/) 来区别于开始标记。元素是 Node 的一种类型。XML 文档对象模型 (DOM) 定义了几种不同的 Nodes 类型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子节点。例如，age 元素有一个子元素，即文本节点 10。XML 解析器可以利用这种父子结构来遍历文档，甚至修改文档的结

21、构或内容。LibXML2 是这样的解析器中的其中一种，并且文中的示例应用程序正是使用这种结构来实现该目的。对于各种不同的环境，有许多不同的解析器和库。LibXML2 是用于 UNIX 环境的解析器和库中最好的一种，并且经过扩展，它提供了对几种脚本语言的支持，如 Perl 和 Python。四、Libxml2中的数据类型和函数一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师的话，90%的功能都是由30%的内容提供的。对于libxml2，我认为搞懂以下的数据类型和函数就足够了。1）内部字符类型xmlCharxmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据

22、类型。事实上它的定义是：xmlstring.htypedef unsigned char xmlChar;使用unsigned char作为内部字符格式是考虑到它能很好适应UTF-8编码，而UTF-8编码正是libxml2的内部编码，其它格式的编码要转换为这个编码才能在libxml2中使用。还经常可以看到使用xmlChar*作为字符串类型，很多函数会返回一个动态分配内存的xmlChar*变量，使用这样的函数时记得要手动删除内存。2） xmlChar相关函数如同标准c中的char类型一样，xmlChar也有动态内存分配、字符串操作等相关函数。例如xmlMalloc是动态分配内存的函数；xmlFr

23、ee是配套的释放内存函数；xmlStrcmp是字符串比较函数等等。基本上xmlChar字符串相关函数都在xmlstring.h中定义；而动态内存分配函数在xmlmemory.h中定义。3）xmlChar*与其它类型之间的转换另外要注意，因为总是要在xmlChar*和char*之间进行类型转换，所以定义了一个宏BAD_CAST，其定义如下：xmlstring.h#define BAD_CAST (xmlChar *)原则上来说，unsigned char和char之间进行强制类型转换是没有问题的。4）文档类型xmlDoc、指针xmlDocPtrxmlDoc是一个struct，保存了一个xml的相

24、关信息，例如文件名、文档类型、子节点等等；xmlDocPtr等于xmlDoc*，它搞成这个样子总让人以为是智能指针，其实不是，要手动删除的。xmlNewDoc函数创建一个新的文档指针。xmlParseFile函数以默认方式读入一个UTF-8格式的文档，并返回文档指针。xmlReadFile函数读入一个带有某种编码的xml文档，并返回文档指针；细节见libxml2参考手册。xmlFreeDoc释放文档指针。特别注意，当你调用xmlFreeDoc时，该文档所有包含的节点内存都被释放，所以一般来说不需要手动调用xmlFreeNode或者xmlFreeNodeList来释放动态分配的节点内存，除非你把

25、该节点从文档中移除了。一般来说，一个文档中所有节点都应该动态分配，然后加入文档，最后调用xmlFreeDoc一次释放所有节点申请的动态内存，这也是为什么我们很少看见xmlNodeFree的原因。xmlSaveFile将文档以默认方式存入一个文件。xmlSaveFormatFileEnc可将文档以某种编码/格式存入一个文件中。5）节点类型xmlNode、指针xmlNodePtr节点应该是xml中最重要的元素了，xmlNode代表了xml文档中的一个节点，实现为一个struct，内容很丰富：tree.htypedef struct _xmlNode xmlNode;typedef xmlNode

26、*xmlNodePtr;struct _xmlNode void *_private;/* application data */ xmlElementType type; /* type number, must be second ! */ const xmlChar *name; /* the name of the node, or the entity */ struct _xmlNode *children;/* parent-childs link */ struct _xmlNode *last; /* last child link */ struct _xmlNode *parent;/* child-parent link */ struct _xmlNode *next; /* next sibling link*/ struct _xmlNode *prev; /* previous sibling link