《数据结构》课程设计报告--内部排序的性能化比较与哈弗曼编码.doc
文本预览下载声明
《数据结构》
课程设计报告
题 目： 内部排序的性能比较与哈弗曼编码
学 院： 商学院
专 业： 信息管理与信息系统
班 级： 信息092
学 号：
姓 名：
同组成员：
指导教师：
完成日期： 2010年01月13日
目 录
目 录 2
一、问题描述 3
1.1哈弗曼编码 3
1.2内部排序性能分析 3
二、问题分析 3
三、数据结构描述 4
四、算法设计 5
4.1希尔排序流程图： 5
五、详细程序清单 7
六、程序运行结果 17
七、心得体会 19
一、问题描述
1.1哈弗曼编码
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
(2)编码：利用建好的哈夫曼树生成哈夫曼编码；
(3)输出编码；
1.2内部排序性能分析
设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序算法的关键字比较次数和移动次数以取得直观感受（待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动））。
二、问题分析
我负责的是内部排序之中希尔排序的性能比较，先设计出希尔排序的排序原理，框架结构，然后设计程序代码，合并到总程序中，修改总程序。
三、数据结构描述
typedef struct
{
int key;
char otherinfo;
}Elem;
typedef struct
{
Elem r[N+1];//r[0]闲置或用作“哨兵”
int length;
}Sqlist;
void ShellSort(int a[],int n)
{
int i,j,d;
d=n/2;
while(d0)
{
for(i=d+1;i=n;i++)
{
a[0]=a[i];j=i-d;
while(j=0 a[0]a[j])
{
a[j+d]=a[j];
j=j-d;
a[j+d]=a[0];
}
d=d/2;
}
}
}
四、算法设计
4.1希尔排序流程图：
核心算法：
//希尔排序
void ShellInsert(Sqlist *L,int dk, int *s,int *t)
{
int i,j;
for(i=dk+1;i=L-length ;i++)
{
(*t)++;
if(L-r [i].key L-r [i-dk].key )
{
L-r [0].key =L-r [i].key ;
(*s)++;
j=i-dk;
(*t)++;
while(j0L-r [0].key L-r [j].key )
{
L-r [j+dk].key =L-r [j].key ;
(*t)++;
(*s)++;
j-=dk;
}
L-r [j+dk].key =L-r [0].key ;
(*s)++;
}//if
}//for
}
void ShellSort(Sqlist *L)
{
int i,j,dk;
int s=0,t=0;
for(i=(int)log(L-length +1);i0;i--) //形成增量
for(j=i;j=(int)log(L-length +1);j++)
{
dk =(int)pow(2,j-i+1)-1;
ShellInsert(L,dk, s,t);
}
printf(希尔排序 比较次数:%d,移动次数:%d\n,t,s);
}
五、详细程序清单
内部排序与哈弗曼的总程序：
#includestdio.h
#includemalloc.h
#includestring.h
#includestdlib.h
typedef struct
{
unsigned int weight;
unsigned char ch;
unsigned int parent,lchild,rchild;
}HT
显示全部