哈夫曼树

《哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、函数模块：调用各个功能函数。四．详细设计1．功能函数的调用关系图main()函数getcharsFreq()makeHuffman()showhuffman()makeHuffcode()dehuffman()获取字符频度建立哈夫曼树输出哈夫曼树求解编码译码从文件中获取调用调用调用调用getcharsFreq()getcharsFreq()getcharsFreq()makeHuffman()select()makeHuffman()makeHuffmanbm()strrev()2．各功能函数的数据流程图a.ge

5、tcharsFreq()函数：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()初始化结点h[i].ch

6、ars=freq[i].chars;h[i].weight=freq[i].weight;h[i].lchild=-1;h[i].rchild=-1;h[i].parent=-1;判断h[j].parent==-1否h[j].parent==-1是获取最小的两个字符频度select()构成新结点返回主函数d.dehuffman()函数dehuffman()打开文件是判断文件是否为空否获取编码,执行以下过程if(ch=='1')root=h[root].rchild;elseroot=h[root].lchild;

7、否判断孩子结点是否为空是查找字符返回主函数3．重点设计及编码a.文件字符频度的获取：以字符的ASCII编码为数组下标，以数组元素值为频度，每读入一个字符进行元素值的加1，直至字符统计完毕，具体代码如下：FREQ*getCharsFreq(constchar*fileName,int*Count){FILE*fpin;FREQ*freq=NULL;intchars[256]={0};intcount=0;inti,j;charch;if((fpin=fopen(fileName,"r"))==NULL){print

8、f("打开失败,文件不存在！");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权值");for(