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

《数据结构-课程设计报告(排序算法比较).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、clude#defineMAXSIZE1000intL[MAXSIZE+1];intnum=100;intcount1=0,count2=0,count3=0,count4=0,count5=0,count6=0,count7=0,count8=0,count9=0,count10=0;intcreatdata()//产生随机数{FILE*f;introw;row=num/10;f=fopen("O_data.txt","wt");//创建并写入产生的随机数if(f){for(inti=0;i<10;i++)//控制列{for(intj=0;j

5、ntf(f,"%2dt",rand()%100);//调用rand()函数控制为两位数}fprintf(f,"");}fclose(f);}return0;}voidzjpx(intL[MAXSIZE])//直接插入排序{creatdata();inti,j;for(i=2;i<=num;i++)//从第二个开始插入{if(L[i]<=L[i-1]){L[0]=L[i];//设置哨兵并记录要插入的值L[i]=L[i-1];count2=count2+2;//如果if成立则此处关键字移动for(j=i-2;(L[0]

6、t1++;//此处关键字比较count2++;//如果两次if成立则此处关键字移动}//记录后移L[j+1]=L[0];//插入到正确位置count2++;}count1++;}printf("直接排序后的结果是:关键字比较了%d次关键字移动了%d次",count1,count2);for(i=2;i<=num;i++){printf("%2d",L[i]);if(i%10==0)printf("");}}voidzbpx(intL[MAXSIZE])//折半插入排序{creatdata();inti,j,m,low,high;//定义标志for(i=2;i<=num;++i

7、)//从第二个开始插入{L[0]=L[i];count4++;//此处关键字移动low=1,high=i-1;while(low<=high)//寻找插入位置{m=(low+high)/2;//折半找到位置if(L[0]