哈夫曼树.doc

西安郵電大學数据结构课程设计报告题 目： 哈夫曼编/译码器院系名称： 计算机学院 专业名称： 软件工程班 级： 1103班 学生姓名： 王梦楠学号（8位）： 04113078指导教师： 曾艳 设计起止时间：2012年12月3日2012年12月14日一. 设计目的加深对哈夫曼树的理解与运用，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。二. 设计内容利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。为这样的信息收发站写一个哈夫曼的编/译码器。1. 建立哈夫曼树：读入文件(*.souce)，统计文件中字符出现的频度，并以这些字符的频度作为权值，建立哈夫曼树。2. 编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，然后输出编码结果，并存入文件(*.code)中。3. 译码：利用已建立好的哈夫曼树将文件(*.code)中的代码进行译码，并输出译码结果，并存入文件(*.decode)中。 三概要设计1功能模块图； 哈夫曼编译码系统 获取文件中 以字符频度 根据哈夫曼 将哈夫曼编 屏幕输出模 主函数模块 各个字符频 为权值建立 树求字符的 码进行译码 块度 哈夫曼树 哈夫曼编码2各个模块详细的功能描述。a. 获取字符频度模块：通过读入以存在文件中的字符，进行字符频度的统计，并将频度进行屏幕输出。b. 哈夫曼树建立模块：将已经统计好的字符频度作为权值，通过每次比较求出最小的权值，然后进行哈夫曼树的建立。c. 求哈夫曼编码模块：定义向左为0，向右为1，对每个字符的编码进行求解。d. 译码模块：读取保存的哈夫曼编码文件，将编码根据已经建立好的哈夫曼树进行翻译，并保存。e. 屏幕输出模块：在屏幕上输出字符频度统计结果，哈夫曼树，文件编码，文件译码结果等。f. 主函数模块：调用各个功能函数。四详细设计1功能函数的调用关系图 main()函数 getcharsFreq() makeHuffman() showhuffman() makeHuffcode() dehuffman() 获取字符频度 建立哈夫曼树 输出哈夫曼树 求解编码 译码 从文件中获取 调用 调用 调用 调用getcharsFreq() getcharsFreq() getcharsFreq() makeHuffman() select() makeHuffman() makeHuffman bm() strrev()2各功能函数的数据流程图a. getcharsFreq()函数： getcharsFreq() 打开文件 是 文件是否为空 否 获取字符 ch=fgetc(fpin) 获取频度值 if (chars(int)ch = 0) count+; chars(int)ch+; ch = fgetc(fpin); 关闭文件 返回主函数b. makeHuffmancode()函数： makeHuffmancode() 定义编码数值 l=0，r=1 否 判断是否有孩子结点 是 定义 chile=parent 返回主函数c. makeHuffman()函数： makeHuffman() 初始化结点hi.chars = freqi.chars; hi.weight = freqi.weight; hi.lchild = -1; hi.rchild = -1; hi.parent = -1; 判断hj.parent = -1 否hj.parent = -1 是 获取最小的两个 字符频度select() 构成新结点 返回主函数d. dehuffman()函数dehuffman() 打开文件 是 判断文件是否为空 否 获取编码,执行以下过程 if(ch = 1) root = hroot.rchild; else root = hroot.lchild; 否 判断孩子结点 是否为空 是 查找字符 返回主函数3重点设计及编码a. 文件字符频度的获取：以字符的ASCII编码为数组下标，以数组元素值为频度，每读入一个字符进行元素值的加1，直至字符统计完毕，具体代码如下：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(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);printf(字符种类个数：%dn, count);putchar(n);* Count = count;fclose(fpin);return freq;b. 求字符的哈夫曼编码：定义向左为0，向右为1，对每个字符的编码进行求解，具体代码如下：void 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;else codej+ = 1;child = parent;parent = hchild.parent;codej = 0;strcpy(hi.code , strrev(code,(int)strlen(code);j = 0;free(code);五测试数据及运行结果1正常测试数据和运行结果a.输入已存在文件1.souce 运行结果如下：b.输入保存编码的文件名 2.code ，结果如下：c.输入编码文件名进行译码，并将译码结果保存入3.decode 运行结果如下：2异常测试数据及运行结果a.输入不存在需编码的文件名（4.souce）时，运行结果如下：b.输入不存在的编码文件名（5.code）时，运行结果如下：六调试情况，设计技巧及体会1改进方案程序只是对文件进行了哈夫曼编/译码，并未实现将文件进行压缩与解压缩，这是需要改进的地方。2体会通过本次课