哈夫曼编译码系统

1、数据结构课程设计说明书 哈夫曼树编码译码 学院（部）： 计算机科学与工程学院专业班级： 物联网工程12-2班 学 号： 2012303285 学生姓名： 陈喜慧 指导教师： 郝伟 起止时间： 2013年12月29日至2014年01月09日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 学 号2012303285学生姓名陈喜慧 专业（班级）物联网工程12-2班设计题目 哈夫曼码的编/译码系统 设计技术参数（1）用C+或C语言实现设计任务；（2）所设计的程序可读性好，执行效率高；（3）有良好的操作界面；（4）设计说明书能很好地反映设计内容设计要求（1）要求小组成员熟练掌握数据结构的基本

2、知识和技能； （2）基本掌握数据结构的基本思路和方法； （3）能够利用所学的数据结构基本知识和技能，解决简单的相关的问题；（5）熟练掌握树的遍历；（6）利用哈夫曼树进行通信的二进制编码。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2013.12.30-14.01.05 根据课程设计大纲的要求，查找相关资料，完成需求分析；2014.01.06 进行系统的概要设计；2014.01.07 进行系统的详细设计和源代码的书写；2014.01.08-14.01.09 对系统进行调试分析，写出课程设计报告。参考资料1 严蔚敏,吴伟民编著.数据结构（C语言版）,北京:清华大学出版社

3、,2002；2 严蔚敏,吴伟民,米宁编著.数据结构题集（C语言版）北京:清华大学出版社,1996；指导教师签字教研室主任签字 2014年 01 月 09日 学生姓名： 陈喜慧 学号： 2012303285 专业班级: 物联网工程12-2班 课程设计题目： 哈夫曼码的编/译码系统 指导教师评语：1：文档不要出现空白页2：目录需要重新引用，更新不对3：多余的标点符号需要删除4：分页符的放置位置不合理重新编辑5：需求分析下应该插入引言6：测试数据这个标题应该改一下，有歧义7：标题上不能加括号8：详细设计下需要插入引言9：文档不要有空行10：参考文件需要再添加几个11：系统运行这一小节可以放到运行调试

4、下面12：不需要完整源码，不需要用附录形式输出 （见评分表）成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表课程设计评分表课程设计评分标准分为前言、分析设计、主体内容、参考文献和排版五部分内容，每部分的得分标准参见下表。内容标准得分范围得分前言（10分）思路清晰，描述清楚。9-10思路基本清晰，描述基本清楚。6-8思路混乱，描述不清。0-5分析设计（30分）问题分析清楚，设计合理。25-30能够基本分析出关键问题，设计上基本能够满足要求。18-24分析问题有偏差，设计上存在问题。9-17分析有误，设计不能满足需求。0-8主体内容（30分）内容详实，能够充分表达整个课程设计的

5、内容。25-30内容完整，能够基本表达清楚课程设计的主要内容。18-24内容有缺失，无法清楚完整表达整个设计内容。9-17内容空洞，无法表达设计内容。0-8参考文献（10分）参考文献在10篇以上，引用合理。9-10参考文献5-9篇，基本与设计内容相符。6-8参考文献少于5篇，且内容相关性差。0-5排版（20分）严格按课程设计模板要求排版。17-20基本按照课程设计模板要求排版，有部分错误。12-16与课程设计模板有大量不符，排版存在很多错误。0-11总 分注1：整个课程设计内容必需完整，如果缺少某部分，该部分按0分处理。注2：主体内容包括总结或心得体会部分。评分人： 日 期： 目录1需求分析6

6、1.1问题描述61.2基本要求61.3测试要求71.4实现提示72总体设计92.1哈夫曼编译码器的算法思想92.2简单函数92.3利用简单操作实现的复杂功能92.4显示格式的实现103详细设计113.1编码函数123.2译码函数134调试分析155小结19参考文献201需求分析在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功

7、能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题haftree，对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走

8、左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电文，直到所有电文都遍历完为止，输出所有从电文中译码出来的信息。关键词：编译器；频度；译码1.1问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。1.2基本要求一个完整的系统应具有以下功能：（1）I:初始化（Initialization）。从终

9、端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P:打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T:打印哈夫曼树（Tree printin

10、g）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。1.3测试要求（1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY

11、FAVORITE”。字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 1.4实现提示（1） 编码结果以文本方式存储在文件CodeFile中。（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。（3） 在程序的一次执行过程中，第一次执行I，

12、D或E命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 2总体设计2.1哈夫曼编译码器的算法思想 本程序分为统计字符频度，构造哈夫曼树，确定哈夫曼码，翻译哈夫曼码四部统计字符频度：逐一输入字符，如没出现过则建立一结点存储此字符，并建立另一结点存储其频度为1。如出现过则使那个字符的频度结点加1；构造哈夫曼树：首先找到parent为0且weight最小的两个结点，并将他们合并为一个结点代替，weight为两者之和。在重复找parent为0且weight最小的两个结点。如此重复直到最后剩一个结点作为哈夫曼根结点；确定哈夫曼码：从叶子到根逆向

13、求编码，如是父结点的左孩子则码为“0”，如是父结点的右孩子则码为“1”；翻译哈夫曼码：接受“0”，“1”字符，从根结点开始，遇0访问左孩子，遇1访问右孩子，如果访问的是叶结点，则返回到根结点，继续查找。最后显示树状结构。 2.2简单函数 CreatHfmTree( weight, ch, n,HafNode) 操作结果：生成哈夫曼树 HaffmanCode (HafNode, n,Code) 操作结果：对哈弗曼树编码 InitHfmTree(weight, ch) 操作结果：初始化哈夫曼树 PrintCodeFile() 操作结果：打印代码文件 PrintTreeCode(HafNode *,

14、 n, p,FILE *) 操作结果：打印哈夫曼树结点 2.3利用简单操作实现的复杂功能 FileCoding() 操作结果：对文件进行哈弗曼编码 PrintTree() 操作结果：打印哈夫曼树 2.4显示格式的实现 Sheet() 操作结果：实现哈夫曼编译码器的操作表单3详细设计算法思想：1： void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) /w存放n个字符的权值(均>0),构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。首先初始化结点的成员，然后在HT1.i-1选择parent为

15、0且weight最小的两个结点，其序号分别为S1和S2开始建哈夫曼树，在这里为了区别叶子结点字符及方便以后操作，把非叶子结点的字符都初始化为“？”。最后从叶子到根逆向求每个字符的赫夫曼编码。2. void Initialization(HuffmanTree &HT, HuffmanCode &HC, int &n)/初始化,注意加引用符号。先判断hfmTree.txt文件是否存在，如果不存在就直接从终端读入字符集大小n，以及n个字符和n个权值，调用上述函数建立哈夫曼树，否则就读到内存中。由于字符可能是空格，所以要用getchar() 函数读入字符。用到的文本文件读写操

16、作如下：ifstream fin("hfmTree.txt", ios:in);/读出ofstream fout("hfmTree.txt", ios:out);/写入3. void Encoding(HuffmanCode & HC,int n)/对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。首先把正文用getline()函数一行一行读入字符串str中。编码过程，一个字符一个字符来，算法如下： for(i=0;stri!='0'i+)/编码过程，一个字符一个字符来 j=1; while(chj!=

17、stri&&j<=n) j+; if(j<=n) fout<<HCj;4 void Decoding(HuffmanTree HT, int n)/将文件CodeFile中的代码进行译码，结果存入文件TextFile中。由于文件中代码全是0、1，无空格，所以可以直接读入字符串str，译码过程，从根出发，按字符0或1确定找左孩子或右孩子，直至叶子结点，算法如下： i=0; j=m; while(i<len ) /len=str.size() if(stri='0') j=HTj.lchild; else j=HTj.rchild; i

18、f(HTj.lchild=0) fout<<chj; j=m; i+; 5 void Print(HuffmanTree HT, int n)/打印代码文件，将文件CodeFile以紧凑格式显示在终端上，每行50个代码。用对50取摸等于0来控制换行。6 void PrintTree(HuffmanTree &HT, int &n)/ 将已在内存中的哈夫曼树以凹入表形式显示在终端上。非叶子结点用权值表示，叶子结点用字符表示，其中为了便于区分层次，空格字符用#代替算法如下： for(l=m;l>0;l-) /m为根结点的权值 for(i=1;i<=2*n-1

19、;i+) if(HTi.weight=l) for(j=0;j<k;j+) /k 表示层数,r表示每层的结点数 cout<<" " fout<<" " /控制每层前面的空格 if(chi!='?') /如果是叶子结点就直接输出，否则输出权重 if(chi=' ') chi='#'/标记为空的字符 cout<<chi<<endl; fout<<chi<<endl; else cout<<HTi.weight<<

20、;endl; fout<<HTi.weight<<endl; p+;/p 表示每层的非叶子结点数 q+;/q 记录每层的结点数目 if(q=r) k+; r=2*p; p=0; q=0; /如果该层的结点满了，就到下一层，即k+1 3.1编码函数 以下是源程序中实现编码的部分：void Encoding(HuffmanCode & HC,int n) /编码 int i,j; string str,str1; ifstream fin("ToBeTran.txt",ios:in);/打开文件 ofstream fout("CodeF

21、ile.txt",ios:out); if(fin.fail() cout<<"文件ToBeTran.txt打开失败！"<<endl; getline(fin,str);/读入一行，可以读入空格 while(!fin.eof()/文件不结束 getline(fin,str1); str=str+str1; fin.close(); for(i=0;stri!='0'i+)/编码过程，一个字符一个字符来 j=1; while(chj!=stri&&j<=n) j+; if(j<=n) fout<

22、;<HCj; fout<<endl; fout.close();3.2译码函数 以下函数是源程序中实现译码部分： void Decoding(HuffmanTree HT,int n)/译码 int j,len,m; string str; m=2*n-1; ifstream fin("CodeFile.txt",ios:in); ofstream fout("TextFile.txt",ios:out); if(fin.fail() cout<<"文件CodeFile.txt打开失败！"<<

23、endl; return ; fin>>str; fin.close(); len=str.size(); i=0;j=m; while(i<len) /从根出发，按字符0或1确定找左孩子或右孩子，直至叶子结点 if(stri='0') j=HTj.lchild; else j=HTj.rchild; if(HTj.lchild=0) fout<<chj; j=m; i+; fout<<endl;4调试分析源码编写完成后经过调试无错误可以运行，进行运行：选择操作I：哈夫曼树已成功存入文件htmTree中建立ToBeTran.txt文件选

24、择操作E：对文件ToBeTran中的内容编码成功并成功存入文件CodeFile中选择操作D：对文件CoDeFile中的内容译码成功并成功存入文件TextFile中选择操作P:50个代码形式的代码成功编码并并成功写入文件CodePrint中选择操作T:哈夫曼树以凹入表的形式成功写入文件TreePrint中选择操作Q：退出系统 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：（1） 在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文

25、件，必定调试不通过。（2） 在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。（3） 由于对指针的使用不够灵活，使程序调试时费时不少。在权值的单行、换行和空格输入，也花了一些时间，不过最终能实现单个空格的输入。（4） 本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，把多次用到的代码分别写成一个函数，然后就可以直接调用了。（5） ToBeTran.txt开始并没有意识到要建立，以为是程序自己运行生成的导致总是读取失败，浪费了不少时间。（6） 算法的时空分析在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间。而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。（7） 本实验采用数据抽象的程序设计方法，将程序分为5个模块，使得设计时思路清晰，实现时调试可以顺利完成，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。5小结 通过本次数据结构的课程设计，我学习了不少之前上课没懂的知识。并在老