《数据结构》课程设计报告-哈夫曼编译码器程序设计.doc

数据结构课程设计报告哈夫曼编译码器程序设计班 级： 2012 级计算机科学与技术 学 号： 201225160106 姓 名： 指导老师： 提交日期： 2013年12月20日 摘 要在现代社会，通信的发展，使得现代社会更加丰富多彩，我们可以随时随地在任何地方了解到世界各地的信息，而这又必须依赖信息的传递。在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性和保密性和无损性，而著名的哈夫曼编码就能够达到这样的要求。哈夫曼编码是Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码（有时也称为霍夫曼编码）。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的不足直接制约了它的广泛应用。本设计主要介绍了哈夫曼编码算法、译码算法等功能的程序实现。关键词：数据结构；哈夫曼编码；哈夫曼树；译码AbstractIn modern society, the development of communication, making more colorful modern society, we can understand that information anywhere, anytime in any place around the world, which in turn must rely on the transmission of information. In todays highly developed information society, we have to pass information to a higher demand, we hope the information in the course of transmission, it is possible to save and maintain the confidentiality and non-destructive nature, and the famous Huffman coding can meet this requirement.Huffman Huffman coding is a coding method proposed in 1952, the method according to the probability of the characters appear completely different prefix to construct the shortest average length of codewords, sometimes referred to as the best coding, generally known as Huffman coding (Huffman coding is sometimes referred to). Huffman coding applied to how far an independent source for diverse independent sources for it is the best code. But its shortcomings directly restricts its wide application. This design introduces the Huffman coding algorithm decoding algorithm functions such program.Keywords: data structure;Huffman coding; Huffman decoding目 录1 引言12 需求分析22.1 数据分析22.2 功能要求23 概要设计33.1 设计思路33.2 抽象数据类型43.3 主程序流程53.4 各程序模块的关系64 详细设计74.1 数据类型的定义74.2 主要模块的描述84.2.1 主要模块算法描述84.2.2 主要算法流程图描述105 调试分析125.1 调试问题分析125.2 算法时空分析126 用户使用说明137 测试结果147.1 详细测试分析147.2 各种情况测试分析158 结论198.1 总结198.2 个人心得19参考文献20附录211 引 言电报曾经是人们进行快速远距离通信的重要手段，它将传送的文字一般使用二进制数传送数据。在发送端将数据转换成0、1序列（即编码），而在接收端又将0、1序列转换成对应的数据（即译码）。在传送电文时，采用哈夫曼方法对传输的电报进行编码，让电文中出现的次数较多的字符采用尽可能短的编码，这样的传输电文的总长度就会减少。哈夫曼编码是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于一种构建极小多余编码的方法（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。本设计主要介绍了哈夫曼树的构造，哈夫曼编码以及哈夫曼译码的主要算法，给出了哈夫曼编译码的程序的简单实现。将要求用户输入一行字符串而后程序将统计字符串中每个字符重复出现的次数并作为其权值。然后将这些字符及权值来构造一棵哈夫曼树，并对它们进行哈夫曼树编码，再根据这些哈夫曼树编码给出二进制串译出字符。2 需求分析2.1 数据分析1）输入的形式：输入一串字符串；在译码的时候输入一串由“0”和“1”组成的字符串。2）输入值的范围：字符串长度小于256（可根据需要进行修改）。3）输出的形式：编码时输出编码表，译码时输出原文字符串。4）程序所能达到的功能：对电文进行转换编码以及实现哈二进制串的译码。5）测试数据：一串包含数字、字母、符号的字符串；一串包含数字的字符串；一串包含字母的字符串；一串包含符号的字符串；一串包含数字、字母、符号、空格的字符串等情况；由所给出的哈夫曼编码组成的二进制串；随意的二进制串；随意的字符串。2.2 功能要求课程设计程序功能要求如下：1）生成哈夫曼树。2）哈夫曼树采用静态链表存储。3）求哈夫曼树对应的哈夫曼编码。4）给出哈夫曼编码译出字符。3 概要设计3.1 设计思路1）编写FrequencyCounter函数来实现统计用户输入字符串的字符及其次数。在统计用户输入的字符串中每个字符出现的次数时，假定这些字符都是ASCII码字符。可以预定一个字符表的结构，其中包含ASCII码表中的所有字符，以及该字符出现的次数。而后对用户输入的字符串进行遍历，若ASCII码表中某个字符在字符串中出现一次，那么将其对应在字符表结构中的次数加1。字符表结构的定义如下：typedef struct char data128;/ASCII码表中的所有字符int freq128; /每个字符出现的次数，初始为0CharTable;2）编写SelectCharactor函数来实现筛选字符表的0次字符。然而此时字符表中存在许多出现次数为0的字符，因此不能够直接通过得到的字符表来构造哈夫曼树，需要筛选那些字符表结构中次数为0的字符，剩下在字符串中出现过的字符及其权值。3）编写HuffmanTree函数来实现构造哈夫曼树，树结点保存在 huf 数组中。在获取这些字符及其权值后，就可以构建哈夫曼树：哈夫曼树的结点类型是左右孩子域、双亲域、数据域和权值域。哈夫曼树可以通过一个一维结点类型数组来表示。对于具有n个叶子结点的哈夫曼树，其结点个数为2n-1，若将这2n-1个结点用一个一维数组来储存，可以将叶子结点存放在数组的前n个位置，而将分支结点放在后n-1个位置。然后依次从huf数组中选出两个权值最小的根结点，并用它们来构造一棵新的二叉树，对于已经构造二叉树的结点不再参与二叉树的构造，而有它构成的二叉树的根结点就才参与新的二叉树的构造。4）编写HuffmanCode函数来实现构造哈夫曼编码，编码值保存在code数组中。每个结点的哈夫曼编码都是由0和1组成的序列，因此可以通过一个字符类型的数组来保存每个结点的哈夫曼编码；同时，由于每个结点的哈夫曼编码的长度是不同的，那么还需要增加一个标志域start来表示编码的起始位置，这样从start开始的所有的值都是编码值。哈夫曼编码的结构为：typedef struct char codeHUFFMAN_MAXVALUE1;/哈夫曼编码值int start; /编码起始位置 HufCode;在构造的哈夫曼树中，其结点都存放在数组huf中，并且该数组的前n个位置存放的叶子结点，而后n-1个位置存放的是分支结点。为了方便哈夫曼编码的实现，讲从叶子结点到根的路径进行编码。因此首先将哈夫曼编码的start域初始化为n，然后当结点为双亲结点的左孩子时，将编码赋值为0；否则赋值为1。同时将start值减1，直到到达根结点为止。5）编写HuffmanDecode函数来实现构造哈夫曼译码，字符串保存在recode数组中。在对二进制串进行译码时，首先从哈夫曼树的祖父结点开始，哈夫曼树的祖父结点就是哈夫曼树结点数组的最后一个，也就是2n-1个哈夫曼树结点，按照字符串中的“0”或“1”来查找左孩子结点或者右孩子结点。若达到叶子结点，叶子结点的左孩子域和右孩子域都是-1，则译出其中字符，而后再从根结点重新出发按照之前的顺序译出其他字符。3.2 抽象数据类型树的抽象数据类型定义：ADT Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：若D为空集，则称为空树。若D仅为一个数据元素，R为空集，否则R=H，H是如下的二元关系：1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。2）若D-root空集，则存在一个划分D1，D2，Dm（m0）。3）对应于D-root的划分，H-root，X1，有唯一的一个划分H1，H2，Hm（m0）。基本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T已存在。操作结果：树T被销毁。ClearTree(&T)初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmpty(T)初始条件：树T已存在。操作结果：若树T为空，则返回TRUE，否则FALSE。TreeDepth(T)初始条件:树T已存在。操作结果：返回T的深度。Root（T）初始条件：树T已存在。操作结果：返回树T的根。3.3 主程序流程主程序的流程图如图2.1所示：开始结束输入原文字符串统计出字符的频率 筛选频率不为0的字符构建哈夫曼树哈夫曼编码输出字符对应的哈夫曼编码 输入二进制串 哈夫曼译码输出原文字符串 图2.1 主程序流程图3.4 各程序模块的关系哈夫曼编译码程序主要是由以下几个模块组成：主程序模块、构造哈夫曼树模块、哈夫曼编码模块、哈夫曼译码模块、统计次数模块、筛选字符模块。主程序调用其它子函数，子函数之间没有进行互相调用，各程序模块的关系图如图2.2所示。构造哈夫曼树构造哈夫曼编码哈夫曼译码统计字符出现次数选出次数不为0的字符主程序图2.2 各程序模块的关系图4 详细设计4.1 数据类型的定义1）哈夫曼树结点结构类型：typedef struct nodetype node; /数据域weighttype weight;/权值域int parent; /双亲域int lchild; /左孩子域int rchild; /右孩子域 HufNode;2）哈夫曼编码结构类型：typedef struct char codeHUFFMAN_MAXVALUE1;/哈夫曼编码值int start; /编码起始位置 HufCode;3）字符表结构类型：typedef structchar data128;/ASCII码表中的所有字符int freq128; /每个字符出现的次数，初始为0 CharTable;4）程序中所需的一些其他类型定义：#define HUFFMAN_MAXVALUE32767 /默认权值最大#define HUFFMAN_MAXVALUE1 20 /默认编码长度typedef char nodetype; /定义char类型是哈夫曼码类型typedef int weighttype; /定义int类型是权值类型4.2 主要模块的描述4.2.1 主要模块算法描述1）构建哈夫曼树模块的伪码算法如下：void HuffmanTree(nodetype node, weighttype weight, int n,HufNode huf)int i,j=0,w1,w2,node1,node2;a(&n,&i,&node,&huf); /初始化哈夫曼树后，n-1个节点的权值域全为0for (i = n; i 2*n-1; i+)w1 = HUFFMAN_MAXVALUE;w2 = HUFFMAN_MAXVALUE;node1 = node2 = -1;for (int j = 0; j = i-1; j+)if(hufj.parent != -1) continue;if(hufj.weight w1)w2 = w1, node2 = node1;w1 = hufj.weight;node1 = j;else if(hufj.weight w2)w2 = hufj.weight;node2 = j;/置两个权值最小的节点及其双亲节点数据hufi.weight=hufnode1.weight+hufnode2.weight;hufi.lchild=node1,hufi.rchild=node2;hufnode1.parent=i,hufnode2.parent=i;2）构建哈夫曼编码模块的伪码算法如下：void HuffmanCode(HufNode node, int n, HufCode code)int i,parent,lchild;HufCode hufcode;for(i=0;in;i+) /计算每个叶子节点的赫夫曼编码hufcode.start=n;hufcode.codehufcode.start+1=0;lchild=i,parent=nodei.parent;a(&parent,&node,&hufcode,& lchild);/没有到达根节点，则编码继续hufcode.start+;codei=hufcode;3）哈夫曼译码模块的伪码算法如下：void HuffmanDecode(HufNode node, char *str, nodetype recode, int n)int i,j,k=0;j=2*n-2;for(i=0;stri!=0;j=2*n-2) /扫描整个字符串a(&I,&j,&node,&str) /找到叶子结点recodek+=nodej.node;recodek=0;4.2.2 主要算法流程图描述1）构建哈夫曼树模块的流程图如图3.1所示。两个权值最小的结点及其双亲结点数据否是否否结束开始i2*n-1i2*n-1后n-1个结点的权值域为0i+i+初始化最小结点，默认为-1ji-1否叶子结点权值小于w1得到最小较小权值赋值给w1，w2=w1得到最小较小权值赋值给w2j+是是是是否图3.1 构建哈夫曼树模块的流程图2）构建哈夫曼编码模块的流程图如图3.2所示。3）哈夫曼译码模块的流程图如图3.3所示。是否开始结束in初始化哈夫曼编码类型HufCode否是到达根结点左孩子相同否是左孩子编码右孩子编码i+下一个结点下一个叶子结点开始结束字符串结束是否是否是否字符为“0”没有左右孩子查找左孩子查找右孩子译出叶结点数据域图3.2 哈夫曼编码模块的流程图 图3.3 哈夫曼译码模块的流程图5 调试分析5.1 调试问题分析1）问题：输出字符串的时候，后面附带一部分乱码。解决方法：在字符串最后一个有效值的后面置0，结束字符串。2）问题：输入字符过多的时候不能正确编码。解决方法：增大字符串的存储空间。5.2 算法时空分析算法的时空说明如下所示，n表示输入的字符串的不同字符的个数。1）主函数的时间复杂度是S(128)（当n128时）；主函数的空间复杂度是T(1)；2）统计次数函数的时间复杂度是S(n2)；统计次数函数的空间复杂度是T(1)；3）筛选字符函数的时间复杂度是S(n)；筛选字符函数的空间复杂度是T(1)；4）构造哈夫曼树函数的时间复杂度是S(4n2)；构造哈夫曼树函数的空间复杂度是T(1)；5）哈夫曼编码函数的时间复杂度是S(n2)；哈夫曼编码函数的空间复杂度是T(n)；6）哈夫曼译码函数的时间复杂度是S(n2)；哈夫曼译码函数的空间复杂度是T(1)。6 用户使用说明程序运行的主界面后将需要用户根据以下要求进行使用：1）用户根据提示输入原文字符串。输入字符串之后程序就会输出相应的哈夫曼编码表，包括字符、出现次数和对应哈夫曼编码。2）用户根据编码成功的哈夫曼编码输入相应的二进制串。输入二进制串之后，程序就会输出译出对应的原文字符串。3）译码成功后根据提示是否继续译码，用户需要输入y or n。在程序输出译码完成的原文字符串之后将会提示是否继续译码，是以原来的哈夫曼编码进行重新的译码，需要用户输入y之后再一次输入需要译码的二进制串。4）不再进行译码时根据提示是否继续编译码，用户需要输入y or n。在程序输出译码完成的原文字符串并且不再继续译码之后，程序将会提示是否继续编译码，是以新的字符串进行重新的编译码，需要用户输入y之后再一次输入原文字符串。5）该程序在开头的时候会进行自动演示，指导用户如何进行操作。如图5.1所示。图5.1 自动演示7 测试结果7.1 详细测试分析输入的字符串是：i love you输入的二进制串是：101111110111101输入的字符串转换成字符分别是：sp（空格）、e、i、l、o、u、v、y；对应次数分别是2、1、1、1、2、1、1、1。构造出哈夫曼树如图6.1所示。sp/2o/1e/1i/1l/1u/1v/1y/122244610图6.1 哈夫曼树所有字符对应的哈夫曼编码分别为110、000、001、010、111、011、100、101。输入的二进制字符串的时候，从根结点开始，依次根据“0”或者“1”，查找左孩子和右孩子，直到找到叶子结点，以字符101译码过程为例进行分析，如图6.2所示。sp/2o/1e/1i/1l/1u/1v/1y/122244610101图6.2 字符101的译码过程程序测试的结果如图6.3所示。图6.3 测试结果7.2 各种情况测试分析1）输入字符串为Data Strutures（由大小写字母和空格组成）输入二进制串为 00110011100111100011110001000100结果如图6.4所示。图6.4 测试用例12）输入字符串为201312182013（由数字组成）输入二进制串为 01101110111101100结果如图6.5所示。图6.5 测试用例23）输入字符串为78jfjs _-+sj =.（由字母、数字、符号和空格组成）输入二进制串为 0000111101111110110100100结果如图6.6所示。图6.6 测试用例34）输入字符串为huhugug78 78gh（由字母、数字和空格组成）输入二进制串为 111000102101（出现非二进制字符在字符串中）只完成非二进制字符前的译码，遇到非二进制将会停止并警告。结果如图6.7所示。图6.7 测试用例45）输入字符串为huhugug77（由字母和数字组成）输入二进制串为 +0001（出现非二进制字符在字符串首）遇到非二进制将会停止并警告，非二进制在字符串首直接停止。结果如图6.8所示。图6.8 测试用例56）输入字符串为njnjnjwxwxwx（由字母组成）输入二进制串为 11100001测试译码完成是否继续正确译码，测试编译码完成是否继续编译码。结果如图6.9所示。图6.9 测试用例68 结 论8.1 总结在当今信息时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。正因为哈夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。但是采用哈夫曼编码时有个问题值得注意：哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的数据串也会接着被译错，全乱了套，这种现象称为错误传播(errorpropagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。8.2 个人心得通过这次课程设计使我充分的理解了用哈夫曼树编码译码问题中基本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码译码问题的程序。虽然此次的程序不够完善，但是总体还是一个能体现数据结构知识点能力的程序。在刚开始编程的时候，无从下手。但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才还有一个比较满意的成果。在此我要感谢的是我的指导老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了跟深刻的认识，同时我还要感谢帮助过我的同学，没有他们的帮助我不肯能完成这样顺利，谢谢。参考文献1 陈越.数据结构M.第一版.北京:高等教育出版社,2012:142-150.2 郑阿奇.数据结构实用教程（C语言版）M.第一版.北京:电子工业出版社,2011:170-179.3 张基温.新概念C程序设计大学教程M.第一版.北京:清华大学出版社,2012:143-155.4 严蔚敏,吴伟民.数据结构（C语言版）M.第一版.北京:清华大学出版社,2011:203-206.5 克尼汉.C程序设计语言M.第二版.北京:机械工业出版社,2004:111-130.附 录#define HUFFMAN_MAXVALUE32767#define HUFFMAN_MAXVALUE1 20#include#include#includetypedef char nodetype;typedef int weighttype;typedef struct nodetypenode;/数据域weighttype weight;/权值域int parent;/双亲域int lchild; /左孩子域int rchild; /右孩子域HufNode;typedef struct charcodeHUFFMAN_MAXVALUE1;/哈夫曼编码值intstart;/编码起始位置 HufCode;/字符表结构typedef struct chardata128;/ASCII码表中的所有字符intfreq128;/每个字符出现的次数，初始为0CharTable;void HuffmanTree(nodetype node,weighttype weight,int n,HufNode huf);/构造哈夫曼树，树节点保存在 huf 数组中void HuffmanCode(HufNode node,int n,HufCode code);/构造哈夫曼编码，编码值将保存在code数组中void HuffmanDecode(HufNode node,char *str,nodetype recode,int n);/哈夫曼译码int FrequencyCounter(char *str,CharTable *table,int n);/统计字符出现的次数int SelectCharactor(CharTable *org,int n,CharTable *res);/选出出现次数不为0的字符void autoout();/自动演示/程序主函数int main()int i,j,n;char k=y,l=y;char string256;/保存用户输入的缓冲区HufNode *hufnode;/哈夫曼树节点HufCode *hufcode;/哈夫曼编码nodetype *hufdecode;CharTable table;/初始字符表CharTable chars;/不包含次数为0的字符表autoout(); /自动演示while(k!=N&k!=n)l=y;for(i=0;i请输入需要编码的字符串：); gets(string); /统计字符出现的频率 n = FrequencyCounter(string, &table, 128); /统计字符出现的次数 n = SelectCharactor(&table ,128, &chars);/选出次数不为0的字符 /构造哈夫曼树 hufnode = (HufNode*)malloc(2*n+1) * sizeof(HufNode); HuffmanTree(chars.data, chars.freq, n, hufnode); /哈夫曼编码 hufcode = (HufCode*)malloc(n * sizeof(HufCode); HuffmanCode(hufnode, n, hufcode); printf(n 原文字符t出现次数tHaffman 编码n); printf(=n); /输出哈夫曼编码值 for(i=0; i请输入需要译码的二进制串：); gets(string); hufdecode = (nodetype*)malloc(256 * sizeof(nodetype); HuffmanDecode(hufnode,string,hufdecode,n); printf(n译码完成的原文字符串是：%sn,hufdecode);printf(n译码完毕，是否继续译码？(Y/N); scanf( %c,&l);getchar(); printf(n哈夫曼编译码器编译码完毕，是否继续?(Y/N); scanf( %c,&k);getchar();printf(n - n);printf(ttt感谢使用哈夫曼编译码系统n);getchar();/free(hufnode);/free(hufnode);return 0;/构造哈夫曼树，树节点保存在 huf 数组中void HuffmanTree(nodetype node,weighttype weight,int n,HufNode huf)int i,j=0,w1,w2,node1,node2;for (i = 0; i 2*n-1; i+)/初始化哈夫曼树hufi.node = in ? nodei : 0;hufi.weight = in ? weighti : 0;/后n-1个节点的权值域全为0hufi.parent = hufi.lchild = hufi.rchild = -1;for (i = n; i 2*n-1; i+)w1 = HUFFMAN_MAXVALUE;w2 = HUFFMAN_MAXVALUE;node1 = node2 = -1;for (int j = 0; j = i-1; j+)/寻找两个权值最小的节点node1和node2if(hufj.parent != -1) continue;if(hufj.weight w1)w2 = w1, node2 = node1;w1 = hufj.weight;node1 = j;else if(hufj.weight w2)w2 = hufj.weight;node2 = j;/置两个权值最小的节点及其双亲节点数据hufi.weight=hufnode1.weight+hufnode2.weight;hufi.lchild=node1,hufi.rchild=node2;hufnode1.parent=i,hufnode2.parent=i;/构造哈夫曼编码，编码值将保存在code数组中void HuffmanCode(HufNode node,int n,HufCode code)int i,parent,lchild;HufCode hufcode;for(i=0;in;i+)/计算每个叶子节点的赫夫曼编码hufcode.start=n;hufcode.codehufcode.start+1=0;lchild=i,parent=nodei.parent;while(parent != -1)/没有到达根节点，则编码继续if(nodeparent.lchild=lchild)hufcode.codehufcode.start=0;/左孩子编码elsehufcode.codehufcode.start=1;/右孩子编码hufcode.start-;lchild=parent,parent=nodeparent.parent; hufcode.start+;codei=hufcode;/哈夫曼译码vo