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

北邮数据结构实验报告北京邮电大学信息与通信工程学院2009级数据结构实验报告实验名称：实验三哈夫曼编/解码器的实现学生姓名：陈聪捷日期：2010年11月28日1.实验要求一、实验目的：了解哈夫曼树的思想和相关概念;二、实验内容：利用二叉树结构实现哈夫曼编/解码器1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。

2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5.打印：以直观的方式打印哈夫曼树。

6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2.程序分析2.1存储结构二叉树templateclassBiTree{public:BiTree();//构造函数，其前序序列由键盘输入~BiTree(void);//析构函数BiNode*Getroot();//获得指向根结点的指针protected:BiNode*root;//指向根结点的头指针};//声明类BiTree及定义结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子树构成data:HCode*HCodeTable;//编码表inttSize;//编码表中的总字符数二叉树的节点结构templatestructBiNode//二叉树的结点结构{Tdata;//记录数据Tlchild;//左孩子Trchild;//右孩子Tparent;//双亲};编码表的节点结构structHCode{chardata;//编码表中的字符charcode[100];//该字符对应的编码};待编码字符串由键盘输入，输入时用链表存储，链表节点为structNode{charcharacter;//输入的字符unsignedintcount;//该字符的权值boolused;//建立树的时候该字符是否使用过Node*next;//保存下一个节点的地址};示意图：2.2关键算法分析1.初始化函数(voidHuffmanTree::Init(stringInput))算法伪代码：1.初始化链表的头结点2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n 记录的是链表中字符的个数)3.从字符串第2个字符开始，逐个取出字符串中的字符3.1将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

数据结构之阳早格格创做真验报告真验称呼：哈妇曼树教死姓名：袁普班级：2013211125班班内序号：14号教号：2013210681日期：2014年12月1.真验手段战真质利用二叉树结构真止哈妇曼编/解码器.基原央供：1、初初化(Init)：不妨对于输进的任性少度的字符串 s举止统计，统计每个字符的频度，并修坐哈妇曼树2、修坐编码表(CreateTable)：利用已经修佳的哈妇曼树举止编码，并将每个字符的编码输出.3、编码(Encoding)：根据编码表对于输进的字符串举止编码，并将编码后的字符串输出.4、译码(Decoding)：利用已经修佳的哈妇曼树对于编码后的字符串举止译码，并输出译码截止.5、挨印(Print)：以曲瞅的办法挨印哈妇曼树（选做）6、估计输进的字符串编码前战编码后的少度，并举止分解，计划赫妇曼编码的压缩效验.7、可采与二进造编码办法（选做）尝试数据：I love data Structure, I love Computer.I will try my best to study data Structure.提示：1、用户界里不妨安排为“菜单”办法：不妨举止接互.2、根据输进的字符串中每个字符出现的次数统计频度，对于不出现的字符一律不必编码2. 步调分解2.1 保存结构用struct结构典型去真止保存树的结面典型struct HNode{int weight; //权值int parent; //女节面int lchild; //左孩子int rchild; //左孩子};struct HCode //真止编码的结构典型{char data; //被编码的字符char code[100]; //字符对于应的哈妇曼编码};2.2 步调过程2.3算法1：void Huffman::Count()[1] 算法功能：对于出现字符的战出现字符的统计，构修权值结面，初初化编码表[2] 算法基原思维：对于输进字符一个一个的统计，并统计出现次数，构修权值数组，[3] 算法空间、时间搀纯度分解：空间搀纯度O（1），要遍历一遍字符串，时间搀纯度O（n）[4] 代码逻辑：leaf=0; //初初化叶子节面个数int i,j=0;int s[128]={0}; 用于保存出现的字符for(i=0;str[i]!='\0';i++) 遍历输进的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构修权值数组j++;}leaf=j; //叶子节面个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构修哈弗曼树[2] 算法基原思维：根据哈妇曼树构修央供，采用权值最小的二个结面分离，新结面加进数组，再继承采用最小的二个结面继承构修.[3] 算法空间、时间搀纯度分解：与决于叶子节面个数，时间搀纯度O（n），空间搀纯度O（1）[4] 代码逻辑HTree=new HNode[2*leaf-1]; n2=n0-1，一同需要2n-1个结面空间for(int i=0;i<leaf;i++){HTree[i].weight=weight[i]; 给每个结面附权值HTree[i].lchild=-1; 初初化安排孩子战女节面，皆为-1HTree[i].rchild=-1;HTree[i].parent=-1;}int x,y; //用于记录二个最小权值for(int i=leaf;i<2*leaf-1;i++){Selectmin(HTree,i,x,y); 选出二个最小权值的结面HTree[x].parent=i; 女节面树坐为新修坐的结面 HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight; 女节面权值为二个相加HTree[i].lchild=x; 使女节面指背那二个孩子结面HTree[i].rchild=y;HTree[i].parent=-1; 女节面的女节面设为-1 }算法3：void Selectmin(HNode*hTree,int n,int&i1,int &i2);[1] 算法功能：从现有的结面中采用出二个最小的结面，返回其位子[2] 算法基原思维：先选出二个不构修的结面，而后背后依次比较，筛选出最小的二个结面[3] 算法空间、时间搀纯度分解：空间搀纯度O(1)，要遍历所有结面，时间复纯度O(N)[4] 代码逻辑int i;for(i=0;i<n;i++) //n为目前有的结面个数，是个变更值,会有相加后的新权值加进{if(hTree[i].parent==-1) //女节面不是-1表示着那个结面还不被采用过{i1=i; 记录结面位子break;}}i++; //真止一遍for循环便加1，意为下次查找从目前位子启初查找for(;i<n;i++){if(hTree[i].parent==-1){i2=i; 记录第二个出采用过的结面编号break;}}if(hTree[i1].weight>hTree[i2].weight) 举止比较，使I1为最小的，I2为第二小的{int j=0;j=i2;i2=i1;i1=j;}i++;for(;i<n;i++) 将I1 I2 与后里的结面举止比较{if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight) 如果结面小于I1{i2=i1; 使I2=I1 I1=新结面i1=i;}else if(hTree[i].parent==-1&&hTree[i].weight<hTree[i2].weight){ I1《新结面《I2，使I2为新节面i2=i;}}算法4：void CreateTable();[1] 算法功能：对于出现的字符举止编码[2] 算法基原思维：根据字符正在哈妇曼树中的位子，从下到上编码，是左孩子编0，左孩子编1[3] 算法空间、时间搀纯度分解：空间搀纯度O(1)，要遍历data数组，时间搀纯度0(N)[4] 代码逻辑HCodeTable=new HCode[leaf]; 新修编码结面，个数为叶子节面个数for(int i=0;i<leaf;i++){HCodeTable[i].data=data[i];int child=i; 初初化要编码的结面的位子int parent=HTree[i].parent; 初初化女结面int k=0; //统计编码个数while(parent!=-1){if(child==HTree[parent].lchild)HCodeTable[i].code[k]='0'; //左孩子标‘0’elseHCodeTable[i].code[k]='1'; //左孩子标‘1’k++;child=parent; 孩子结面上移parent=HTree[child].parent; 女节面也上移}HCodeTable[i].code[k]='\0'; //将编码反背char code[100];for(int u=0;u<k;u++)code[u]=HCodeTable[i].code[k-u-1];for(int u=0;u<k;u++)HCodeTable[i].code[u]=code[u];cout<<data[i]<<"的哈妇曼编码为：";cout<<HCodeTable[i].code<<endl;length3[i]=k; //每一个字符编码的少度，为供编码总少度干准备}算法5：void Encoding();[1] 算法功能：对于输进的字符串举止编码[2] 算法基原思维：找到每个字符对于应的编码，将编码按程序输出[3] 算法空间、时间搀纯度分解：空间搀纯度O(1),时间搀纯度0（n）[4] 代码逻辑cout<<endl<<"输进的字符串转移为哈妇曼编码为:"<<endl;for (int i=0;str[i]!='\0';i++) 遍历输进的每一个字符{for(int j=0;j<leaf;j++)if(str[i]==HCodeTable[j].data) 找到字符对于应的编码{ s1=s1+HCodeTable[j].code; 将所有编码按程序加起去cout<<HCodeTable[j].code; 输出编码 }}cout<<endl;算法6：void Decoding();[1] 算法功能：对于编码串举止解码[2] 算法基原思维：找到每段编码对于应的字符，输出字符[3] 算法空间、时间搀纯度分解：时间搀纯度0(N)，空间搀纯度0（1）[4] 代码逻辑（可用真代码形貌）cout<<"解码后的字符串为: "<<endl;char *s = const_cast<char*>(s1.c_str()); 将编码字符串转移为charwhile(*s!='\0'){int parent=2*leaf-2; 女节面为末尾一个节面while(HTree[parent].lchild!=-1) //另有左子树，不可能是叶子节面{if(*s=='0') 编码为0，为左孩子parent=HTree[parent].lchild;elseparent=HTree[parent].rchild; 编码为1，为左孩子s++;}cout<<HCodeTable[parent].data; 输出字符}cout<<endl;……注意分解步调的时间搀纯度、内存申请战释搁，以及算法思维的体现.2.4 其余正在此次考查中使用了类战STL中的string，使用string不妨便当的将单个字符的编码加起去成为总的编码后的数值，再利用STL中的转移函数不妨间接将string 转移为char，便当举止解码处事.总而止之，使用STL使得编码大大的简净了.3.步调运止截止分解调试历程中逢到的问题主假如真止时有内存过失，查看后创造是数组有越界局里，那指示尔正在编写时一定要小心，特地是正在for循环条件上一定要注意范畴归纳最先正在输进字符串时尔创造间接用cin无法输进空格，正在上钩查询后找到了getline函数办理了那个问题.而后另有便是怎么样保存编码后总的那个字符串，果为每一个字符编码的少度大概，无法用char数组去保存，于是用了string 的相加函数去将所有编码加起去.末尾由于正在解码时要用char数组，又上钩查询到了string转移成char的函数办理了那个问题，真验易面也正在于怎么样找到二个最小权值去构修哈妇曼树，觅找二个最小权值的思维主假如通过一个个的比较去找到最小值，而且注意形参要用引用.通过此次真验尔体验到了stl的劣良性.另有便是编码时要注意数组的大小.再者便是有问题时不妨试着去网上查询问案.。

实验报告1、实验目的：(1）理解哈夫曼树的含义和性质。

（2）掌握哈夫曼树的存储结构以及描述方法。

(3）掌握哈夫曼树的生成方法。

（4)掌握哈夫曼编码的一般方法,并理解其在数据通讯中的应用.2、实验内容：哈夫曼树与哈弗曼编码、译码a。

问题描述：哈夫曼问题的提出可以参考教材P。

145。

利用哈弗曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码.b。

算法提示：参见教材P.147—148算法6.12、6。

13的描述.3、实验要求：建立哈夫曼树，实现编码,译码。

错误!.初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

○2。

编码（Encoding）.利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读入），对文件ToBeTran 中的正文进行编码,然后将结果存入文件CodeFile中。

○3.译码（Decoding ).利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件T extFile 中。

错误!.输出代码文件(Print）.将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

错误!。

输出哈夫曼树（TreePrinting）.将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

测试数据：设权值c= （a，b, c, d , e, f，g，h)w=（5,29，7,8，14，23,3，11）,n=8。

按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：5:0001,29：11，7：1110，8：111114：110，23:01,3：0000，11：001。

赫夫曼树实验报告赫夫曼树实验报告引言：赫夫曼树是一种用于数据压缩的重要算法，它通过构建一棵二叉树来实现对数据的编码和解码。

本次实验旨在通过实际操作，深入了解赫夫曼树的原理和应用，并验证其在数据压缩中的有效性。

一、实验背景数据压缩在现代信息技术中起着至关重要的作用。

随着数据量的不断增加，如何有效地压缩数据成为了一个迫切的问题。

赫夫曼树作为一种经典的数据压缩算法，具有较高的压缩比和较快的解压速度，因此备受关注。

二、实验目的1. 了解赫夫曼树的原理和构建方法；2. 掌握赫夫曼编码的过程和步骤；3. 验证赫夫曼树在数据压缩中的有效性。

三、实验过程1. 构建赫夫曼树首先，我们需要统计待压缩数据中各个字符的出现频率。

然后，按照频率从小到大的顺序，将字符构建成一棵二叉树。

具体构建方法为：每次选取频率最低的两个字符，将它们作为左右子节点，生成一个新的节点，该节点的频率为左右子节点频率之和。

重复此过程，直到所有字符都被构建成树的节点。

2. 进行赫夫曼编码在赫夫曼树构建完成后，我们需要对每个字符进行编码。

编码的规则是：向左走为0，向右走为1。

从根节点开始，对每个字符进行路径搜索，直到找到对应的叶子节点，记录下路径上的0和1，即为该字符的编码。

3. 数据压缩与解压缩利用赫夫曼编码，我们可以对待压缩数据进行压缩。

将每个字符替换为对应的编码后，将所有编码拼接起来，即可得到压缩后的数据。

解压缩则是将编码根据赫夫曼树进行反向解码，得到原始数据。

四、实验结果通过实验，我们将不同类型的数据进行了压缩和解压缩，并与原始数据进行了对比。

结果表明，赫夫曼树在数据压缩中表现出色，能够显著减小数据的大小，同时保持数据的完整性。

五、实验总结赫夫曼树作为一种高效的数据压缩算法，具有广泛的应用前景。

通过本次实验，我们深入了解了赫夫曼树的原理和构建方法，并验证了其在数据压缩中的有效性。

赫夫曼树的应用不仅可以提高数据传输的效率，还可以节省存储空间，对于大数据时代的到来具有重要意义。

数据结构哈夫曼树实验报告一、实验内容本次实验的主要内容是哈夫曼树的创建和编码解码。

二、实验目的1. 理解并掌握哈夫曼树的创建过程；2. 理解并掌握哈夫曼编码的原理及其实现方法；3. 掌握哈夫曼树的基本操作，如求哈夫曼编码和哈夫曼解码等；4. 学习如何组织程序结构，运用C++语言实现哈夫曼编码和解码。

三、实验原理哈夫曼树的创建：哈夫曼树的创建过程就是一个不断合并权值最小的两个叶节点的过程。

具体步骤如下：1. 将所有节点加入一个无序的优先队列里；2. 不断地选出两个权值最小的节点，并将它们合并成为一个节点，其权值为这两个节点的权值之和；3. 将新的节点插入到队列中，并继续执行步骤2，直到队列中只剩下一棵树，这就是哈夫曼树。

哈夫曼编码：哈夫曼编码是一种无损压缩编码方式，它根据字符出现的频率来构建编码表，并通过编码表将字符转换成二进制位的字符串。

具体实现方法如下：1. 统计每个字符在文本中出现的频率，用一个数组记录下来；2. 根据字符出现的频率创建哈夫曼树；3. 从根节点开始遍历哈夫曼树，给左分支打上0的标记，给右分支打上1的标记。

遍历每个叶节点，将对应的字符及其对应的编码存储在一个映射表中；4. 遍历文本中的每个字符，查找其对应的编码表，并将编码字符串拼接起来，形成一个完整的编码字符串。

哈夫曼解码就是将编码字符串还原为原始文本的过程。

具体实现方法如下：1. 从根节点开始遍历哈夫曼树，按照编码字符串的位数依次访问左右分支。

如果遇到叶节点，就将对应的字符记录下来，并重新回到根节点继续遍历；2. 重复步骤1，直到编码字符串中的所有位数都被遍历完毕。

四、实验步骤1. 定义编码和解码的结构体以及相关变量；3. 遍历哈夫曼树，得到每个字符的哈夫曼编码，并将编码保存到映射表中；4. 将文本中的每个字符用其对应的哈夫曼编码替换掉，并将编码字符串写入到文件中；5. 使用哈夫曼编码重新构造文本，并将结果输出到文件中。

五、实验总结通过本次实验，我掌握了哈夫曼树的创建和哈夫曼编码的实现方法，也学会了如何用C++语言来组织程序结构，实现哈夫曼编码和解码。

数据结构实验报告实验名称:实验三树——哈夫曼编／解码器学生姓名:班级:班内序号：学号:日期:２014年12月11日1.实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Iｎiｔ):能够对输入得任意长度得字符串s进行统计,统计每个字符得频度,并建立赫夫曼树2、建立编码表(CreaｔeTabｌｅ)：利用已经建好得赫夫曼树进行编码,并将每个字符得编码输出。

3、编码(Encｏｄing）:根据编码表对输入得字符串进行编码,并将编码后得字符串输出。

4、译码(Ｄecｏding）：利用已经建好得赫夫曼树对编码后得字符串进行译码，并输出译码结果。

5、打印(Ｐrint)：以直观得方式打印赫夫曼树(选作）6、计算输入得字符串编码前与编码后得长度,并进行分析,讨论赫夫曼编码得压缩效果。

测试数据:I lｏvｅdata Sｔｒｕcture, I lovｅputｅr。

I wiｌｌtrｙmy best ｔｏsｔudy ｄata Structure、提示：１、用户界面可以设计为“菜单”方式:能够进行交互。

2、根据输入得字符串中每个字符出现得次数统计频度,对没有出现得ﻩ字符一律不用编码。

2、程序分析2、1存储结构Ｈuffmａn树给定一组具有确定权值得叶子结点,可以构造出不同得二叉树,其中带权路径长度最小得二叉树称为Hｕffｍan树,也叫做最优二叉树。

wｅighｔlchilｄｒcｈｉld paｒｅnt２－1－1-15－1-1-16-1－1-17-１－1-1９-１-1-1wｅigｈt lchild rchilｄparent 2-1-155-1－156-１－167-１－１69-１-177017１3２38165482967-12、2 关键算法分析(1)计算出现字符得权值利用AＳCII码统计出现字符得次数,再将未出现得字符进行筛选,将出现得字符及頻数存储在数组ａ[]中。

void Huffmａn::Iｎｉt(){ﻩｉｎｔｎNｕm［256]＝ {0}；／/记录每一个字符出现得次数ｉnｔ ch = cin、get();ｉnt i=0;ﻩwｈｉle(（ｃｈ!='\r') ＆& （ch!='\n'）)ﻩ｛ﻩﻩｎＮｕm[cｈ]＋＋; ／/统计字符出现得次数ﻩstr[i＋+] ＝ cｈ; //记录原始字符串ﻩcｈ = cin、geｔ（）; //读取下一个字符ﻩ}str[ｉ]='\0';n = 0;for ( ｉ=０;ｉ＜256;i＋+)ﻩ｛ﻩﻩｉｆ(nNｕm[i]>０) /／若nＮum[i］==0,字符未出现ﻩ{l[ｎ] = (cｈａｒ)i;ﻩa［ｎ] = nNum[ｉ]；n++;ﻩ}}}时间复杂度为O(１);（2）创建哈夫曼树:算法过程:Huffman树采用顺序存储---数组;数组得前ｎ个结点存储叶子结点,然后就是分支结点,最后就是根结点；首先初始化叶子结点元素—循环实现；以循环结构，实现分支结点得合成，合成规则按照hｕfｆmaｎ树构成规则进行。

哈夫曼树实验报告哈夫曼树实验报告引言：哈夫曼树是一种经典的数据结构，广泛应用于数据压缩、编码和解码等领域。

本次实验旨在通过构建哈夫曼树，探索其原理和应用。

一、哈夫曼树的定义和构建方法哈夫曼树是一种特殊的二叉树，其叶子节点对应于待编码的字符，而非叶子节点则是字符的编码。

构建哈夫曼树的方法是通过贪心算法，即每次选择权值最小的两个节点合并，直到构建出完整的哈夫曼树。

二、哈夫曼编码的原理和实现哈夫曼编码是一种可变长度编码，即不同字符的编码长度不同。

其原理是通过构建哈夫曼树来确定字符的编码，使得频率较高的字符编码较短，频率较低的字符编码较长。

这样可以有效地减少编码的长度，从而实现数据的压缩。

三、实验过程和结果在本次实验中，我们选择了一段文本作为输入数据，通过统计每个字符的频率，构建了对应的哈夫曼树。

然后，根据哈夫曼树生成了字符的编码表，并将原始数据进行了编码。

最后，我们通过对编码后的数据进行解码，验证了哈夫曼编码的正确性。

实验结果显示，通过哈夫曼编码后，原始数据的长度明显减少，达到了较好的压缩效果。

同时，解码后的数据与原始数据完全一致，证明了哈夫曼编码的可靠性和正确性。

四、哈夫曼树的应用哈夫曼树在实际应用中有着广泛的用途。

其中，最典型的应用之一是数据压缩。

通过使用哈夫曼编码，可以将大量的数据压缩为较小的存储空间，从而节省了存储资源。

此外，哈夫曼树还被广泛应用于网络传输、图像处理等领域，提高了数据传输的效率和图像的质量。

五、对哈夫曼树的思考哈夫曼树作为一种经典的数据结构，其优势在于有效地减少了数据的冗余和存储空间的占用。

然而，随着技术的不断发展，现代的数据压缩算法已经不再局限于哈夫曼编码，而是采用了更为复杂和高效的算法。

因此，我们需要在实际应用中综合考虑各种因素，选择合适的压缩算法。

六、总结通过本次实验，我们深入了解了哈夫曼树的原理和应用。

哈夫曼编码作为一种重要的数据压缩算法，具有广泛的应用前景。

在实际应用中，我们需要根据具体情况选择合适的压缩算法，以达到最佳的压缩效果和性能。

11．实验要求利用二叉树结构实现哈夫曼编/ 解码器(1). 初始化：能够对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立哈夫曼树。

(2). 建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

(3). 编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

(4). 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

(5). 打印：以直观的方式打印哈夫曼树。

(6). 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

(7). 用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2.程序分析2.1存储结构二叉树：示意图：root2.21{2.3 关键算法分析1. 定义哈夫曼树的模板类#include <iostream>#include <string.h> using namespace std; structLNode {char ch;int weight;char code[20];LNode* next; };struct TNode{int weight; //int Lchild; //int Rchild; //int Parent; // };class Huffman 结点权值左孩子指针右孩子指针双亲指针// 链表的节点, 用来统计字符频率，并编码// 字符// 权值// 字符编码// 指向下一个节点// 哈弗曼树结点的结构体1 public:Huffman(); ~Huffman(); void CreateTable(); void PrintTable(); void Encoding(); void Decoding(); void Comrate();// 构造函数，输入、统计字符，创建哈弗曼树、码表// 释放链表空间、哈弗曼树的节点// 建立编码表，并将信息存入链表// 输出码表// 哈弗曼编码// 译码void SelectMin(int &x,int &y,int begin,int end);void reverse(char ch[]); voidcontrol();private: // 选取权值最小的两个数，创建哈弗曼树// 将码值倒置，用来编码// 对菜单交互等提示操作TNode* troot;LNode* lroot; void List(char a[]); void HTree(); int Letter; char astr[1000]; char bstr[1000]; // 在统计字符频率是构建链表的根节点// 统计字符的权值建立的单链表// 哈弗曼树建立// 共有不同字符总数// 用户输入的一串字符// 将字符串的码值保存Huffman::Huffman(){lroot=new LNode;bstr[0]='\0';lroot->next=NULL;Letter=0; // 初始化字符总数为1 cout<<" 请输入一串字符，以回车键结束"<<endl;cin.getline(astr,1000,'\n');if(strlen(astr)==0) throw 1;else{List(astr); // 用链表存储每个字符HTree();CreateTable();Encoding();}};Huffman::~Huffman(){delete troot;LNode* p=lroot;while(p=lroot->next)1{{ lroot=p->next; delete p; p=lroot;}delete p; };2. 建立哈夫曼树void Huffman::HTree(){LNode* p=lroot; int a=0;troot=new TNode[2*Letter-1]; //2n-1 while (p=p->next){troot[a].weight=p->weight; troot[a].Parent=-1; troot[a].Lchild=-1; troot[a].Rchild=-1; a++;};for (int i=Letter;i<2*Letter-1;i++)troot[i].Parent=-1; int x,y,begin=0;for (int j=Letter;j<2*Letter-1;j++) while (troot[begin].Parent!=-1)begin++;个结点// 建立叶子节点// 是两个最小值的角标SelectMin(x,y,begin,j);troot[j].weight=troot[x].weight+troot[y].weight;troot[j].Lchild=x;troot[j].Rchild=y;troot[j].Parent=-1;troot[x].Parent=j;troot[y].Parent=j;}};3.统计字符的频率void Huffman::List(char a[]){LNode *p=lroot;int i=0;while(a[i]!='\0'){{while (p&&p->ch!=a[i]) // 查找链表中没有该字符或者找到该字符p=p->next;if (!p) // 如果没有该字符，创建节点。