完整word版)哈夫曼树

1、西安郵電大學数据结构课程设计报告题 目： 哈夫曼编 / 译码器院系名称： 计算机学院专业名称：软件工程班 级：1103 班学生姓名：王梦楠学号（ 8 位）：04113078指导教师：曾艳设计起止时间： 2012 年 12 月 3 日 2012 年 12 月 14 日设计目的加深对哈夫曼树的理解与运用， 提高综合运用所学的理论知识和方法独立分析和解决问 题的能力。二 . 设计内容利用哈夫曼编码进行信息通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输 成本。这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行 译码(复原) 。为这样的信息收发站写一个哈夫曼的编/译

2、码器。1. 建立哈夫曼树： 读入文件 (*.souce) ，统计文件中字符出现的频度， 并以这些字符的频 度作为权值，建立哈夫曼树。2. 编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码， 然后输出编码结果，并存入文件 (*.code) 中。3. 译码：利用已建立好的哈夫曼树将文件 (*.code) 中的代码进行译码， 并输出译码结果， 并存入文件 (*.decode) 中。三概要设计1功能模块图；哈夫曼编译码系统获取文件中 各个字符频 度以字符频度 为权值建立 哈夫曼树将哈夫曼编屏幕输出模主函数模块码进行译码块根据哈夫曼 树求字符的 哈夫曼编码2各个模块详细的功能描述

3、。a. 获取字符频度模块：通过读入以存在文件中的字符，进行字符频度的统计，并将频度进 行屏幕输出。b. 哈夫曼树建立模块：将已经统计好的字符频度作为权值，通过每次比较求出最小的权值， 然后进行哈夫曼树的建立。c. 求哈夫曼编码模块：定义向左为 0，向右为 1，对每个字符的编码进行求解。d. 译码模块：读取保存的哈夫曼编码文件，将编码根据已经建立好的哈夫曼树进行翻译， 并保存。e. 屏幕输出模块：在屏幕上输出字符频度统计结果，哈夫曼树，文件编码，文件译码结果 等。f. 主函数模块：调用各个功能函数。四详细设计1功能函数的调用关系图2各功能函数的数据流程图a. getcharsFreq() 函数：

4、chile=parent初始化结点 hi.chars = freqi.chars; = freqi.weight;否是获取最小的两个 字符频度 select()判断hj.parent = -1hj.parent = -1c. makeHuffman() 函数：makeHuffman()hi.weigh hi.lchild = -1; hi.rchild = -1; hi.parent = -1;构成新结点返回主函数d. dehuffman() 函数3重点设计及编码a. 文件字符频度的获取：以字符的 ASCII 编码为数组下标，以数组元素值为频度，每读入一个字符进行元素值 的加 1，直至字符统计

5、完毕，具体代码如下：FREQ *getCharsFreq(const char *fileName, int *Count) FILE *fpin;FREQ *freq = NULL;int chars256 = 0;int count = 0;int i, j;char ch;if(fpin = fopen(fileName, r) = NULL) printf( 打开失败 ,文件不存在！ n); exit(-1);ch = fgetc(fpin);while(!feof(fpin)if (chars(int)ch = 0) count+;chars(int)ch+; ch = fgetc(

6、fpin);freq = (FREQ *)malloc(sizeof(FREQ)*count);printf( 字符 t 权值 n);for (i = j = 0; i 256; i+) if(charsi) printf(%ct,freqj.chars = i); printf(%dn,freqj+.weight = charsi); %dn, count);printf( 字符种类个数： putchar(n);* Count = count; fclose(fpin);return freq;b. 求字符的哈夫曼编码：定义向左为 0，向右为 1，对每个字符的编码进行求解，具体代码如下： v

7、oid makehuffmancode(HTNode *h,int count) char * code = NULL;int i,j=0;int child, parent;code=(char *)calloc(sizeof (char),count); for(i = 0; i count; i+)parent = hi.parent;child = i;while (parent != -1)if(hparent.lchild = child) codej+ = 0;elsecodej+ = 1;child = parent;parent = hchild.parent; codej

8、= 0;strcpy(hi.code , strrev(code,(int)strlen(code); j = 0; free(code);五测试数据及运行结果1正常测试数据和运行结果a. 输入已存在文件 1.souce 运行结果如下：guest-QydqlK)wm-virtual-machine: 字符 权值32142DEI J221216324Y a b d下标字符权值左孩子右孩子父节点编码O81-1490101#2-1-133112%1-1-128111OO33-114011101402-134111O52128IelIOI6二442ll7A21134llll8D2-135100009E

9、4-1-143611010I1-1-129IellIO11J1-129lllll12M314113N2-1-1351114023611O152-1-136lll17T113011000118V2-1-13711OO19Y1-131IIOOIO20a6147Illl21b3-1-141l22d2-1-13711123f1-1131IIeOlI24t1-1-132IlIOOO25k11132IlIOOI字符种类个数:28b. 输入保存编码的文件名 2.code ，结果如下：c. 输入编码文件名进行译码，并将译码结果保存入 3.decode 运行结果如下：2异常测试数据及运行结果a. 输入不存在需编码的文件名( 4.souce )时，运行结果如下：b.输入不存在的编码文件名（ 5.code）时，运行结果如下：六调试情况，设计技巧及体会1改进方案程序只是对文件进行了哈夫曼编 /译码，并未实现将文件进行压缩与解压缩，这是需要 改进的地方。2体会通过本次课程设计， 深刻的了解了哈夫曼