数据结构-课程设计报告(排序算法比较).doc
《数据结构-课程设计报告(排序算法比较).doc》由会员分享，可在线阅读，更多相关《数据结构-课程设计报告(排序算法比较).doc（18页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告
学院：
计算机科学与工程
专业：
计算机科学与技术
班级：
09级班
学号：
姓名：
指导老师:
时间:
2010年12月
一、课程设计题目：
1、哈夫曼编码的实现
2、城市辖区地铁线路设计
3、综合排序算法的比较
二、小组成员：
三、题目要求：
1．哈夫曼编码的实现
（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。
（2）针对上述统计结果，对各字符实现哈夫曼编码
（3）对任意文章，用哈夫曼编码对其进行编码
（4）对任意文章，对收到的电文进行解码
2．某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线。
（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离
（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。
使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。
（3）输出应该建设的地铁路线及所需要建设的总里程信息。
3．综合排序算法的比较
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。
试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。
（1）对以下各种常用的内部排序算法进行比较：
直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。
（2）待排序的表长不少于100，要求采用随机数。
（3）至少要用5组不同的输入数据做比较：
比较的次数为有关键字参加的比较次数和关键字移动的次数
（4）改变数据量的大小，观察统计数据的变化情况。
（5）对试验统计数据进行分析。
对各类排序算法进行综合评价。
四、项目安排：
1、小组内分工合作
分工：
负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。
合作：
组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。
五、完成自己的任务：
任务：
综合排序算法比较
1.思想实现流程图
开始
初始数据
……
选择排序
快速排序
冒泡排序
希尔排序
折半排序
直接排序
排序优劣
排序结果
统计排序效率
2.代码的实现
#include
#include
#include
#defineMAXSIZE1000
intL[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 {
fprintf（f,"%2d\t",rand（）%100）; //调用rand（）函数控制为两位数
}
fprintf（f,"\n"）;
}
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] {
L[j+1]=L[j];
count1++; //此处关键字比较
count2++; //如果两次if成立则此处关键字移动
} //记录后移
L[j+1]=L[0]; //插入到正确位置
count2++;
}
count1++;
}
printf（"直接排序后的结果是:
\n关键字比较了%d次\n关键字移动了%d次\n",count1,count2）;
for（i=2;i<=num;i++）
{
printf（"%2d",L[i]）;
if（i%10==0）
printf（"\n"）;
}
}
voidzbpx（intL[MAXSIZE]） //折半插入排序
{
creatdata（）;
inti,j,m,low,high; //定义标志
for（i=2;i<=num;++i） //从第二个开始插入
{
L[0]=L[i];
count4++; //此处关键字移动
low=1,high=i-1;
while（low<=high） //寻找插入位置
{
m=（low+high）/2; //折半找到位置
if（L[0] {
high=m-1;
} //判断是否需要移动位置并将折半区间进一步缩小
elselow=m+1;
count3++; //在上次判断的时候已经做了关键字的比较所以比较次数自加
}
for（j=i-1;j>=high+1;j--）
{
L[j+1]=L[j]; //记录后移
count4++; //此处关键字移动
}
L[high+1]=L[0]; //插入记录
count4++; //此处关键字移动
}
printf（"折半插入排序后的结果是:
\n关键字比较了%d次\n关键字移动了%d次\n",count3,count4）;
for（i=2;i<=num;i++）
{
printf（"%2d",L[i]）;
if（i%10==0）
printf（"\n"）;
}
}
voidxepx（intL[MAXSIZE],intnum） //希尔排序
{
creatdata（）;
inttemp;
inti,j,d;
d=num/2; //确定第一次分组
while（d>=1） //在第一组内进行向后的比较
{
for（i=d+1;i<=num;i++） //对各组进行排序
{
temp=L[i];
j=i-d;
count6++; //如果while（d>=1）成立则此处有关键字的移动
while（（j>0）&&（temp {
L[j+d]=L[j];
j=j-d;
count6++; //如果while成立则此处有关键字的移动
}
count5++; //由于组内比较所以此处有关键字的比较
L[j+d]=temp;
count6++; //此处有关键字的移动
}
d=d/2;
}
printf（"\n希尔排序后的结果是:
\n关键字比较了%d次\n关键字移动了%d次\n",count5,count6）;
for（i=2;i<=num;i++）
{
printf（"%2d",L[i]）;
if（i%10==0）
printf（"\n"）;
}
}
voidmppx（intL[MAXSIZE]） //冒泡排序
{
creatdata（）;
intflag=1;
inttemp;
for（inti=1;i<=num&&flag!
=0;i++） //第一层循环排序
{
flag=0;
for（intj=1;j<=（num-i）;j++） //第二层循环排序
{
if（L[j]{
temp=L[j];
L[j]=L[j+1];
L[j+1]=temp; //进行排序
flag=1;
count8=count8+2; //如果if成立则此处有关键字的移动
}
count7++; //由于内部排序上面的if语句此处有关键字的比较
}
}
printf（"\n冒泡排序后的结果是:
\n关键字比较了%d次\n关键字移动了%d次\n",count7,count8）;
for（i=1;i {
printf（"%2d",L[num-i]）;
if（i%10==0）
printf（"\n"）;
}
}
voidxzpx（intL[MAXSIZE]） //选择排序
{
creatdata（）;
inti,j,k,temp;
for（i=1;i {
k=i;
for（j=i+1;j<=num;j++） //查找关键字最小的记录
{
if（L[k] {
k=j;
} //查到最小记录的关键字然后与第一个数互换位置
count9++; //此处有关键字的比较
if（i!
=k）
{
temp=L[i];
L[i]=L[k];
L[k]=temp; //将关键字最小记录与还未排序的第一个数交换
count10+=2; //如果if成立则关键字有移动（!
!
!
此处有问题显然if肯定有成立的时候所以count10会有值但是测试结果一直是0搞不清原因）
}
}
}
printf（"\n选择排序后的结果是:
\n关键字比较了%d次\n关键字移动了%d次\n",count9,count10）;
for（i=1;i {
printf（"%2d",L[num-i]）;
if（i%10==0）
printf（"\n"）;
}
}
/*intpartition（intL[MAXSIZE],intlow,inthigh）
{
inttemp,t;
inti,j,pos,flag;
intchange1,change2;
temp=L[1]; //保存该元素的值
pos=low; //记录当前位置
change1=change2=0; //记录每次比较的起始元素，距离区间头或尾的偏移量
do
{
flag=1; //没有元素交换
for（i=high-change1;i>=pos+1;i--） //在左区间进行比较
{
if（L[i] {
t=L[pos];
L[pos]=L[i];
L[i]=t;
pos=i;flag=0;change1++; //记录新的位置pos,偏移量增加
break;
}
}
if（flag==0） //如果左区间有元素发生移动，则对右区间进行比较
{
flag=1;
for（j=low+change2;j<=pos-1;j++） //从右区间的起始位置开始，一直到基准元素所处的位置
{
if（L[j]>temp）
{
t=L[j];
L[j]=L[pos];
L[pos]=t;
pos=j;flag=0; change2++;break; //如果有元素交换，flag置0，记录新的位置，偏移量增加
}
}
}
}while（flag==0）;
for（i=0;i<=7;i++）
printf（"%d",*（a+i））;
printf（"\n\n"）;
returnpos;
}
voidkspx（intL[MAXSIZE],intb,intt）
{
creatdata（）;
inti;
if（b {
i=partition（L,b,t）; //对区间（b,t）进行第一次划分
kspx（L,b,i-1）; //左区间进行划分
kspx（L,i+1,t）; //右区间进行划分
}
}
*/
voidcompare（intL[MAXSIZE]）
{
printf（"排序方式 直接 折半 希尔 冒泡 选择\n"）;
printf（"比较次数 %4d %4d %4d %4d %4d \n",count1,count3,count5,count7,count9）;
printf（"移动次数 %4d %4d %4d %4d %4d\n",count2,count4,count6,count8,count10）;
}
voidmenu（intL[MAXSIZE]）
{
intx;
printf（"\n1直接排序 4冒泡排序 7比较数据统计\n"）;
printf（""）;
printf（"\n2折半排序 5快速排序（未完成） 0退出\n"）;
printf（""）;
printf（"\n3希尔排序 6选择排序\n"）;
printf（""）;
printf（"\n请输入对应的序号查看结果\n"）;
scanf（"%d",&x）;
if（x>=0&&x<=7）
{
switch（x）
{
case0:
exit（0）;
case1:
zjpx（L）;menu（L）;break;
case2:
zbpx（L）;menu（L）;break;
case3:
xepx（L,num）;menu（L）;break;
case4:
mppx（L）;menu（L）;break;
// case5:
kspx（L,0,10）;menu（L）;break;
case6:
xzpx（L）;menu（L）;break;
case7:
compare（L）;menu（L）;break;
}
}
else
{
printf（"输入有误！
"）;
menu（L）;
}
}
voidmain（）
{
creatdata（）;
FILE*fp;
inti=0;
fp=fopen（"O_data.txt","r"）; //只读
if（fp==NULL） //失败
{
printf（"错误！
"）;
exit
（1）; //中止程序
}
while（!
feof（fp）） //从文件读出数据
fscanf（fp,"%d",&（L[i++]））;
fclose（fp）;
printf（"随机生成的数为:
\n"）;
for（i=0;i {
if（i%10==0）
printf（"\n"）;
printf（"%2d",L[i]）;
}
printf（"\n"）;
menu（L）;
}
3.实验数据分析：
本实验共成功测试了5个排序方法，除了选择排序的关键字比较出现问题外实验结果全部合理正确，在统计关键字比较以及移动的问题上，与预想的结果相差不大，可以认为测试基本成功。
4.算法优劣综合比较：
数据结果表明，在数据量很小的情况下，几种排序算法的效率几乎没有太大差异，当数据量很大时，几种排序的效率差异才较为明显，综合比较之下，希尔排序的效率是最高的，而冒泡排序的效率是最低的，其他各种排序方法会根据数据的不同有稍微的差异。
七夕，只因有你，
总有一些人牵肠挂肚难以忘记，
总有一些日子温暖甜蜜最为珍惜
从春夏到秋冬，从陌生到熟悉，
虽不能时时联系，却总在特别的日子想起你，
七夕快乐，我的朋友。
七夕，只因有你，
因为有你，再苦生活也不觉得累，
再大的险阻也无所畏，
再大的波折也不担忧，
再痛的经历也会忘记，
因为有你，我就拥有了整个世界，
谢谢你出现在我的生命里。
七夕快乐，我的朋友。
七夕，只因有你，
相识，是最珍贵的缘分，
牵挂，是最真挚的心动，
思念，是最美丽的心情，
问候，是最动听的语言，
在这七夕到来之际，最美的祝福送给你，
七夕快乐，我的朋友。
七夕，只因有你，
雨点轻敲窗，风吹散了梦想，
唯有你的模样依旧在脑海里徜徉，
夜深人静时，你占满了心房，
舍半生轻狂，半世时光，
只为拥有一段和你相处的珍贵情缘，
七夕快乐，我的朋友。
七夕，只因有你，
虽然相距很远，但两颗心却紧紧相连
虽然不常见面，音容笑貌犹如眼前，
悄悄的挟一缕情丝，放飞在炎炎夏日
默默的拽一丝牵挂，悬挂在无垠宇宙
静静的捎一声问候，盛开在七夕佳节
七夕快乐，我的朋友。
七夕，只因有你，
祝福，是一种真实的心意，
是一种甘甜的快乐，
是一种浪漫的味道，
是一种温馨的记忆，
是一种美丽的幸福，
更是我们情谊永远不变的纽带，
七夕快乐，我的朋友。
七夕，只因有你，
爱是种体会，即使心碎也觉得甜蜜，
爱是种感受，即使痛苦也觉得幸福，
爱是种缘分，即使分离也觉得快乐，
七夕到了，最真诚的祝福送给你，
七夕快乐，我的朋友。
七夕，只因有你，
愿天下有情人终成眷属，
愿单身人士找到爱的方向，
愿情侣们找到幸福的天堂，
愿夫妻找到温暖的避风巷，
愿岁月抚平生活的忧伤，愿爱的花瓣轻舞飞扬，
升级会员 