数据结构-Huffman编码

数据结构实验报告

知识范畴：树

实验题目：Huffman编码

实验内容及要求：

输入符号数（序号用英文字母A,B,C,…表示）以及各符号出现概率（要求符号数不小于

10,建议用字符文件实现数据输入），建立Huffman二叉树存储结构，以字符串形式输出各符

号对应的二进制哈夫曼编码（建义输出到屏幕和字符文件中以便检验正确性）。

从键盘以字符串形式输入字母组成的符号串，利用已经建立的Huffman编码表在屏幕上输

出该符号串对应的二进制Huffman编码串然后对Huffman编码串进行译码并在屏幕上输出译

码后的字母符号串（对比是否与原始符号串相同）。建议用菜单形式提供功能以实现可多次输

入字母符号串及其编码译码结果。

实验目的：掌握Huffman编码。

数据结构设计简要描述:

采用结构体存储二叉树的结点，每个结点包含四个数据域。其结构如下：

typedefstruct

{

intparent;〃双亲下标

intIchild;〃左儿子下标

intrchild;〃右儿子下标

intw;〃结点权重

}HF_BTNode;

采底结构体存储二叉树，包含五个数据域，结构如下：

typedefstruct

（

intn;〃输入的实际符号种数，n<=N

ElemTps[N];//符号表

intweight[N];〃符号权重表

charcode[N][N+l];〃编码表

HF_BTNodehf[2*N-l];〃码树

}HFT;

算法设计简要描述：

构建编码树时，先初始化所有结点，再初始化叶子结点。生成根结点点时，先按下标从小

到大的顺序找出处于初始化状态的结点作为根结点，再按权重从大到小的顺序找出两个权重最

小的结点，作为该根结点的左右儿子。跟结点权重等于左右两个儿子的权重和。

编码二叉树时，从叶子结点开始回溯，到编码树的跟结点时结束回溯，当前结点为父母结

点的左儿子时编码1,右儿子时编码0,保存至字符串中。回溯时，通过父母指针找到跟结点。

回溯结束时，还需要将字符串反序，得到最终的哈夫曼编码。

译码01串和编码的顺序刚好相反，从编码树的根结点出发,为0是找到该结点的右儿子，

为1时找到该结点的左儿子，儿子结点为叶子结点时打印字符，继续下一个字符的译码。

输入/输出设计简要描述：

程序运行时打印菜单，输入菜单提示的功能。输入1时构建并编码哈夫曼二叉树，输入2

通过哈夫曼二叉树译码，输入3推出程序。对于1,2功能的输入，按下回车时结束输入。编

码时，输出字符总数和各字符出现的频数，接着输出每个字符对应的哈夫曼编码。

译码时，直接输出译码的结果。

输入输出均有文字提示。

编程语言说明：

使用VisualC++编程。主要代码采用C语言实现；输入与输出采用C的scanf和printf；

程序注释采用C/C++规范。

主要函数说明:

voidcreateHF(HFT&a)〃构建哈夫曼二叉树编码

voiddec(HFT&a,charreceive口，ElemTpdecoded[])〃哈夫曼二叉树的译码

voidinit(HFT&HTM,charstr[],intweight[])〃初始化字符表和权重表

程序测试简要报告：

编码输入：ABBAAACDACCDAACCAADA

译码输入：10010011110100010101000110101110001

运行结果：如图1

图一期望结果图二等长码

源程序代码:

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#includc<string.h>

#defineN100〃最大允许输入的符号个数

typcdcfcharElcniTp;

intflag=0;

〃二叉树结点结构

typedefstruct

(

intparent;〃双亲下标

intIchiki;〃左儿子下标

intrchild;〃右儿子下标

intw;〃结点权重

}HF_BTNode;〃码树结点类型

//哈夫曼编码二叉树结构

typcdcfstruct

(

intn;〃输入的实际符号种数,n<=N

ElemTps[N];〃符号表

intweight[N];〃符号权重表

charcode[N][N+l];〃编码表

HF_BTNodchf[2*N-l];〃码树

}HFT;

〃构建哈夫曼二叉树编码

voidcreateHF(HFT&a)

//a.n,a.s[0..n-l],a.weight[0..n-l]已知，求a.hf和a.code

{

int

char*p,*q,ch;

intchild;

//初始化

m=2*a.n-l;〃二叉树结点的个数(n个根节点，n・l个叶子结点)

fbr(i=O;i<m;i-H-)

!

a.hf[i].parent=a.hf[i].lchikl=a.hf[i].rchikl=・l;〃初始化各指针域为-1

}

fbr(i=O;i<a.n;i-H-)

a.hf{i].w=a.wcight[i];〃初始化码树中叶子结点的权重

〃构造Huffman二叉树，生成a.hf[n..m-l]

fbr(i=a.n;i<m;i++)〃生成码树的根结点

(

fdr(jl=O;jl<i;jl++)〃遍历码树的叶子结点

if(a.hf[jl].parent=l)〃找到码树中处于初始化状态的结点，记录下标为j1

break;

fbr(j=jH-l;j<i;j++)

it|a.hf[j].parcnt==-l&&a.hf[j].w<a.hf£j1].w)

jl=j；〃寻找处于初始化状态的最小权重的结点

a.hf[jl].parent=i;〃赋值该结点的父母指针指向第i个结点

a.hf[i].lchild=jl;〃第i个结点的左儿子指针指向jl

fbr(j2=0;j2<i;j2-H-)//同理，再寻找初始化状态的最小权重结点，记录下标为j2,

if(a.hflj2].parcnt=-l)

break;

fbrO=j2+l;j<i;j++)

if(a.hf[j].parent=-1&&a.hflj].w<a.hf[j2].w)

j2=j；

a.hf[j2].parent=i;〃赋值该结点的父母指针指向第i个结点

a.hfli].rchild=j2;〃第i个结点的左儿子指针指向j2

a.hf[i].w=a.hf[jl].w+a.hf[j2].w;〃跟结点权重等于左右两个儿子的权重和

flag=l;

//以下生成code字符串数组

fbr(i=O;i<a.n;i++)//从叶子结点开始回溯

!

j=i；//j从第i个叶子结点出发上溯至根结点，

p=a.code[i];〃code[i]表示一种字符编码

while(a.hf[j].parent!=-1)〃结束条件为T树的根结点(只有根节点的父母指针处于初始化状态)

(

child=j;〃记录回溯过程的孩子结点

j=a.hflj].parcnt;//j继续向上回溯

if(a.hf[j].1chi1d==child)〃如果孩子结点是左儿子，则记录编码1,是右儿子则记录0

*p++=T;

else*p++=*0,;

)

*p='\0,;〃编码结束

q=a.code[i];

P-；

whilc(qvp)//字符串逆序，记录正向编码(头尾互换位置)

{

ch=*q;

*q=*p;

*p=ch;

q++；

P-；

)

)

/*

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

printf(,,%d,%d,%d\nu,a.hf[i].lchild,a.hf[i].rchild,a.hf[i].w);

printffW”)；

*/

〃哈夫曼二叉树的译码

voiddcc(HFT&a,charreccive[],ElcmTpdccodcd[])〃a为哈夫曼编码树，decode存放译码的结果，receive为待翻译的01串

inti=O,j=O,k;

//puts(receive);

/*fbr(i=0;i<2*a.n-l;i++)

printf(M%d,%d,%d\n**,a.hf[i].lchild,a.hf[i].rchild,a.hf[i].w);

printfV，\nu);*/

i=0;

whilc(rcccivc[i]!-\0')

{

k=2*a.n-2;//k指向根结点

while(k>=a.n&&receive[i]!=W)//a.n为叶子结点个数，同时a.n也表示第•个根结点

{//printf(M%c,%d\n",receive[i],k);

if(receive[i]='r)〃如果编码为1,则指向左边，编码为0,则指向右子树，直到指向叶子结点

{k=a.hf[k].lchild;}

elseif(receive[i]=-0')

{k=a.hf[k].rchild;}

else

i++；

if|k<a.n)

{dccodcd[j++]=a.s[k];}〃从符号表中查找k号结点对应的符号，并存放到译码串中

}

}

decodedU]=*\(T;〃译码结束

printffW译码结果为:")；

puts(decoded);

}

voidinit(HFT&HTM,charstr[],intweight口)

{

charstr2[N],temp;

intij,k=0,n;

printfC请输入一个字符串巧;

scanfC\nn);

gets(str);

n=strlen(str);

print"，=%d\n",n);

〃冒泡排序字符串

fbr(i=l;i<n;i-H-)

fbr(j=O;jvn-i;J++)

if(str[j]>str[j4-l])

{temp=str[j];str[j]=str[j+l];str[j+1]=temp;J

//puts(str);

str2[0]=str[O];wcight[O]++;

〃统计权重

fbr(i=1;i<n;i-H-)

(

if(str[i]=str[i-l])

{weight[k]-H-;)

else

{k++;str2[k]=str[i];weight[k]++;}

}

HTM.n=k+1;

//printf(nHTM.n=%d\nu,HTM.n);

//初始化哈夫曼二叉树的字符表和权重表

fbr(i=O;i<HTM.n;i++)

(

HTM.s[i]=str2[i];

HTM.wcight[i]=wcight[i];

printff%c:%d\nM,HTM.s[i],HTM.weight[i]);

}

print(。”)；

}

intmain()

{

HFTHTM;

inti;

charstr[N],decoded[N],receive[N];

charch;

while(l)

intwcight[N]={0};

printfl："-----------------------------\n");

printf("l>构建编码哈夫曼二又树\n");

printfi："2、通过哈夫曼二叉树译码\n");

print*"3、退出\n");

printfi："-----------------------------\n");

printf("请输入:")；

scanf("\n");

ch=getchar();

switch(ch)

(

caseT:

(

init(HTM,str,weight);

crcatcHF(HTM);

fbr(i=O;i<HTM.n;i++)