哈夫曼编译码器课程设计报告.doc

哈夫曼编码/译码器一 目的通过本次课程设计：复习学过的数据结构的内容；巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解，这里主要用到二叉树和栈；掌握现实复杂问题的分析建模和解决方法；提高利用计算机分析解决综合性实际问题的基本能力。二 需求分析目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二进制的字符组成的字符串。在传送电文时，希望总长度尽可能地短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长度便可减少。如果要设计长短不等的编码，则必须是任一个字符的编码都不是另外一个字符的编码的前缀，这种编码叫前缀编码。设计电文总长最短的二进制前缀编码，要以n种字符出现的频率做权，设计一棵哈夫曼树，由此得到的二进制前缀编码就叫做哈夫曼编码。编码时，从待编译文件ToBeTran.txt中获得出现的字符及其出现的次数（出现次数即为此字符的权值）；或从终端获取各个字符及其权值据此建立哈夫曼树。建好的哈夫曼树以凹凸表的形式存到文件TreePrint.txt中。利用建好的哈夫曼树对各个字符进行编码，编得的哈夫曼码存到文件HuffmanCodes.txt中。利用已建好的各字符的哈夫曼码对ToBeTran.txt进行逐字编码，编好的二进制字符串存到文件CodeFile.txt中。在编码期间，用户可以选择是否观看：建好的哈夫曼树；建好的各字符的哈夫曼码；ToBeTran.txt中的原文；原文经编译产生的二进制字符串。译码时，从HuffmanCodes.txt中获取各字符的哈夫曼码，据此建好哈夫曼树，然后利用建好的哈夫曼树对文件CodeFile.txt中的二进制字符串进行译码，将二进制字符串译成对应字符集，并把它们存到文件TextFile.txt中。 在译码期间，用户可以选择是否观看：CodeFile.txt中的哈夫曼码集；建好的各字符的哈夫曼码；哈夫曼码集经译码产生的字符集。三 概要设计1、程序抽象数据类型的定义（1）typedef structchar character;/字符unsigned int weight;/权值unsigned int parent;/父母节点unsigned int lchild;/左孩子unsigned int rchild;/右孩子HTNode,*PHTNode,*HuffmanTree; HuffmanTree：哈夫曼树；HTNode：哈夫曼树的节点；PHTNode：指向哈夫曼树节点类型数据的指针类型。（2）typedef HTNode StackElementType;typedef structStackElementType *base;/栈底指针，在栈构造前和销毁后，base的值为0 。StackElementType *top;/栈顶指针。int stack_max_capacity;/栈的最大容量。int stack_length;/栈当前的长度。SqStack;SqStack：栈（在打印哈夫曼树前建立凹凸表时用到，程序的核心部分没有用到栈。）（3）typedef int Status;Status：函数的返回类型，0代表成功，1代表不成功。2、程序含三个模块（1）主程序模块打印菜单；让用户选择是编码还是译码；让用户决定是否观看一些信息。（2）编码模块Status Initialization(HuffmanTree& HT);初始化哈弗曼树，统计待编码文件ToBeTran.txt中各字符出现次数并记入哈弗曼树中；Status CreatHuffman(HuffmanTree& HT);已知各字符出现次数，据此建立哈弗曼树；Status HuffmanCoding(HuffmanTree& HT,HuffmanCode& HC);已建好哈弗曼树，据此对各字符进行编码，并将各字符的哈弗曼码存到HuffmanCodes.txt中；Status TextCoding(HuffmanTree& HT,HuffmanCode& HC);对ToBeTran.txt中的文字编码，结果存入CodeFile.txt中。（3）译码模块Status CreatHuffmanTree2(HuffmanTree& HT);读HuffmanCodes.txt，建立哈夫曼树；Status TextDecoding(HuffmanTree& HT);建好哈弗曼树后，读CodeFile.txt 把哈弗曼码译为字符并存到TextFile.txt中。3、程序中用到的其它函数（1）打印相应东西到屏幕上的3个函数Status ShowText(char *filename);读文件，把里面的字符打到屏幕上。Status ShowTree(HuffmanTree& HT);哈夫曼树已建好，把哈夫曼树以凹凸表形式打印到屏幕上。Status ShowHuffmanCodes();各个字符的哈夫曼码已建好并已存于HuffmanCodes.txt中，把各字符的哈夫曼码打印到屏幕上。（2）栈的6个函数Status InitStack(SqStack& S);Status Push(SqStack& S,StackElementType E);Status Pop(SqStack& S,StackElementType& E);Status GetTop(SqStack& S,StackElementType& E);Status FindSame(SqStack& S,StackElementType& E);Status DestoryStack(SqStack& S);4、程序流程图（1）主函数流程图（2）编码模块流程图（3）译码模块流程图四 详细设计1、编码时建立哈夫曼树前提：初始化哈弗曼树， 统计待编码文件ToBeTran.txt中各字符出现次数并记入哈弗曼树中，即已经知道了各字符及其权值。功能：建立哈夫曼树。char charsN=' ','e','t','a','o','i','n','r','s','h','d','c',',','.','l','m','p','u','f','g','w','y','b','v',''','n','k','x','j','q','z'Status CreatHuffman(HuffmanTree& HT)int i,smallest1,smallest2,m=2*N-1;统计权值不为零的字符;m=权值不为零的字符的个数;for(i=N+1;i<=m;i+)/建立哈弗曼树，每循环一次少一棵子树/选择两棵权值最小的子树，smallest1是靠前的那棵Select(HT,i-1,smallest1,smallest2);利用储存哈夫曼树的数组的新的一个空间，把此空间的左子树设为下标为smallest1的节点，右子树设为下标为smallest2的节点；把下标为smallest1和smallest2的节点的父母节点都设为新利用空间；return OK;2、对ToBeTran.txt中的原文进行编码前提：HC中储存着各个字符的哈夫曼码。功能：把原文中的各个字符翻译为这个字符对应的哈夫曼码存于文件中。Status TextCoding(HuffmanTree& HT,HuffmanCode& HC)FILE *fp,*fp2;fp打开待译文件ToBeTran.txt；fp2打开CodeFile.txt；/将把原文译得的二进制字符串写到里面。/逐个读ToBeTran.txt中的字符 在HT对应位置找到该字符的码 把码打到CodeFile.txt中while(ch=fgetc(fp)!=EOF)int p=1;/从待译文件中读到一个字符ch，寻找ch在HT中的位置while(ch!=(*(HT+p).character)p+;fputs(HCp,fp2);/把该字符对应的哈夫曼码写到CodeFile.txt中。return OK;3、译码时建立哈夫曼树前提：CodeFile.txt存在且里面已存有译好的二进制字符串， HuffmanCodes.txt存在且里面存有编好的各字符的哈夫曼码，并且这两个文件里的内容是同一个编码实例产生的。功能：利用HuffmanCodes.txt建立哈夫曼树。Status CreatHuffmanTree2(HuffmanTree& HT)for(i=1,p=HT+1;i<=m;i+,p+)/对哈弗曼树进行初始化 (*p).character='#' (*p).lchild=0; (*p).rchild=0;FILE *fp;fp打开HuffmanCodes.txt；/这样可获取每个字符的哈夫曼码。char ch;int s=0;/s代表chars中的位置int q=1;/q是未入哈弗曼树的第一个节点的下标while(ch=fgetc(fp)!=EOF)HuffmanCodes.txt中哈夫曼码为1的字符不做处理，continue；/其它的做以下处理：int z=1;while(遍历该字符的哈夫曼码的每一位)读此字符的哈夫曼码的每一位，为0的则利用储存哈夫曼树的数组的第一个未被利用的空间，把此空间设为已利用的空间的右孩子，为1的设为左孩子;非叶子节点的character都设为#;叶子节点的character设为对应字符;return OK;4、对CodeFile.txt中的二进制字符串进行译码前提：哈夫曼树已建好，CodeFile.txt存在且里面存有满足一定条件的二进制字符串。功能：对CodeFile.txt中的二进制字符串进行译码，译得的原文存于TextFile.txt中。Status TextDecoding(HuffmanTree& HT)FILE *fp,*fp2;fp打开CodeFile.txt；fp2打开TextFile.txt；char ch;while(ch=fgetc(fp)!=EOF)int s=1;/从数组1位置 即根节点开始往下走 根节点作为父母节点while(ch=fgetc(fp)!=EOF)/又读了一位 因为每个字符的码的第一位都是0 故要忽略if(ch='0') s=HTs.rchild;/从节点HTs往下走了一层 付给s新值 s为新的父母节点的下标。else s=HTs.lchild;if(HTs.character='#') continue;/如果新的这层的节点内存有'#' 则应continue 。else fputc(HTs.character,fp2); break;/直到读到非'#'时break 说明此时一段哈码已被译为一个字符 则可开始一段新的哈码。return OK;五 调试分析待添加的隐藏文字内容11、调试内容一作用：测试编码模块建好的哈夫曼树是否和预期的一致。路径：main()->Initialization(HT)-> CreatHuffman(HT)。发现的问题及解决策略：对哈夫曼树的初赋值应该分成两部分，前半部分储存字符，后半部分储存非叶子节点；储存哈夫曼树的数组，出现频率高的字符放在数组靠前的位置，这样子在统计ToBeTran.txt中各字符出现次数时可减少寻找对应字符的时间；CreatHuffman(HT)中，有一个while循环的循环次数，原来设为N+1<=i<=2*N-1，但运行不出正确结果，经调试发现，while循环的循环次数不是一个固定的值，而是需要编码几种字符就循环几次，所以后来就设了个计数器来记录有几种字符需编码，这个问题就解决了。2、调试内容二作用：测试译码模块建的哈夫曼树是否和预期的一致。路径：main()->CreatHuffmanTree2(HT)。发现的问题及解决策略：因为char charsN这个数组不涉及到对它的改变且至少有三个函数用到它，所以适合设为全局变量；因为各个字符的哈夫曼码都是以“0”开头的，所以可以忽略这个“0”，建哈夫曼树时，可以减少使用一个节点，且在后来的译码中，每一个需翻译的原文字符都少走了一步（解释：译码时，要从根节点走到叶子节点，叶子节点里储存的是该路径下对应的字符，而该路径就代表一个哈夫曼码）。3、调试内容三作用：测试以凹凸表打印哈夫曼树的模块是否正确。路径：main()->Initialization(HT)à CreatHuffman(HT)à ShowTree(HT)。发现的问题1：不能正确打印出哈夫曼树。解决策略：修改路径为main()->Initialization(HT)à HuffmanCoding(HT,HC)-àCreatHuffman(HT)à ShowTree(HT)。结果：可以正确打印哈夫曼树了。原因：未找到。发现的问题2：在Status ShowTree(HuffmanTree& HT)这个函数中，char *dir开辟的空间在本函数快结束时只要释放就会在运行时产生错误。解决策略：把释放空间的代码注释，让这块未释放的空间在程序停止运行后由系统自动收回。结果：可以正确运行了，但是这个问题只是被隐藏了，并没有真正解决。原因：未找到。4、调试用到的环境VC+6.0。六 测试结果1、编码测试数据（存于ToBeTran.txt中）经编译后得到的各字符的哈夫曼码（存于HuffmanCodes.txt中，并可以在屏幕上显示）经编译产生的二进制字符串（存于ColdFile.txt中）2、译码测试数据：见“1，编码”部分的第四个截图测试结果（存于TextFile.txt中）七 用户使用说明1、主界面在此界面下有三个选项（1：编码；2：译码；3：退出。），用户可以输入对应的数字再敲回车键执行相应功能。2、编码（正确运行情况下）编码前请确认文件夹内已有文件ToBeTran.txt（已存有待译原文）、HuffmanCodes.txt（将存储编译得到的各字符的哈夫曼码）、CodeFile.txt（将存储编译原文得到的哈夫曼码集）、HuffmanTree.txt（将把哈夫曼树存入此中）。获得字符及其权值有两种方法：1，读待译文件统计出现的字符及其权值；2，从键盘输入各字符及其权值。这里用第1种方法。在此期间，用户可选择查看：建好的哈夫曼树（以凹凸表的形式）、各字符的哈夫曼码、ToBeTran.txt中的原文、原文经编译产生的哈夫曼码集。3、编码（错误输入情况下）在此次实例中，ToBeTran.txt中拥有全部的小写字母及英文空格、英文逗号、英文句号、英文单引号，但是在从终端输入字符及其权值时，只输入了abcdef六种字符，结果，原文经编码得到二进制字符串是不对的。这是因为，程序把原文中除abcdef以外的字符都编码为1，这样，就得到了截屏中看到的CodeFile.txt中的二进制字符串。用户最好是用“从待编译文件ToBeTran.txt中获得出现的字符及其出现的次数”这种方法来建立哈夫曼树，这样可保证建好的电文二进制字符串最短。而若从终端输入字符及其权值，则有三个弊端：1，需注意输入的字符正是待译文件中存在的字符（若待译文件中没有的字符却从终端输入了该字符，则程序可得到正确运行结果；若待译文件中有的字符而终端没有输入，程序虽然能够运行，但得到的结果是错误的）；2，用户输入的字符的权值不一定和待译文件中对应字符的出现次数相符合（这样译得的二进制字符串就可能不是最短的了）；3，浪费时间。4、译码译码前请确认文件夹内已有文件HuffmanCodes.txt（已存有每个字符的哈夫曼码）、CodeFile.txt（已存有原文的哈夫曼码集）和TextFile.txt（将存入译得的原文）。在译码期间，用户可以选择是否观看：CodeFile.txt中的哈夫曼码集；建好的各字符的哈夫曼码；哈夫曼码集经译码产生的字符集。八 课程设计总结做这个课程设计，最开始想向要求的那样，从终端输入字符及其权值，但是逐渐考虑到刚刚在用户手册中提到的用这种方法的三个弊端，于是就开始想另外一种获得字符集及其权值的方法，就这样，“从待编译文件ToBeTran.txt中获得出现的字符及其出现的次数”这样的方法诞生了。但是随后还是把“从终端输入字符及其权值”这种建哈夫曼树的方法也加到了程序里，供用户二选一。用“从待编译文件ToBeTran.txt中获得出现的字符及其出现的次数”这样的方法去建哈夫曼树，需事先罗列出待译文件中所有的可能出现的字符，若待译文件中恰好有这个字符，就建它的哈夫曼码，若没有这个字符，则这个字符的哈夫曼码设为“1”，因为其它正常的字符的哈夫曼码开头的一位都是“0”，这样子就可以把两种字符区分开来。事后证明，在打印各字符的哈夫曼码时，打印哈夫曼树时，接收方建哈夫曼树时（在下一段将详细提到），这种区分是很有必要的。本课程设计要求的是建好哈夫曼树编译了待译文件，然后利用这棵已建好的哈夫曼树，把二进制字符串翻译为原文。考虑到在实际应用中，编译待译文件时建好的哈夫曼树在发送文件方的电脑内存中，而发送文件方只能把二进制字符串发送给接受文件方，所以接受文件方的电脑内存中肯定没有现成的哈夫曼树可以使用，他只能自己另建一棵。这个是本程序的难点，就是接受文件方要依据些什么东西才能建一棵和发送文件方一样的哈夫曼树。于是我想到，发送方要把各字符的哈夫曼码随同译好的二进制电文一同发送给接收方，接收方要和发送方使用相同的字符顺序，这样接收方就可以知道各个字符的哈夫曼码，他就依据这个可以再建一棵哈夫曼树（接收方的哈夫曼树形态上和发送方的大大不同，但实质上一模一样）。写这个程序遇到的另一个难点是怎样把哈夫曼树以凹凸表的形式打印到屏幕上。一开始想用递归，但是这样不好确定哈夫曼各个节点在屏幕上相应的位置。其实我们上学期也写过以凹凸表形式打印二叉树的一个程序，但那个程序里的二叉树是以二叉链表的形式储存的，而本程序的哈夫曼树（二叉树的一种）是以数组形式储存的，一开始我以为那个程序的方法在本程序中不适用。后来因为想不到其它方法，就考虑能否用那个程序的方法放在本程序中使用。结果发现，我只改动了少许地方就可以了。从这一点上我认识到，二叉树是以什么方式储存的不重要，最重要的是对二叉树的一些操作对于不同储存类型的二叉树是普遍通用的。另外，因为未学扎实，程序中还有至少两个未解决的问题。这在“调试分析”中提到过。这两个问题通过其它的一些措施可以避免错误的运行，但终究是没有彻底解决，需在课程设计被检查完以后，再花些时间搞懂。总之，通过此次的课程设计，我又复习了一遍二叉树、栈等数据结构里的知识点，加深了对它们的理解，对使用这些数据结构更加熟练了；又重新略看了一遍C语言程序设计教程，回想起了C语言的很多细节，还找到了一些以前没有注意到的C语言的细节；对使用编译器也更加熟练了。