数据结构课程设计之赫夫曼编码的应用

学生课程设计

题 目： 赫夫曼编码的应用

学生姓名： 赵旺 学 号：124090102042

所在院(系)： 计算机与信息科学学院

专 业： 2012级计算机科学与技术 班 级： (二） 指导教师： 冯韵

2014年9月24日

目 录

一、概述 ................................................. 1 二、系统分析 ............................................. 1 三、概要设计 ............................................. 2 四、详细设计 ............................................. 4 4.1 赫夫曼树的建立 .................................... 4 4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 ................................................. 5 4.1.2 统计字符串中字符的种类以及各类字符的个数 ..... 7 4.1.3构造赫夫曼树 .................................. 8 4.2赫夫曼编码 ....................................... 10 4.2.1赫夫曼编码算法 ............................... 10 4.2.2建立正文的编码文件 ........................... 11 4.3代码文件的译码 .................................... 12 五、运行与测试 .......................................... 14 六、总结与心得 .......................................... 14 参考文献 ................................ 错误！未定义书签。 附录 .................................... 错误！未定义书签。

一、概述

本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编

码生产的代码串进行译码，输出 电文字符串。

在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

二、系统分析

赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。那么，

1

∑W i L i 恰好为二叉 树上带权路径长度。

因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。 根据设计要求和分析，要实现设计，必须实现以下方面的功能： （1） 赫夫曼树的建立； （2） 赫夫曼编码的生成； （3） 编码文件的译码；

三、概要设计

程序由哪些模块组成以及模块之间的层次结构、各模块的调用关

系；每个模块的功能。 void main()

void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)//编码部分

char *decode(HuffmanCode Hc)//译码 void

ChuffmanTree(HuffmanTree

HT,HuffmanCode

HC,int

cnt[],char str[]) //生成Huffman树

void select(HufmanTree HT,int k,int &s1,int &s2) //找寻parent为0,权最小的两个节点

2

其流程图如下：

开始 进行相应的操作 构对对程 造字编序赫符码结 夫串串束 曼编译退 树 码 码 出 进行相应的操作 输出结果 结束

3

四、详细设计

4.1 赫夫曼树的建立

由赫夫曼算法的定义可知，初始森林有 n 棵只含根节点的

二叉树。算法的第二步是：将当前森林 中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新 节点。显然要进行 n-1 次合并，所以生 n-1 个新节点，它们都是具有两个孩子分支结点。由此可 知，最新求得的赫夫曼树中一共有2n-1 个结点，其中n 个结点是初始森林的n 个孤立结点。并且赫夫 曼树中没有度数为1 的分支结点。我们可用一个大小为2n-1 的一维数组来存储赫夫曼树中的结点。因 此，赫夫曼树的存储结构描述为： #define n 100 #define m 2*n-1 typedef struct{ int weight;

int lchild,rchild,parent; }HTNode; T

typedef HTNode HuffmanTree[m+1];

4

开始 第i个结点权值 否 i=num? 是 第i个根结点 否 i=2*num-1? 是 创建赫夫曼树 输出字符统计情 否 i=num? 是 结束

4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法

void select(HuffmanTree T,int k,int *s1,int *s2)

{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序

5

号分别为S1和S2 int i,j; int min1=100;

for(i=1;i<=k;i++)//查找s1

if(T[i].weightj=i;min1=T[i].weight; } *s1=j; min1=32767;

for(i=1;i<=k;i++)//查找s2,不和s1相同

if(T[i].weightmin1=T[i].weight; } *s2=j; }

6

4.1.2 统计字符串中字符的种类以及各类字符的个数

假设电子文件字符串全是大写字母，那么该算法的实现思想是：

先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。应为大写字母的ASCII码与整数1~26个元素之间相差，因此在算法中使用字母减去作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。具体实现如下：

int jsq(char *s,int cnt[],char str[]) {

//统计各字符串中各种字母的个数以及字符的种类 char *p; int i,j,k; int temp[27]; for(i=1;i<=26;i++) temp[i]=0;

7

for(p=s;*p!='\\0';p++) {//统计各种字符个数 if(*p>='A' && *p<='Z') { k=*p-; temp[k]++; } } j=0;

for(i=1,j=0;i<=26;i++)//统计有多少种字符 if(temp[i]!=0) { j++;

str[j]=i+;//将对应的数组送到数组中 cnt[j]=temp[i];//存入对应数组的权值 } return j; }

4.1.3构造赫夫曼树

void

ChuffmanTree(HuffmanTree

HT,HuffmanCode

cnt[],char str[]) {//构造赫夫曼树HT int i,s1,s2;

8

HC,int

for(i=1;i<=2*num-1;i++)//初始化HT，左右孩子，双亲，权值都为0 { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].weight=0; }

for(i=1;i<=num;i++)//输入num个叶节点的权值 HT[i].weight=cnt[i];

for(i=num+1;i<=2*num-1;i++)//从numd后面开始新建结点存放新生成的父节点 {

select(HT,i-1,&s1,&s2);//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2

HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent赋值 HT[i].lchild=s1; HT[i].rchild=s2;//新结点的左右孩子 HT[i].weight=HT[s1].weight+ HT[s2].weight;//新结点的权值 }

for(i=0;i<=num;i++)//输入字符集中的字符 HC[i].ch=str[i]; i=1;

while(i<=num)

printf(\"字符 %c,次数为: %d\\n\}

9

4.2赫夫曼编码

要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要

求和实际需要定义的类型如下：

typedef struct{ char ch; char bits[n+1]; int start ; }CodeNode;

typedef CodeNode HuffmanCode[n];

4.2.1赫夫曼编码算法

void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) {//根据赫夫曼树HT 求赫夫曼编码表ＨＣ int c,p,i; char cd[n];

int start; cd[num]='\\0'; for(i=1;i<=num;i++) {

start=num;

10

c=i;

while((p=HT[c].parent)>0)//直至上诉到ht[c]是树根为止 {//若HT[c]是HT[p]的孩子，则生成0；否则生成代码1 cd[--start]=(HT[p].lchild= =c)? '0':'1' : c=p;

}//end of while

strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; } }

4.2.2建立正文的编码文件

建立编码文件的基本思想是：将要编码的字符串中的字符逐一与

预先生成赫夫曼树时保保存的 字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。 具体算法如下：

viod coding(huffmanCode HC,char *str) { int i,j; FILE *fp;

11

fp =fopen(“codefile.tex”,”w”);

while(*str){//对电文中字符逐一生成编码并写入文件 for(i=1;i<=num;i++) if(HC[i].ch= =*str){ for(j=0;j<=HC[i].len;j++) f putc (HC[i].bits[j],fp); break; } str++; }

fclose(fp); }

4.3代码文件的译码

译码的基本思想是:读文件中编码，并与生成的赫夫曼编码表比

较，遇到相等时，即取出其对应的 字符存入一个新串中。 Char * decode (HuffmanCode HC) {//代码文件codefile.tex 译码 FILE *fp; char str[254]; char *p;

static char cd[n+1] int i,j,k=0,cjs;

12

fp=fopen(“codefile.tex”,”r”); while(!feof(fp)) {cjs=0;

for(i=0;i<=num&&cjs==0&&!feof(fp);i++) { cd[i]=‘ ；’ cd[i+1]='\\0'; cd[i]=fgetc(fp); for(j=1;j<=num;j++)

if(strcmp(HC[i].bits,cd)= =0) {

str[k]=HC[j].ch;k++; cjs=1;break; } } str[k]='\\0'; ;p=str; return p; }

13

五、运行与测试

运行结果为

六、总结与心得

本次编写过程中出现了较多的问题，比如开始对赫夫曼树的理解

不是很清楚，导致在编写过程中某些代码错误而没能及时修改，在最后进行修改时遇到了较多的麻烦。但是经过这次对赫夫曼树的学习后，我了解到赫夫曼编码(Huffman Coding)是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据的无损耗压缩。总之受益匪浅。

14