哈夫曼树实验报告

1、数据结构实验报告实验名称：实验三哈夫曼树学生姓名：班级：班内序号：学号：日期：程序分析：存储结构：二叉树程序流程：template<classT>classBiTreepublic:ThOatdiTfaiec);arThlahCOde100Tnsigiilded$ntcomt(TVpadebOomsedree:InNOsiengexput)算法'伪代码：Lr1.初始化链表的头结点2. 获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3.从字符串第2个字符开始，逐个取出字符串中的字符将当前取出的字符与链表中已经存在的字符逐个比较，如果当前

2、取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n+=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)5. 创建哈夫曼树6. 销毁链表源代码：voidHuffmanTree:Init(stringInput)Node*front=newNode;建哈夫曼树(voidHuffmanTree:CreateCodeTable(Node*p)算法伪代码：1. 创建一个长度为2*tSize-1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点的data域，并将对应

3、结点的孩子域和双亲域赋为空3. 从三叉链表的第tSize个结点开始，i=tSize3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 根据哈夫曼树创建编码表源代码：voidHuffmanTree:CreateHTree(Node*p,intn)root=newBiNode<int>2*n-1;ata=front->count;rooti

4、.lchild=-1;rooti.rchild=-1;rooti.parent=-1;front=front->next;front=p;intNew1,New2;for(i=n;i<2*n-1;i+)SelectMin(New1,New2,0,i);arent=rootNew2.parent=i;ata=rootNew1.data+rootNew2.data;child=New1;rooti.rchild=New2;rooti.parent=-1;CreateCodeTable(p);始化编码表2 .初始化一个指针，从链表的头结点开始，遍历整个链表将链表中指针当前所指的结点包含的

5、字符写入编码表中得到该结点对应的哈夫曼树的叶子结点及其双亲如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0如果不止一个叶子结点，从当前叶子结点开始判断如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为1child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复的操作将已完成的编码倒序取得链表中的下一个字符3 输出编码表源代码：voidHuffmanTree:CreateCodeTable(Node*p)HCodeTable=newHCodetSize;ata=front->character;arent;odek='0'k+;whil

6、e(parent!=-1)child)odek='0'elseHCodeTablei.codek='1'k+;child=parent;parent=rootchild.parent;HCodeTablei.codek='0'Reverse(HCodeTablei.code);ata<<''<<HCodeTablei.code<<endl;时间复杂度：需要遍历哈夫曼树获取编码，时间复杂度为O(n2)4选择两个最小权值的函数算法伪代码：1. 从下标为begin的结点开始，寻找第一个没用过的结点2.

7、 遍历哈夫曼树中从下标为begin到下标为end的结点序列，寻找没用过的同时权值又是最小的结点。3. 暂时改变找到的权值最小结点的双亲域，防止第2次找到相同的结点。4. 将权值最小结点的下标记录下来。5. 重复步骤14，找到第2个权值最小的结点源代码：voidHuffmanTree:SelectMin(int&New1,int&New2,intbegin,intend)intmin;for(intj=0;j<2;j+)arent=-1)ata;sign=i;break;for(i=begin;i<end;i+)arent=-1)if(min>rooti.dat

8、a)min=rooti.data;sign=i;rootsign.parent=0;将字符串倒序的函数(voidHuffmanTree:Reverse(char*pch)算法伪代码：1 得到字符串的长度2 初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另一个为字符串结尾字符所在的下标j3 将下标为i和j的字符交换4 i+,j-时间复杂度：时间复杂度为O(n)6. 编码函数(voidHuffmanTree:Encode(string&s,string&d)算法伪代码：1. 从s开头的字符开始，逐一对s中的字符进行编码2. 在编码表中查找与当前字符对应的字符3. 如果

9、找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。4. 重复以上步骤，直到所有待编码串中的字符都编码完毕5. 输出编码后的字符串源代码：voidHuffmanTree:Encode(string&s,string&d)for(intj=0;j<();j+)ata)(HCodeTablei.code);码函数算法伪代码：1. 得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针2. 逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1，则指向当前结点的右孩子3. 指向待解码串的指针指向解码串中的下一个字符，直

10、到指向哈夫曼树结点的指针的孩子结点为空4. 如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的字符5. 如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应的字符追加到解码串中。6. 输出解码串源代码：voidHuffmanTree:Decode(string&s,string&d)for(inti=0;i<();)intparent=2*tSize-1-1;child!=-1)child;elsechild;i+;if(tSize=1)ata);计算哈夫曼编码的压缩比(voidHuffmanTree:Calculate(strings1,st

11、rings2)算法伪代码：1. 获得编码前字符串的长度，即其占用的字节数2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字节数3. 压缩比将两个相除源代码：voidHuffmanTree:Calculate(strings1,strings2)intcal1=();intcal2=();cal2=ceill(float)cal2/8);打印哈夫曼树(voidHuffmanTree:PrintTree(intTreeNode,intlayer)算法伪代码：1. 如果待打印结点为空，则返回2. 递归调用函数打印当前结点的右子树3. 根据当前结点所在的层次确定其前面要输出多少空格

12、，先输出空格，在打印当前结点的权值4. 递归调用函数打印当前结点的左子树源代码：voidHuffmanTree:PrintTree(intTreeNode,intlayer)if(TreeNode=-1)child,layer+1);ata<<endl;child,layer+1);菜单函数(voidHuffmanTree:Menu()算法伪代码：1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的string变量中，直到读到回车输入符为止2. 删除string变量末尾的回车输入符3. 利用string变量创建哈夫曼树，初始化编码表。4. 直观打印哈夫曼树5. 对输

13、入的字符串进行编码6. 对编码后的字符串进行解码7. 计算编码前后的压缩比并输出源代码：voidHuffmanTree:Menu()cout<<"请输入你要编码的文本,按回车键确定输入"<<endl;stringInput;charletter;do于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入的字符串，并采用string类的类成员函数来完成各项任务2. 打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。3. 为了输入空格，输入时采取逐个字符输入的方式三.程序运行结果分析：主函数流程图：运行结果请输入你要编码的文本.按回车键确定输入Ilouedatasti*uctLnreIlouecamputer.1willti*y|mybesttostmdi/dlatastrnictu；编祜表为；I11BR01111100Q1n0610uM0M01CBilld11MM1d0011C100S010甘r1H1MLleuL4-1018,01100Qm01QIQp011001；M1W11u011010imimiy11011L0Q0Q1010011101011解码后的字符串加willnty beet; to 仁七Ltdy da七a