北邮数据结构实验三-哈夫曼树

1、数据结构实验报告实验名称：实验三树学生姓名：TOC o 1-5 h z班级：班内序号：学号：日期：1实验目的通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解哈夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力实验内容：利用二叉树结构实现哈夫曼编/解码器。基本要求：1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Dec

2、oding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print):以直观的方式打印哈夫曼树(选作)6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。(选作)7、可采用二进制编码方式(选作)测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.2程序分析2.1存储结构：三叉树：classHuffmanprivate:HNode*HTree;/P合夫曼树结点HCode*HCodeTable;/哈夫曼编码表charb1000;记录所有输入内容被

3、编码后的结果charc127;charletter1000;输入内容的保存voidSelectMin(int&x,int&y,intk);/求最小权重的字符node*count;计算各个字符出现次数intn;/输入字符的种类(个数)intl;public:Huffman();voidCreateHTree();创建哈夫曼树voidCreateCodeTable();/创建哈夫曼编码表voidEncode。;/编码voidDecode。;/解码;结点结构为如下所示：三叉树的节点结构：structHNode/哈夫曼树结点的结构体intweight;/结点权值intparent;/双亲指针intlc

4、hild;/左孩子指针intrchild;/右孩子指针chardata;/字符;示意图为：intweightintparentintlchildintrchildchardata编码表节点结构：structHCode/编码表结构体chardata;/字符charcode100;编码内容;示意图为：chardatacharcode100基本结构体记录字符和出现次数:structnodeintnum;chardata;示意图为:intnumchardata2.关键算法分析(1).初始化:伪代码：输入需要编译的文本内容将输入的内容保存到动态建立的node型数组count中统计出现的字符种类的数目，并

5、且保存到private型变量nHuffman:Huffman()/将输入数据保存到Huffman类中l=0;n=0;count=newnode127;coutvv请输入需要编译压缩的内容vvendl;cin.getline(letter，200，n);for(intj=0;jv127;j+)/一个号码代表一种字符countj.num=0;while(letterl!=O)在结束之前，每输入一个字符，贝V对应字符的数目则自增1+countletterl.num;countletterl.data=letterl;+l;for(intk=0;k0)n+;在某个字符出现此书num不为0时，n自增1,

6、最终n为出现的字符种类数目其时间复杂度为O(n)(2).创建哈夫曼树(voidHuffmanTree:CreateCodeTable(Node*p)算法伪代码：创建一个长度为2*n-1的三叉链表将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空从三叉链表的第n个结点开始，3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其下标x,y。3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲

7、设置为空根据哈夫曼树创建编码表源代码为：voidHuffman:CreateHTree()l=0;HTree=newHNode2*n-1;建立含有n种字符的哈夫曼树只需要2*n-1个结点即可for(inti=0;in;i+)while(countl.num=0)如果count内的权重为0,即该字符没有出现，则跳过，i自增继续寻找出现过的字符l+;HTreei.weight=countl.num;/将count里统计的次数传入哈夫曼树的节点中，作为字符权重HTreei.lchild=-1;HTreei.rchild=-1;HTreei.parent=-1;/将左右孩子结点和父节点都置空HTree

8、i.data=countl.data;/将count内的有效字符传入哈夫曼树的结点l+;intx=-1,y=-1;for(inti=n;iv2*n-1;i+)开始建立哈夫曼树SelectMin(x,y,i);/挑选三者中的权重较小的两个HTreex.parent=HTreey.parent=i;/令较小的x、y为孩子节点，该两个结点的父节点是iHTreei.weight=HTreex.weight+HTreey.weight;/i结点字符的权重赋为是左右孩子字符权重之和HTreei.lchild=x;左孩子为xHTreei.rchild=y;/佑孩子为yHTreei.parent=-l;父节点

9、置空x=-1;y=-1;将x、y重新赋值为零，进行下一次比较建树其时间复杂度为：O(n)(3)创建编码表算法伪代码：初始化编码表初始化一个指针，从链表的头结点开始，遍历整个链表将链表中指针当前所指的结点包含的字符写入编码表中得到该结点对应的哈夫曼树的叶子结点及其双亲如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0如果不止一个叶子结点，从当前叶子结点开始判断如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为1child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复2.4.1的操作将已完成的编码倒序取得链表中的下一个字符3输出编码表源代码为：voidHuff

10、man:CreateCodeTable()/建立哈夫曼编码表HCodeTable=newHCoden;/建立动态编码表for(inti=0;in;i+)HCodeTablei.data=HTreei.data;intchild=i;intparent=HTreei.parent;intk=0;while(parent!=-1)if(child=HTreeparent.lchild)判断该节点是父节点的左孩子或右孩子，左孩子则编码为0，右孩子则编码为1HCodeTablei.codek=0;elseHCodeTablei.codek=1;k+;child=parent;将该节点的父节点作为新的孩

11、子节点，继续进行编码输出parent=HTreechild.parent;HCodeTablei.codek=0;/code数组以0结尾Reverse(HCodeTablei.code);由于是从下到上输出，顺序是相反的，所以还需要逆置才能输出字符的编码值coutvvendlvvendlvv每个字符的编码为：vvendl;for(inti=0;in;i+)coutwHCodeTableMdatavv：wHCodeTableUcodevvendl;/逐个输出对应的字符和其编码其时间复杂度为：O(n)选择两个最小权值的函数voidHuffman:SelectMin(int&x,int&y,intk

12、)算法伪代码：从下标为i=0的开始遍历。前两次将x，y赋值为序号最小的两个结点的地址序号。开始进行比较：进行如下分类对于任何不存在父节点的结点：若x权值=y权值且i权值=y权值，贝9无疑i权值最大，为输出x、y为权值较小的两个故而x，y值不便；其余情况皆为x、i的权值是较小的两个，令y赋值为i,则保证x、y权值是最小的两个。若y权值=x权值且i权值=x权值，则i权值是最大，x、y不变。其余情况皆为i、y权值最小，令x赋值为i,保证x、y序号结点的权值最小完成如上循环，直至i=k则推出循环，第k个结点在树的位置已经确定源代码为：voidHuffman:SelectMin(int&x,int&y,

13、intk)/选出权值较小的两个字符结点inti=0;while(ivk)while(ivk&HTreei.parent=-l)若结点不具有父结点且满足ivk则进行如下循环，建立新子树if(x=-1)x=i;elseif(y=-1)y=i;elseif(HTreex.weight=HTreey.weight)if(HTreey.weightHTreey.weight)if(HTreei.weight=HTreex.weight)x=x;y=y;elsex=i;i+;i+;其时间复杂度为O(n).将字符串倒序的函数(voidHuffmanTree:Reverse(char*pch)算法伪代码：1得

14、到字符串的长度初始化两个记录下标的变量，一个为字符串开头字符所在的下标i,另个为字符串结尾字符所在的下标j将下标为i和j的字符交换i+,j-源代码：voidReverse(chara)charb100;inti=0,j=0;while(ai!=0)bi=ai;i+;bi=0;i-;while(i=0)aj=bi;i-;j+;aj=0;其时间复杂度为O(n).编码函数(voidHuffman:Encode(a)算法伪代码：从开头的字符开始，逐一对a中的字符进行编码在编码表中查找与当前字符对应的字符3如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。重复以上步骤，直到所有待编码

15、串中的字符都编码完毕输出编码后的字符串voidHuffman:Encode()编译输入内容为代码内容用0和1表示coutvv编码结果为：;intk=0;for(inti=0;letteri!=0;i+)intj=0;while(HCodeTablej.data!=letteri)/编码表的字符等于输入内容的字符时进行下一个while循环j+;intm=0;while(HCodeTablej.codem!=0)/输出该字符的编码bk=HCodeTablej.codem;佣数组b记录所有的编码数据，以备后续解码使用k+;m+;bk=0;coutb;coutendl;其时间复杂度为：O(n).解码函

16、数(voidHuffman:Decode()算法伪代码：1.得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针2.逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1，则指向当前结点的右孩子指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点的指针的孩子结点为空如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的字符如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应的字符追加到解码串中。6.输出解码串源代码：voidHuffman:Decode()coutvv解码结果为：”；inti=0,j=0;whi

17、le(bi!=0)intchild=2*n-l-l;找到保存根节点的数组数据while(HTreechild.lchild!=-1)/若是这个节点父节点的孩子存在则继续向下寻找if(bi=0)child=HTreechild.lchild;是0则找左孩子elsechild=HTreechild.rchild;是1则找右孩子i+;cj=HCodeTablechild.data;/若不存在孩子节点，则令数组的元素为该节点的字符变量coutcj;j+;逐个输出字符内容时间复杂度：O(n)3.程序运行结果1.主函数流程图开始程序*J等待用户输入字符串4利用用户输入的字符串创建哈夫曼树和编码表*直观打E

18、哈夫曼树的编码表+J对输我的字符串编码*对编码审解玛亠运行结果：门stiiy：11100编码结果为,國！C:v.rindowssystem32cmd.exe请输入需要编译压缩的内容:IlouedataStructure,IloueComputer.Iwillt/ymybesttosttidydata.Sti*uctui*e廊个字符的編码为二1100110101110011110000000011011001111110001011101101001111100011010010010010101101101000100國！C:v.rindowssystem32cmd.exe0011010010010010101101101000100