数据结构 课程设计报告（排序算法比较）

数据结构课程设计报告

学院：计算机科学与工程 专业：计算机科学与技术 班级：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

#define MAXSIZE 1000 int L[MAXSIZE+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(\ 入产生的随机数 if(f) { for(int i=0; i<10; i++) { for(int j=0; j

void zjpx(int L[MAXSIZE]) 排序 { creatdata(); int i,j;

for(i=2;i<=num;i++) 二个开始插入 { if(L[i]<=L[i-1]) { L[0]=L[i]; 哨兵 并记录要插入的值 L[i]=L[i-1];

//产生随机 //创建并写 //控制列 //调用rand()函数 //直接插入 // 从第 //设置

count2=count2+2; //如果if 成立 则此处 关键字移动 for(j=i-2;(L[0]

printf(\直接排序后的结果是:\\n关键字比较了%d次\\n关键字移动了%d次\\n \

for(i=2;i<=num;i++) { printf(\ if(i==0) printf(\ } }

void zbpx(int L[MAXSIZE]) //折半插入排序 { creatdata(); int i,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]

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 \

for(i=2;i<=num;i++) { printf(\ if(i==0) printf(\ } }

void xepx(int L[MAXSIZE],int num) //希尔排序 { creatdata(); int temp; int i,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

for(i=2;i<=num;i++) { printf(\ if(i==0) printf(\ } }

void mppx(int L[MAXSIZE]) //冒泡排序 { creatdata(); int flag=1; int temp;

for(int i=1;i<=num && flag!=0;i++) //第一层循环排序 {

flag=0;

for(int j=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关键字比较了%d次\\n关键字移动了%d次\\n \

for(i=1;i

void xzpx(int L[MAXSIZE]) //选择排序 { creatdata(); int i,j,k,temp; for(i=1;i

count9++; //此处有关键字的比较 if(i!=k) { temp=L[i]; L[i]=L[k]; L[k]=temp; //将关键字最小记录与还未排序的第一个数交换 count10+=2; //如果if成立 则关键字有移动（!!!此处有问题 显然if肯定有成立的时候 所以count10会有值 但是测试结果一直是0 搞不清原因） } } } printf(\选择排序后的结果是:\\n关键字比较了%d次\\n关键字移动了%d次\\n \

for(i=1;i

/*int partition(int L[MAXSIZE],int low,int high) { int temp,t; int i,j,pos,flag; int change1,change2; temp=L[1]; //保存该元素的值 pos=low; //记录当前位置 change1=change2=0; //记录每次比较的起始元素，距离区间头或尾的偏移量 do { flag=1; //没有元素交换 for(i=high-change1;i>=pos+1;i--) //在左区间进行比较 {

if(L[i]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(\ \ printf(\ return pos; }

void kspx(int L[MAXSIZE],int b,int t) { creatdata(); int i; if(b

行划分

//记录新的

//如果

//从右区间

//如果有元素交

//对区间(b,t)

//左区间进

本文来源：https://www.bwwdw.com/article/9eo2.html