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

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 <stdio.h>#include <stdlib.h>#include <string.h>#define BUFFERSIZE 6000#define VERBAL 0#define DEBUG 1#define MAXVALUE 6000typedef struct hnode int weig

5、ht; int lchild, rchild, parent;THNode, * TpHTree;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( huffm

6、ani.weight < a ) a = huffmani.weight; subb = suba; suba = 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 ) *

7、 num ); for( i = 0; i < num; +i ) phti.weight = weightsi; phti.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.weig

8、ht + phtsubB.weight; return pht;void output_huffman_tree(TpHTree pht, int n)int 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 ) i

9、nt i, j, k, m, len; TpHcodeTab table = ( TpHcodeTab )malloc( sizeof( THCode ) * n); char * pch = (char *) malloc(n + 1 ); 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

10、= phtj.parent; len = n - m + 1; tablei.pcode = ( char * )malloc( len ); strncpy( tablei.pcode, &pchm, strlen(&pchm) ); return table;char * encode_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 =

11、 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 += len; 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

12、 = ( char * )malloc( BUFFERSIZE + 1 ); len = strlen(msg); for(i = 0; i < len; ) idx = (2 * n) - 2; while ( idx >= n) if( msgi = '0') idx = phtidx.lchild; +i; else idx = phtidx.rchild; +i; pchpos = dictidx; pos+; return pch;void destroy_hctable(TpHcodeTab hcode_table, int n) int i; for(

13、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(): 打开文件%s失败!n", filename);exit(0);elseprintf("read_fil

14、e(): 成功打开文件%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;/ 统计

15、字符串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 < 128; i+)if( tokensi > 0 )nchar+;pwght = (int*)malloc(sizeof(int)*nchar);if( !pwght )printf("为权重数组分配空间失败！n&

16、quot;);exit(0);pch = (char *)malloc(nchar);if( !pch )printf("为字符数组（字典）分配空间失败！n");exit(0);k = 0;for(i = 0; i < 128; +i)if( tokensi > 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 *

17、filename = "/Users/pro/Desktop/数据结构实验/src/debug/love_letter.txt"TpHTree pht = NULL;TpHcodeTab 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, &

18、amp;weights, &dict, nmsg ); for(i = 0; i < nleaves; +i)printf("%d %c : %dn",i, dicti, weightsi);pht = create_huffman_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);d