数据结构-课程设计报告(排序算法比较)

1、精选优质文档-倾情为你奉上数据结构课程设计报告学院：计算机科学与工程专业：计算机科学与技术班级：09级班学号：姓名：指导老师:时间: 2010年12月一、课程设计题目： 1、哈夫曼编码的实现 2、城市辖区地铁线路设计 3、综合排序算法的比较二、小组成员：三、题目要求：1哈夫曼编码的实现（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。（2）针对上述统计结果，对各字符实现哈夫曼编码（3）对任意文章，用哈夫曼编码对其进行编码（4）对任意文章，对收到的电文进行解码2某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设

2、路线。（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。（3）输出应该建设的地铁路线及所需要建设的总里程信息。3综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。（1）对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。（2）待排序的表长不少于100，要求采用随机数。

3、（3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数（4）改变数据量的大小，观察统计数据的变化情况。（5）对试验统计数据进行分析。对各类排序算法进行综合评价。四、项目安排：1、小组内分工合作分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。五、完成自己的任务：任务：综合排序算法比较1. 思想实现流程图 开始 初始数据 选择排序 快速排序 冒泡排序 希尔排序 折半排序 直接排序 排序优劣 排序结果统计排序效率2.代码的实现#include#include

4、#include#define MAXSIZE 1000int LMAXSIZE+1;int num=100;int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0,count7=0,count8=0,count9=0,count10=0;int creatdata()/产生随机数FILE *f;int row;row=num/10;f = fopen(O_data.txt, wt);/创建并写入产生的随机数 if(f) for(int i=0; i10; i+)/控制列 for(int j=0; jrow; j+) fprintf(

5、f, %2dt, rand()%100);/调用rand()函数 控制为两位数 fprintf(f, n); fclose(f); return 0;void zjpx(int LMAXSIZE)/直接插入排序 creatdata();int i,j; for(i=2;i=num;i+)/ 从第二个开始插入if(Li=Li-1)L0=Li;/设置哨兵 并记录要插入的值Li=Li-1;count2=count2+2;/如果if 成立 则此处 关键字移动for(j=i-2;(L0Lj);j-)/开始向前寻找Lj+1=Lj;count1+;/此处关键字比较count2+;/如果两次if成立 则此处关

6、键字移动/记录后移 Lj+1=L0; /插入到正确位置 count2+;count1+; printf(直接排序后的结果是:n关键字比较了%d次n关键字移动了%d次n ,count1,count2); for(i=2;i=num;i+) printf(%2d ,Li);if(i%10=0)printf(n);void zbpx(int LMAXSIZE)/折半插入排序 creatdata();int i,j,m,low,high;/定义标志 for(i=2;i=num;+i)/ 从第二个开始插入 L0=Li;count4+;/此处关键字移动low=1,high=i-1; while(low=h

7、igh)/寻找插入位置 m=(low+high)/2;/折半 找到位置 if(L0=high+1;j-)Lj+1=Lj;/记录后移count4+;/此处 关键字 移动Lhigh+1=L0;/插入记录count4+;/此处关键字 移动 printf(折半插入排序后的结果是:n关键字比较了%d次n关键字移动了%d次n ,count3,count4); for(i=2;i=1)/在第一组内进行向后的比较for(i=d+1;i=1）成立 则此处有关键字的移动while(j0)&(tempLj)/对组内进行排序Lj+d=Lj;j=j-d;count6+;/如果 while 成立 则此处有关键字的移动co

8、unt5+;/由于组内比较 所以此处有关键字的比较Lj+d=temp;count6+;/此处有关键字的移动d=d/2;printf(n希尔排序后的结果是:n关键字比较了%d次n关键字移动了%d次n ,count5,count6); for(i=2;i=num;i+)printf(%2d ,Li);if(i%10=0)printf(n );void mppx(int LMAXSIZE)/冒泡排序creatdata(); int flag=1;int temp; for(int i=1;i=num & flag!=0;i+)/第一层循环排序 flag=0; for(int j=1;j=(num-i

9、);j+)/第二层循环排序 if(LjLj+1) temp = Lj; Lj = Lj+1; Lj+1 = temp;/进行排序 flag=1;count8=count8+2;/如果if成立 则此处有关键字的移动 count7+;/由于内部排序上面的if语句 此处有关键字的比较 printf(n冒泡排序后的结果是:n关键字比较了%d次n关键字移动了%d次n ,count7,count8); for(i=1;inum;i+)printf(%2d ,Lnum-i);if(i%10=0)printf(n );void xzpx(int LMAXSIZE)/选择排序creatdata();int i,

10、j,k,temp;for(i=1;inum;i+)/第一趟循环寻找最小记录k=i;for(j=i+1;j=num;j+)/查找关键字最小的记录if(LkLj)k=j;/查到最小记录的关键字然后与第一个数互换位置count9+;/此处有关键字的比较if(i!=k)temp=Li;Li=Lk;Lk=temp;/将关键字最小记录与还未排序的第一个数交换count10+=2;/如果if成立 则关键字有移动（!此处有问题 显然if肯定有成立的时候 所以count10会有值 但是测试结果一直是0 搞不清原因）printf(n选择排序后的结果是:n关键字比较了%d次n关键字移动了%d次n ,count9,c

11、ount10); for(i=1;i=pos+1;i-) /在左区间进行比较if(Litemp)t=Lpos;Lpos=Li;Li=t;pos=i; flag=0; change1+;/记录新的位置pos,偏移量增加break;if(flag=0) /如果左区间有元素发生移动，则对右区间进行比较flag=1; for(j=low+change2;jtemp)t=Lj;Lj=Lpos;Lpos=t;pos=j; flag=0;change2+;break; /如果有元素交换，flag置0，记录新的位置，偏移量增加while(flag=0);for(i=0;i=7;i+)printf(%d ,*(

12、a+i);printf(nn);return pos; void kspx(int LMAXSIZE,int b,int t)creatdata();int i;if(b=0&x=7)switch(x)case 0:exit(0);case 1:zjpx(L);menu(L);break;case 2:zbpx(L);menu(L);break;case 3:xepx(L,num);menu(L);break;case 4:mppx(L);menu(L);break;/case 5:kspx(L,0,10);menu(L);break;case 6:xzpx(L);menu(L);break;

13、case 7:compare(L);menu(L);break;else printf(输入有误！);menu(L);void main()creatdata();FILE* fp;int i=0;fp=fopen(O_data.txt,r);/只读if(fp=NULL)/失败printf(错误！);exit(1);/中止程序 while(!feof(fp)/从文件读出数据fscanf(fp,%d,&(Li+); fclose(fp);printf(随机生成的数为:n);for(i=0;inum;i+)if(i%10=0)printf(n);printf(%2d ,Li);printf(n);

14、menu(L);3. 实验数据分析：本实验共成功测试了5个排序方法，除了选择排序的关键字比较出现问题外 实验结果全部合理正确，在统计关键字比较以及移动的问题上，与预想的结果相差不大，可以认为测试基本成功。4. 算法优劣综合比较：数据结果表明，在数据量很小的情况下，几种排序算法的效率几乎没有太大差异，当数据量很大时，几种排序的效率差异才较为明显，综合比较之下，希尔排序的效率是最高的，而冒泡排序的效率是最低的，其他各种排序方法会根据数据的不同有稍微的差异。七夕，只因有你，总有一些人牵肠挂肚难以忘记，总有一些日子温暖甜蜜最为珍惜从春夏到秋冬，从陌生到熟悉，虽不能时时联系，却总在特别的日子想起你，七夕

15、快乐，我的朋友。七夕，只因有你，因为有你，再苦生活也不觉得累，再大的险阻也无所畏，再大的波折也不担忧，再痛的经历也会忘记，因为有你，我就拥有了整个世界，谢谢你出现在我的生命里。七夕快乐，我的朋友。七夕，只因有你，相识，是最珍贵的缘分，牵挂，是最真挚的心动，思念，是最美丽的心情，问候，是最动听的语言，在这七夕到来之际，最美的祝福送给你，七夕快乐，我的朋友。七夕，只因有你，雨点轻敲窗，风吹散了梦想，唯有你的模样依旧在脑海里徜徉，夜深人静时，你占满了心房，舍半生轻狂，半世时光，只为拥有一段和你相处的珍贵情缘，七夕快乐，我的朋友。七夕，只因有你，虽然相距很远，但两颗心却紧紧相连虽然不常见面，音容笑貌犹如眼前，悄悄的挟一缕情丝，放飞在炎炎夏日默默的拽一丝牵挂，悬挂在无垠宇宙静静的捎一声问候，盛开在七夕佳节七夕快乐，我的朋友。七夕，只因