哈夫曼树及其操作数据结构实验报告2.docx

1、哈夫曼树及其操作数据结构实验报告2电 子 科 技 大 学实 验 报 告 课程名称： 数据结构与算法 学生： *浩 学 号： * 点名序号： * 指导教师： 钱* 实验地点： 基础实验大楼 实验时间： 2015.5.7 2014-2015-2学期 信息与软件工程学院实 验 报 告(二)学生：*浩 学 号：* 指导教师：钱*实验地点： 科研教学楼A508 实验时间：2015.5.7一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法树三、实验学时：4四、实验原理：霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David

2、A. Huffman在麻省理工攻读博士时所发明的。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的

3、长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi（i=1,2,.n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,.n）。可以证明霍夫曼树的WPL是最小的。五、实验目的：本实验通过编程实现赫夫曼编

4、码算法，使学生掌握赫夫曼树的构造方法，理解树这种数据结构的应用价值，并能熟练运用C语言的指针实现构建赫夫曼二叉树，培养理论联系实际和自主学习的能力，加强对数据结构的原理理解，提高编程水平。六、实验容：（1）实现输入的英文字符串输入，并设计算法分别统计不同字符在该字符串中出现的次数，字符要区分大小写；（2）实现赫夫曼树的构建算法；（3）遍历赫夫曼生成每个字符的二进制编码；（4）显示输出每个字母的编码。七、实验器材（设备、元器件）： PC机一台，装有C或C+语言集成开发环境。八、数据结构与程序：/* * *程序名称：哈夫曼树的相关操作 * * *程序容：生成哈夫曼树及其编码表、对字符串进行编码等

5、* * *编写作者：家浩 * * *完成时间：2015.5.15 * */#include #include #include #define MAXSIZE 10000char file_address100; /全局通用文件地址typedef struct hnode / 哈夫曼树的节点结构定义 int weight; int lchild, rchild, parent;THNode, * TpHTree;typedef struct huffman_code / 哈夫曼编码表的元素结构定义 int weight; / 编码对应的权值 char * pcode; / 指向编码字符串的指针

6、THCode, *TpHcodeTab;/*/ * *声明函数/*TpHcodeTab build_codesheet( TpHTree pht, int leaves_num); / 根据哈夫曼树得到编码表TpHTree create_huffman_tree(int weights, int n ); / 构造哈夫曼树void select_mintree(TpHTree , int , int *, int *); / 从森林中选择权值最小的两棵子树void destroy_codesheet(TpHcodeTab codesheet, int n); / 销毁哈夫曼编码表int rea

7、d_file(char file_address100, char *message); / 从文本文件读入字符串 int calc_freq(char text, int *freq, char *dict, int n); / 统计字符串text中字符出现的频率/*/ * *主函数/*int main(void) int i, msg_num,choose; char s; /清空缓存 int leaves_num = 0; do TpHTree pht = NULL; /建立树根 TpHcodeTab codesheet; /建立编码表 char msgMAXSIZE; /建立信息数组

8、int *weights = NULL; /建立频率数组 char *dict = NULL; /建立字符数组 printf( - n-哈夫曼树-n - ); printf(n读取文件还是手动输入信息？n 1：手动输入信息n 2：读取文件n 请选择：); scanf(%d,&choose); if(choose = 1) printf(请输入信息：n); scanf(%c,&s); /清理键盘缓存 gets(msg); msg_num = strlen(msg); else printf(输入文件地址（例如：F:filename.txt）:n); scanf(%c,&s); /清理键盘缓存 g

9、ets(file_address); /输入文件地址 msg_num = read_file( file_address, msg); /读取文本文件 leaves_num = calc_freq( msg, &weights, &dict, msg_num );/统计文本串中的字符频率，同时得到哈夫曼树的叶节点数 pht = create_huffman_tree( weights, leaves_num ); /创建哈夫曼树 codesheet = build_codesheet( pht, leaves_num ); /构造哈夫曼编码表 printf(n-字符频率编码表-n); prin

10、tf(符号 - 频率 - 编码n); for(i = 0; i leaves_num ; i+) printf(%4c - %-3d - %-6sn, dicti, codesheeti.weight, codesheeti.pcode); printf(-n); destroy_codesheet( codesheet, leaves_num); /销毁哈夫曼编码表 if(pht) /释放所有临时空间 free(pht); if(dict) free(dict); if(weights) free(weights); printf(nt0：结束nt1：继续nt请选择：); scanf(%d,

11、&choose); while(choose); return 0;/*/ * *构造哈夫曼编码表/*TpHcodeTab build_codesheet( TpHTree pht, int leaves_num ) int i, cid, pid, cursor, len; TpHcodeTab sheet; char * pch = (char *) malloc( leaves_num + 1 ); if( !pch ) printf(申请空间失败！); exit(0); memset( pch, 0, (leaves_num + 1) ); / 清零新分配的空间 sheet = ( T

12、pHcodeTab )malloc( sizeof( THCode ) * leaves_num ); if( !sheet ) printf(申请编码表存空间失败！); exit(0); for( i = 0; i leaves_num; +i ) sheeti.weight = phti.weight; for( i = 0; i leaves_num; +i ) cursor = leaves_num; cid = i; pid = phtcid.parent; while( pid!= -1 ) /不为根节点 if (phtpid.lchild = cid) pch-cursor =

13、0; / 左分支编码为0 else pch-cursor = 1; / 右分支编码为1 cid = pid; pid = phtcid.parent; len = leaves_num - cursor + 1; sheeti.pcode = ( char * )malloc( len ); if( !sheeti.pcode ) printf(为节点%d的编码申请存空间失败！, i); exit(0); memset( sheeti.pcode, 0, len ); strncpy( sheeti.pcode, &pchcursor, strlen(&pchcursor) ); free(p

14、ch); return sheet;/*/ * *构造哈夫曼树/*TpHTree create_huffman_tree( int weights, int n ) TpHTree pht; int minA, minB; / 用于保存权值最小的两棵子树的序号 int i, a = 0; if( n 1 ) printf(没有叶子节点！n); return 0; a = (2 * n) - 1; pht = ( TpHTree ) malloc( sizeof( THNode ) * a ); if( !pht ) printf(分配数组空间失败！n); exit(0); for( i = 0

15、; i a; +i ) / 哈夫曼数组初始化 phti.weight = (i n) ? weightsi : 0; phti.lchild = -1; phti.rchild = -1; phti.parent = -1; for( i = n; i a; +i ) select_mintree( pht, (i-1), &minA, &minB ); phtminA.parent = i; phtminB.parent = i; phti.lchild = minA; phti.rchild = minB; phti.weight = phtminA.weight + phtminB.we

16、ight; return pht;/*/ * *选出权值最小的两棵子树/*void select_mintree(TpHTree pht, int n, int *minA, int *minB) int id, min1 = -1, min2 = -1; /最小值，次小值 int maxa = 10000, maxb = 10000; for(id = 0; id = n; id+) if(phtid.parent = -1) if( phtid.weight maxa ) min2 = min1; min1 = id; maxa = phtid.weight; else if(phtid.

17、weight maxb ) min2 = id; maxb = phtid.weight; *minA = min1; *minB = min2; return;/*/ * *销毁哈夫曼编码表/*void destroy_codesheet(TpHcodeTab sheet, int n) int i; for(i = 0; i n; +i) free(sheeti.pcode); free(sheet); return;/*/ * *读取文本文件 /*int read_file(char file_address100, char *message) int str_len; /字符串长度

18、FILE * pFile = NULL; pFile = fopen( file_address, r); /打开文件 if(!pFile) printf(打开文件失败!n); exit(0); else printf(打开文件成功!n); memset(message, 0, MAXSIZE); /清除缓冲 if( fgets( message, MAXSIZE, pFile ) = NULL) printf( fgets errorn ); exit(0); else printf( 成功读取文件，容如下：n%sn, message); str_len = strlen(message);

19、 fclose(pFile); return str_len;/*/ * *统计字符出现的频率/*int calc_freq(char text, int *freq, char *dict, int n)/n为字符串长度 int i, k; int char_num = 0; int * chars; /不同种类的字符 char * fre; /字符的出现频率 int times256 = 0; for(i = 0; i n; +i) /各个字符出现的频率 timestexti+; for(i = 0; i 0 ) char_num+; chars = (int*)malloc(sizeof

20、(int)*char_num); if( !chars ) printf(为频率数组分配空间失败！n); exit(0); fre = (char *)malloc(sizeof(char)*char_num); if( !fre ) printf(为字符数组分配空间失败！n); exit(0); k = 0; for(i = 0; i 0 ) charsk = timesi; frek = (char)i; k+; *freq = chars; *dict = fre; return char_num;/不同种类的字符个数九、程序运行结果： 一、手动输入信息 二、从文件读取信息十、实验结论：

21、本实验通过编程实现赫夫曼编码算法，在实验中掌握了赫夫曼树的构造方法，理解了树这种数据结构的应用价值，并且已经能够熟练运用指针实现构建赫夫曼二叉树，理论联系实际和自主学习的能力得到了培养，对数据结构的原理理解更加深刻，也提高了编程水平。十一、总结及心得体会： 1、虽然算法很多事现有的，可以用来做参考，不宜照抄。 2、使用指针存储信息之前应为其分配存空间； 3、scanf()函数读取到空格会自动停止，而gets()函数读取到回车即停止； 4、需要读取单个字符时要考虑到键盘的缓冲区； 5、双重指针的问题应特别注意； 6、文件地址如果输入错误的解决方案没有考虑到； 7、申请了存的空间应该在程序结束时进行释放，否则可能造成空间浪费；8、应养成对代码进行注释的习惯，不久之后可能自己的程序自己都不知道是什么意思；9、实验是培养独立思考、作业的过程，要多思考，不应过多依赖他人。