数据结构课程设计

课程设计书786645655

学院计算机学院。

专业信息与计算科学

5667789907yuiiiii2班。

题目利用树进行哈弗曼编码

教师贺全兵。

学生。摘要：哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

在计算机信息处理中，哈弗曼编码在信息论中应用举例“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

利用哈弗曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本，但是，这要求发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，对于双工通道（即可以双向传输的信道），每端都要有一个完整的编码译码系统，因此可以设计一个编码译码系统解决这样一个问题。

关键字：树、哈弗曼编码、编码译码系统。

分工：程序设计及编写：王瑶、傅登林。

程序调试及实现：王瑶、傅登林。

时间复杂度分析：王瑶、傅登林。

实验报告书写：王瑶、傅登林。

目录。第一章课程设计的内容及要求 1

第二章功能说明 2

第三章详细设计 3

3.1 创建哈弗曼树 3

3.2 编码 4

3.3 译码 4

第四章程序实现 5

4.1 源码分析 5

4.2 调试结果 8

4.3 调试分析 11

第五章课程设计心得 12

第六章参考文献 13

第一章课程设计的内容及要求。

第二章功能说明。

系统分为三个模块：

（1）、编码：读取字符——建立哈夫曼树——对文本进行哈弗曼编码并输出编码

2）、译码：提示输入需要译码的字符——利用建好的哈夫曼树进行译码

3）、退出：退出系统，程序运行结束。

第三章详细设计。

3.1创建哈弗曼树。

3.2编码。

3.3译码。

第4章程序实现。

4.1 源码分析。

#include<>

#defineup50

#definedown90

#defineleft60

#defineright55

#defineenter40

#definen50

#definem2*n-1

#definesize6

typedefstruct//定义结构体存放哈夫曼码。

chardata;

floatweight;

intparent,lchild,rchild;

htnode;

intchoice;

intkey()

unionregslf;

int86(0x16,&lf,&lf);

structimformation

charch;

floatfre;

imfor[size]=,

给相关字符设置初值。

typedefstruct

charcd[n];

intstart;

hcode;

voidcreateht(htnodeht,intn)

inti,k,lnode,rnode;

floatmin1,min2;for(i=0;i<2*n-1;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=-1;

for(i=n;i<2*n-1;i++)构造哈夫曼树。

min1=min2=1.1;//使用两个最小权值的结点为左孩子和右孩子。

lnode=rnode=-1;

for(k=0;k<=i-1;k++)

if(ht[k].parent==-1)

if(ht[k].weight{

min2=min1;rnode=lnode;

min1=ht[k].weight;lnode=k;

elseif(ht[k].weight{

min2=ht[k].weight;rnode=k;

ht[lnode].parent=i;ht[rnode].parent=i;

ht[i].weight=ht[lnode].weight+ht[rnode].weight;

ht[i].lchild=lnode;ht[i].rchild=rnode;

getchar();

voidcreatehcode(htnodeht,hcodehcd,intn)

inti,f,j,c;

hcodehc;

for(i=0;i{

c=i;f=ht[i].parent;

while(f!=-1)//回溯到树根结点。

if(ht[f].lchild==c)//遍历做孩子结点。

else//遍历孩子的右结点。

c=f;f=ht[f].parent;

hcd[i]=hc;

voidhuffmancode(htnodeht,hcodehcd,intn)

charb[m],*p;

inti,j,m,k;

printf("pleaseinputthewords:");

scanf("%s",b);

m=strlen(b);

for(i=0,p=b;i{

for(j=0;jif(ht[j].data==*p)

for(k=hcd[j].start;k<=n;k++)

printf("%c",hcd[j].cd[k]);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了