数据结构实验报告-赫夫曼编码算法讲解

1、电 子 科 技 大 学实 验 报 告学生姓名：XXX 学 号：XXX 指导教师：XX实验地点：信软楼306 实验时间：5月19日一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法树三、实验学时：4四、实验原理：霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的

2、编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为

3、0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi（i=1,2,.n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,.n）。可以证明霍夫曼树的WPL是最小的。五、实验目的：本实验通过编程实现赫夫曼编码算法，使学生掌握赫夫曼树的构造方法，理解树这种数据结构的应用价值，并能熟练运用C语言的指针实现构建赫夫曼二叉树，培养理论联系实际和自主学习的能力，加强对数据结构的原理理解，提高编程水平。六、实验内容：（1）实现输入的英文字符串输入，并设计算法分别统计

4、不同字符在该字符串中出现的次数，字符要区分大小写；（2）实现赫夫曼树的构建算法；（3）遍历赫夫曼生成每个字符的二进制编码；（4）显示输出每个字母的编码。七、实验器材（设备、元器件）：PC机一台，装有C或C+语言集成开发环境。八、数据结构与程序：#include #include #include #define BUFFERSIZE 6000#define VERBAL 0#define DEBUG 1#define MAXVALUE 6000typedef struct hnode int weight; int lchild, rchild, parent;THNode, * TpHTre

5、e;typedef struct huffman_code int weight; char * pcode;THCode, *TpHcodeTab;void select_subtree(TpHTree huffman,int n,int *subA,int *subB) int i, suba = -1, subb = -1,a = MAXVALUE,b = MAXVALUE; for(i = 0; i = n; i+) if(huffmani.parent = -1) if( huffmani.weight a ) a = huffmani.weight; subb = suba; su

6、ba = i; else if(huffmani.weight b ) b = huffmani.weight; subb = i; *subA = suba; *subB = subb; return;TpHTree create_huffman_tree(int weights, int n ) TpHTree pht; int subA, subB,i, num=(2*n)-1; pht = ( TpHTree ) malloc( sizeof( THNode ) * num ); for( i = 0; i num; +i ) phti.weight = weightsi; phti.

7、lchild = -1; phti.rchild = -1; phti.parent = -1; for( i = n; i num; +i ) select_subtree( pht, i-1, &subA, &subB ); phtsubA.parent = i; phtsubB.parent = i; phti.lchild = subA; phti.rchild = subB; phti.weight = phtsubA.weight + phtsubB.weight; return pht;void output_huffman_tree(TpHTree pht, int n)int

8、 i; for (i=n+1;i=2*n-1;i+) printf( %d,phtphti.lchild.weight); printf( %d,phti.weight); printf( %dn,phtphti.rchild.weight); TpHcodeTab build_huffman_code_table(TpHTree pht, int n ) int i, j, k, m, len; TpHcodeTab table = ( TpHcodeTab )malloc( sizeof( THCode ) * n); char * pch = (char *) malloc(n + 1

9、); for( i = 0; i n; +i ) m = n; j = i; k = phtj.parent; tablei.weight = phti.weight; while( k!= -1 ) if (phtk.lchild = j) pch-m = 0; else pch-m = 1; j = k; k = phtj.parent; len = n - m + 1; tablei.pcode = ( char * )malloc( len ); strncpy( tablei.pcode, &pchm, strlen(&pchm) ); return table;char * enc

10、ode_huffman(TpHcodeTab pht, char *msg, char *dict, int n) int i, j; long m, len, offset = 0; char * pch; pch = ( char * )malloc( BUFFERSIZE + 1 ); m = strlen(msg); for(i = 0; i m; +i) for(j = 1; j = n; +j) if(msgi = dictj) len = strlen(phtj.pcode); strncpy( &pchoffset, phtj.pcode, len); offset += le

11、n; break; return pch; char * decode_huffman(TpHTree pht, char *msg, char *dict, int n) int i, pos = 0, idx = 0; long len; char * pch; pch = ( char * )malloc( BUFFERSIZE + 1 ); len = strlen(msg); for(i = 0; i = n) if( msgi = 0) idx = phtidx.lchild; +i; else idx = phtidx.rchild; +i; pchpos = dictidx;

12、pos+; return pch;void destroy_hctable(TpHcodeTab hcode_table, int n) int i; for(i = 0; i n; +i) if (hcode_tablei.pcode) free(hcode_tablei.pcode); free(hcode_table);long read_file(char* filename, char *message)long slen;FILE * pFile = NULL;pFile = fopen(filename, r);if(!pFile)printf(read_file(): 打开文件

13、%s失败!n, filename);exit(0);elseprintf(read_file(): 成功打开文件%s!n, filename);memset(message, 0, BUFFERSIZE);if( fgets( message, BUFFERSIZE-1, pFile ) = NULL)printf( fgets errorn );exit(0);elseprintf( %s, message);slen = strlen(message);fclose(pFile);printf(read_file(): 成功读入文件%s!n, filename);return slen;/

14、 统计字符串text中字符出现的频率int calc_freq(char text, int *freq, char *dict, long n)int i, k, nchar = 0;int * pwght;char * pch;int tokens128 = 0;for(i = 0; i n; +i)tokenstexti+;for(i = 0; i 0 )nchar+;pwght = (int*)malloc(sizeof(int)*nchar);if( !pwght )printf(为权重数组分配空间失败！n);exit(0);pch = (char *)malloc(nchar);i

15、f( !pch )printf(为字符数组（字典）分配空间失败！n);exit(0);k = 0;for(i = 0; i 0 )pwghtk = tokensi;pchk = (char)i; /强制类型转换k+;*freq = pwght;*dict = pch;return nchar;int main(int argc, char *argv)int i, nleaves = 0; long nmsg;char * filename = /Users/pro/Desktop/数据结构实验/src/debug/love_letter.txt;TpHTree pht = NULL;TpHc

16、odeTab hcode_table;char msgBUFFERSIZE;int *weights = NULL;char *dict = NULL;char *pcode = NULL;char *ptxt = NULL; nmsg = read_file(filename, msg);printf(%sn, msg); nleaves = calc_freq( msg, &weights, &dict, nmsg ); for(i = 0; i nleaves; +i)printf(%d %c : %dn,i, dicti, weightsi);pht = create_huffman_

17、tree( weights, nleaves ); output_huffman_tree(pht, nleaves); hcode_table = build_huffman_code_table( pht, nleaves ); printf(nHuffman编码表如下：n); pcode = encode_huffman(hcode_table, msg, dict, nleaves); printf(nHuffman编码为：n%sn, pcode); ptxt = decode_huffman(pht, pcode, dict, nleaves); printf(n编码的解码为： n%sn,ptxt);destroy_hctable( hcode_t