完整数据结构课程设计-电文编码译码哈夫曼编码

福建农林大学

计算机与信息学院

数据结构课程设计

设计：哈夫曼编译码器

姓名：

专业：2013级计算机科学与技术

学号：

班级：

完成日期：

哈夫曼编译码器

一、需求分析

在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间

和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛

且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树一即最优二

叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特

殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之

处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符

使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串

的平均期望长度降低，从而达到无损压缩数据的目的X哈夫曼编码的应用很广泛，

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子

都有一条路径，对路径上的各分支约定：指向左子树的分支表示〃0〃码，指向右

子树的分支表示〃r码，取每条路径上的或的序列作为和各个叶子对

应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进

制代码，输入二进制代码时可以编译成字符串。

二、设计要求

对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译

码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解

码。电报通信是传递文字的二进制码形式的字符串。但在信息传递口寸，总希望总长

度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长

度为Li,电文中有n种字符,则电文编码总长度为£WiLi。若将此对应到二叉树上,

Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么,\WiLi恰好为二叉树

上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符

出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功

能：Q）哈夫曼树的建立；（2）哈夫曼编码的生成；（3）编码文件的译码。

三、概要设计

哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生

成哈夫曼编码后进行译码。

在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进

制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0,右分支

代表1，则从根节点到每个叶子节点所经过的路径分支组成的。和1的序列便为该

节点对应字符的编码，称之为哈夫曼编码。

最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字

符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文

的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。

设计包含的几个方面：

①哈夫曼树的建立

赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二

叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一

棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行

n-1次合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支结点。由

此可知，最终求得的哈夫曼树中一共有2n-1个结点，其中n个结点是初始森林的

n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小

为2n-l的一维数组来存储赫夫曼树中的结点。定义的结构体类型如下：

typedefstruct

chardata;〃结点字符

k=*p;

cnt[k]++;

)

j=0;

for(i=lj=0;i<=256;i++)

if(cnt[i]!=O)

(

j++；

)

returnj;

)

②哈夫曼树的算法

voidCreateHT(HTNodeht[],intn,charstr[],intcn[])〃创建哈夫曼树函数

{for(intinput=l;input<=256;input++)

(

str[input]=input;

)

int1=0;

for(intoutput=l;output<=256;output++)

(

if(cn[output]!=0)

{ht[l].data=str[output];〃按字母顺序将出现的字母依次存

入数组ht[]

ht[l].weight=cn[output];

I++；

)

)

inti,k,lnode,mode;

intminl,min2;

for(i=0;i<2*n-l;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=O;〃所有结点的相关域置初值0

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

(

minl=min2=MAX;//int的范围是-32768-32767

lnode=rnode=0;//Inode和mode记录最小权值的两个结点位置

for(k=0;k<=i-l;k++)〃选出每次外层循环最小权值的两个结点

(

if(ht[k].parent==O)〃只在尚未构造二叉树的结点中查找

{

if(ht[k].weight<minl)〃比mini小时

min2=minl;rnode=lnode;

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

)

elseif(ht[k].weight<min2)〃比mini大，比min2小

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

)

)

)

ht[lnode].parent=i;ht[rnode].parent=i;〃两个最小节点的父节点是i

ht[i].weight=ht[lnode].weight+ht[rnode].weight;〃两个最小节点的父节点权值为两个

最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode;〃父节点的左节点和右节点

)

)

③哈夫曼编码

voidCreateHCode(HTNodeht[],HCodehcd[],intn)

inti,p,c;

HCodehe;

for(i=0;i<n;i++)〃根据哈夫曼树求哈夫曼编码

(

hc.start=n;〃初始位置

c=i；〃从叶子结点ht[i]开始上溯

p=ht[i].parent;

while(p!=0)〃循序直到树根结点结束循环

hc.cd[hc.start-]=(ht[p].lchild)==c?,O':,l';〃左孩子记为0,右孩子记为1

C=p;

p=ht[p].parent;〃与上句c=i;p=ht[i].parent同义，促进循环

)

hc.start++;//start指向哈夫曼编码hc.cd□中最开始字符

hcd[i]=hc;

}

)

④哈夫曼译码

voiddeHCode(HTNodeht[],HCodehcdOJntn,charstr[])〃译码函数

(

printf。输出译码结果为:\n");

intizj,k,x,m=0;

charcode[MAX];

for(i=0;i<MAX;i++)

for(j=O;j<n;j++)

if(str[i]==ht[j].data)〃循环查找与输入字符相同的编号，相同的就输出这个字符

的编码

{

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

code[m]=hcd[j].cd[k];〃将输出的编码赋值至擞组中

m++;

)

break;〃输出元成后跳出当刖for循环

)

code[m]='#";

〃把要进行译码的字符串存入code数组中

while(code[0]!='#')

for(i=0;i<n;i++)

(

m=0;//m为想同编码个数的计数器

//]为记录所存储这个字符的编码个数

for(k=hcd[i].start,j=O;k<=n;k++/j++)

if(code[j]==hcd[i].cd；k])〃当有相同编码时m值加1

m++;

}

if(m==j)〃当输入的字符串与所存储的编码字符串个数相等时

则输出这个的data数据

(

printf("%c"fht[i].data);

for(x=0;code[x-j]!='#;x++)〃把已经使用过的code数组里的字符串删除

(

code[x]=code[x+j];〃删除j个数，往前移动j位

)

)

)

printf("\n");

)

⑤主函数

voidmain()

(

charst[MAX],sst[MAX];

intcn[257];

intn,i;

printf("请输入字符串(任意字符):\n");

gets(st);

n=jsq(st,cn,sst);

〃〃〃〃〃〃〃〃〃〃〃〃〃/99

for(i=0;i<99;i++)

sst[i]=st[i];

IIIIIIIIIIIIIIIIIIIIIIIIIIIHIIIII

HTNodeht[M];

HCodehcd[N];

CreateHT(ht,n,st,cn);

CreatelICode(htzhcd,n);

outputHCode(ht,hcd,n);

editHCode(ht,hcd,n/sst);

deHCode(ht,hcd/n,sst);

)

五、调试

输出哈夫曼编码

青输入字符串〈任意字符）:

lothingisimpossible?

输出哈夫曼编码:

■011

F?:11100

N:11101

b：11110

e：11111

0000

h：0001

i：110

1：0010

n：0011

n:0100

o:1011

P:0101

s：100

t：1010

输出编码结果

请输入字符串（任意字符》:

Letitbe!

输出哈夫曼编码:

：110

«：010

L：011

b：100

e：111

i：101

t：00

输出编码结果：

0111110011010100110100111010

输出译码结果

附录

源程序

#include<stdio.h>

#include<string.h>〃gets()函数需要

#defineN256〃义用N表示50叶节点数

#defineM2*N-1〃用M表示节点总数当叶节点数位n时总节点数为2n-l

#defineMAX32767

typedefstruct

chardata;〃结点字符

intweight;〃权值

intparent;〃双亲结点

intIchild;〃左孩子结点

intrchild;〃右孩子结点

JHTNode;

lllllllllllllllllllllllllll

typedefstruct

charcd[N];〃存放哈夫曼码

intstart;〃从start开始读cd中的哈夫曼码

}HCode;

lllllllllllllllllllllllllllllllllll

intjsq(char*s,intcnt[],charstr[])

{char*p;

intij,k;

for(i=l;i<=256;i++)

cnt[i]=0;

for(p=s;*p!=,\0';p++)

(

k=*p;

cnt[k]++;

)

j=0；

for(i=l,j=0;i<=256;i++)

if(cnt[i]!=0)

j++;

)

returnj;

)

lllllllllllllllllllllllllllllllllllllllllllllllllll

voidCreateHT(HTNodeht[],intnfcharstr[],intcn[])〃创建哈夫曼树函数

{for(intinput=l;input<=256;input++)

(

str[input]=input;

)

int1=0;

for(intoutput=l;output<=256;output++)

(

if(cn[output]!=0)

{ht[l].data=str[output];〃按字母顺序将出现的字母依次存

入数组ht[]

ht[l].weight=cn[output];

I++；

)

)

inti,k,lnode,rnode;

intminl,min2;

for(i=0;i<2*n-l;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=O;〃所有结点的相关域置初值0

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

(

minl=min2=MAX;//int的范围是-32768-32767

lnode=rnode=0;//Inode和mode记录最小权值的两个结点位置

for(k=0;k<=i-l;k++)〃选出每次外层循环最小权值的两个结点

(

if(ht[k].parent==O)〃只在尚未构造二叉树的结点中查找

{

if(ht[k].weight<minl)〃比mini小时

min2=minl;rnode=lnode;

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

)

elseif(ht[k].weight<min2)〃比mini大，比min2小

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

)

)

}

ht[lnode].parent=i;ht[rnode].parent=i;〃两个最小节点的父节点是i

ht[i].weight=ht[lnode].weight+ht[rnode].weight;〃两个最小节点的父节点权值为两个

最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode;〃父节点的左节点和右节点

)

)

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

voidCreateHCode(HTNodeht[],HCodehcd[],intn)

inti,p,c;

HCodehe;

for(i=0;i<n;i++)〃根据哈夫曼树求哈夫曼编码

hc.start=n;〃初始位置

c=i；〃从叶子结点ht[i]开始上溯

p=ht[i].parent;

while(p!=0)〃循序直到树根结点结束循环

hc.cd[hc.start-]=(ht[p].lchild)==c?'O':'l';〃左孩子记为0,右孩子记为1

c=p;

p=ht[p].parent;〃与上句c=i;p=ht[i].parent同义，促进循环

hc.start++;〃start指向哈夫曼编码hc.cd口中最开始字符

hcd[i]=hc;

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

voidoutputHCode(HTNodeht[],HCodehcd[],intn)/制出哈夫曼编码的列表

inti,k;

printf("输出哈夫曼编码:\n");

for(i=0;i<n;i++)〃输出data中的所有数据,

{

printf("%c:\t",ht[i].data);

for(k=hcd[i].start;k<=n;k++)〃输出所有data中数据的编码

{

printfC%c",hcd[i].cd[k]);〃从初最开始的字符起输出

)

printf("\n");

)

)

llllllllllllllllllllllllllllllllllllllllllll

voideditHCode(HTNodeht[],HCodehcd[],intn,charstr[])〃编码函数

{intijk;

printf("\n输出编码结果:\n)

for(i=0;i<MAX;i++)

for(j=0;j<n;j++)

if(str[i]==ht[j].data)〃循环查找与输入字符相同的编号，相同的就输出这个字符

的编码

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

primf(”％c”,hcd[j].cd[k]);

)

break;〃输出完成后跳出当前for循环

)

printf("\n");

)

IIIIIIIHIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

voiddeHCode(HTNodeht[],HCodehcd[],intn,charstr[])〃译码函数

printf（"输出译码结果为:\n）

inti,j,k,x,m=0;

charcode[MAX];

for(i=0;i<MAX;i++)

for(j=0;j<n;j++)

if(str[i]==ht[j].data)〃循环查找与输入字符相同的编号，相同的就输出这个字符

的编码

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

code[m]=hcd[j].cd[k];〃将输出的编码赋值到数组中

m++;

)

break;〃输出元成后跳出当刖for循环

)