北京邮电大学信通院数据结构试验三——哈夫曼树试验报告

1、2009级数据结构实验报告实验名称：实验三一一哈夫曼编/解码器的实现学生姓名：陈聪捷日期：2010 年 11 月 28 日1.实验要求一、实验目的：了解哈夫曼树的思想和相关概念；二、实验内容：利用二叉树结构实现哈夫曼编/解码器1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5.打印：以直观的方式打印哈夫曼树。6.计算输入的字符串编码前和编码后的

2、长度，并进行分析，讨论哈夫曼编码的压缩效果。7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2 .程序分析2.1存储结构二叉树templateclassBiTreepublic:BiTree();BiTree(void);BiNode*Getroot();/protected:BiNode*root;/声明类BiTree及定义结构BiNodeData:二叉树是由一个根结点和两棵互不相交的左右子树构成/构造函数，其前序序列由键盘输入/析构函数获得指向根结点的指针/指向根结点的头指针哈夫曼树类的数据域，继承节点类型为int

3、的二叉树classHuffmanTree:publicBiTreedata:HCode*HCodeTable;/编码表inttSize;/编码表中的总字符数二叉树的节点结构templatestructBiNode/Tdata;/记录数据Tlchild;/左孩子Trchild;/右孩子Tparent;/双亲;示意图:TdataTlchildTrchildTparent编码表的节点结构structHCodechardata;/编码表中的字符charcode100;/该字符对应的编码;示意图：chardatacharcode100待编码字符串由键盘输入，输入时用链表存储，链表节点为structNod

4、e二叉树中的结点具有相同数据类型及层次关系charcharacter;/输入的字符二叉树的结点结构unsignedintcount;/boolused;/Node*next;/2.2 关键算法分析1.%2.初始化函数(voidHuffmanTree:Init(stringInput)算法伪代码：1.%2.%3.初始化链表的头结点2.%2.%3.获得输入字符串的第一个字符， 并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3.%2.%3.从字符串第2个字符开始，逐个取出字符串中的字符3将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链

5、表中该字符的权值加1。3如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n+4.%2.%3.tSize=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)5.%2.%3.创建哈夫曼树6.%2.%3.销毁链表源代码：voidHuffmanTree:Init(stringInput)Node*front=newNode;初始化链表的头结点if(!front)throwexception(堆空间用尽)；front-next=NULL;front-character=NULL;front-count=0;Node*pfront=front;charch=Input

6、0;/获得第一个字符Node*New1=newNode;if(!New1)throwexception(堆空间用尽)；New1-character=ch;将第一个字符插入链表New1-count=1;New1-next=pfront-next;pfront-next=New1;boolreplace=0;/判断在已经写入链表的字符中是否有与当前读出的字符相同的字符)；charcharacterunsignedintcountboolusedNode*next该字符的权值建立树的时候该字符是否使用过保存下一个节点的地址示意图:intn=1;统计链表中字符个数for(inti=1;inext;if

7、(int)pfront-character=(int)ch)(pfront-count+;replace=1;break;while(pfront-next);if(!replace)如果在链表中没找到与当前字符相同的字符，则将该字符作为新成员插入链表Node*New=newNode;if(!New)throwexception(堆空间用尽);New-character=ch;New-count=1;New-next=pfront-next;pfront-next=New;n+;2.创建哈夫曼树(voidHuffmanTree:CreateCodeTable(Node*p)算法伪代码：1.创建

8、一个长度为2*tSize-1的三叉链表2. .将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点的data域，并将对应结点的孩子域和双亲域赋为空3. .从三叉链表的第tSize个结点开始，i=tSize从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其下标x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点/如果在链表中有与当前字符相同的字符,该字符权值加1pfront=front;replace=0;tSize=n;CreateHTree(front,n);pfront=front;while(pfront)(front=pfront;pfront=pf

9、ront-next;deletefront;时间复杂度：若输入的字符串长度为/重置pfront和replace变量为默认值/tSize记录的是编码表中字符个数/创建哈夫曼树销毁整个链表n,则时间复杂度为O(n)将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. .根据哈夫曼树创建编码表源代码：voidHuffmanTree:CreateHTree(Node*p,intn)(root=newBiNode2*n-1;初始化哈夫曼树Node*front=p-next;if(n=0)throwexceptio

10、n(没有输入字符);for(inti=0;icount;rooti.lchild=-1;rooti.rchild=-1;rooti.parent=-1;front=front-next;front=p;intNew1,New2;for(i=n;inext;for(inti=0;icharacter;/将第i个字符写入编码表intchild=i;得到第i个字符对应的叶子节点intparent=rooti.parent;得到第i个字符对应的叶子节点的双亲intk=0;if(tSize=1)如果文本中只有一种字符，它的编码为0(HCodeTablei.codek=0;k+;while(parent!

11、=-1)从第i个字符对应的叶子节点开始，寻找它到根结点的路径(if(child=rootparent.lchild)如果当前结点为双亲的左孩子，则编码为0,否则编码为1HCodeTablei.codek=0;elseHCodeTablei.codek=1;k+;child=parent;parent=rootchild.parent;HCodeTablei.codek=0;Reverse(HCodeTablei.code);front=front-next;将编码逆置得到下一个字符cout编码表为：endl;for(i=0;itSize;i+)输出编码表(coutHCodeTablei.dat

12、aHCodeTablei.codeendl;)时间复杂度：需要遍历哈夫曼树获取编码，时间复杂度为O(nV)4 .选择两个最小权值的函数( (voidHuffmanTree:SelectMin(int&New1,int&New2,intbegin,intend)算法伪代码：.从下标为begin的结点开始，寻找第一个没用过的结点.遍历哈夫曼树中从下标为begin到下标为end的结点序列， 寻找没用过的同时权值又是最小的结点。.暂时改变找到的权值最小结点的双亲域，防止第2次找到相同的结点。.将权值最小结点的下标记录下来。.重复步骤14,找到第2个权值最小的结点源代码：voidHuff

13、manTree:SelectMin(int&New1,int&New2,intbegin,intend)intmin;for(intj=0;j2;j+)(要选择两个权值最小的结点intsign=begin;for(inti=begin;iend;i+)从下标为begin的结点开始，寻找第1个没用过的结点(if(rooti.parent=-1)(min=rooti.data;sign=i;break;)for(i=begin;irooti.data)(min=rooti.data;sign=i;)rootsign.parent=0;暂时改变所找最小结点的双亲域，防止第2次找到的是

14、同一个结点if(!j)New1=sign;elseNew2=sign;)时间复杂度：两次遍历链表，时间复杂度为O(n)5 .将字符串倒序的函数(voidHuffmanTree:Reverse(char*pch)算法伪代码：.得到字符串的长度.初始化两个记录下标的变量，一个为字符串开头字符所在的下标i,另个为字符串结尾字符所在的下标j.将下标为i和j的字符交换.i+,j-时间复杂度：时间复杂度为O(n)6.编码函数(voidHuffmanTree:Encode(string&s,string&d)算法伪代码：.从s开头的字符开始，逐一对s中的字符进行编码.在编码表中查找与当前字符

15、对应的字符.如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。.重复以上步骤，直到所有待编码串中的字符都编码完毕.输出编码后的字符串源代码：voidHuffmanTree:Encode(string&s,string&d)for(intj=0;js.length();j+)逐个对待编码字符串中的字符进行编码for(inti=0;itSize;i+)/在编码表中查找与当前字符对应的编码if(sj=HCodeTablei.data)d.append(HCodeTablei.code);/编码break;)coutdendl;/输出编码后的字符串)时间复杂度：设待

16、编码字符串长度为n,编码表中字符个数为m,则复杂度为O(n*m)7.解码函数(voidHuffmanTree:Decode(string&s,string&d)算法伪代码：.得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针.逐个读取待解码串中的字符，若为0,则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1,则指向当前结点的右孩子.指向待解码串的指针指向解码串中的下一个字符， 直到指向哈夫曼树结点的指针的孩子结点为空.如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的字符.如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应的字

17、符追加到解码串中。.输出解码串源代码：voidHuffmanTree二Decode(string&s,string&d)(parent=rootparent.lchild;else编码为1则寻找右孩子parent=rootparent.rchild;i+;i+;d.append(1,HCodeTableparent.data);将叶子节点对应的字符追力口至U解码串中)coutdendl;)时间复杂度：设待解码串长度为n,则复杂度为O(n)8 .计算哈夫曼编码的压缩比(voidHuffmanTree:Calculate(strings1,strings2)算法伪代码：.获得编码前

18、字符串的长度，即其占用的字节数.获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字节数3.压缩比将两个相除源代码：voidHuffmanTree二Calculate(strings1,strings2)(for(inti=0;is.length();)(intparent=2*tSize-1-1;while(rootparent.lchild!=-1)(if(si=0)得到哈夫曼树的根结点如果结点不为叶子结点/编码为0则寻找其左孩子)if(tSize=1)/如果编码表只有一个字符，则根结点即为叶子结点intcal1=s1.length();intcal2=s2.length();

19、cal2=ceill(float)cal2/8);将编码串的比特数转化为字节数cout编码前的字符串长度：cal1endl;cout编码后的字符串长度：cal2endl;cout压缩比为：(double)cal2/(double)cal1)*100%endl;时间复杂度：O(1).打印哈夫曼树(voidHuffmanTree:PrintTree(intTreeNode,intlayer)算法伪代码：.如果待打印结点为空，则返回.递归调用函数打印当前结点的右子树.根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打印当前结点的权值.递归调用函数打印当前结点的左子树源代码：voidHu

20、ffmanTree:PrintTree(intTreeNode,intlayer)(if(TreeNode=-1)/如果待打印结点为空，则返回return;else(PrintTree(rootTreeNode.rchild,layer+1);先打印该结点的右子树，layer记录的是该结点所在的层次for(inti=0;ilayer*2;i+)/根据该结点所在的层次，确定在它之前需要打印多少空格cout;coutrootTreeNode.dataendl;打印该结点的权值PrintTree(rootTreeNode.lchild,layer+1);打印该结点的左子树时间复杂度：中序遍历哈夫曼树

21、，复杂度为O(n).菜单函数(voidHuffmanTree:Menu()算法伪代码：.逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的string变量中，直到读到回车输入符为止.删除string变量末尾的回车输入符.利用string变量创建哈夫曼树，初始化编码表。.直观打印哈夫曼树.对输入的字符串进行编码.对编码后的字符串进行解码.计算编码前后的压缩比并输出源代码:Decode(d1,d2);coutASCII码编码与HUFFMANCalculate(Input,d1);2.3 其他由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入的字符串，并采用st

22、ring类的类成员函数来完成各项任务打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。为了输入空格，输入时采取逐个字符输入的方式3.程序运行结果主函数流程图：开始voidHuffmanTree:Menu()cout请输入你要编码的文本stringInput;charletter;doletter=cin.get();Input.append(1,letter);while(letter!=n);Input.erase(Input.length()-1,1);Init(Input);，按回车键确定输入endl;将字符逐个读入Input变量中/去掉Input末尾的回车符根据输入的字符串创建哈夫曼树及其编码表cout直观打印哈夫曼树PrintTree(2*tSize-1-1,1);coutnn;stringd1,d2;cout编码后的字符串为Encode(Input,d1);cout解码后的字符串为endl;endl;endl;打印哈夫曼树/编码并打印编码串解码并打印解码串编码的比较endl;计算编码前后的压缩比运行结果:请输入你要编码的文本，按回车键确定输入IlouedatastiMicture,Iloveconputer.I