《北邮数据结构实验—Huffman编码解码器》由会员分享，可在线阅读，更多相关《北邮数据结构实验—Huffman编码解码器（14页珍藏版）》请在金锄头文库上搜索。
1、.数据结构实验报告实验名称： _Huffman编码 / 解码器 _学生姓名： _班级： _班内序号： _学号： _.日期： _.1实验要求利用二叉树结构实现哈夫曼编/ 解码器。基本要求：1.初始化 (Init) ：能够对输入的任意长度的字符串s 进行统计， 统计每个字符的频度， 并建立哈夫曼树2.建立编码表 (CreateTable) ：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3.编码 (Encoding) ：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4.译码 (Decoding) ：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5.计算输入的
2、字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。2. 程序分析2.1 存储结构静态三叉链表WeightLchildRchildparent2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等 )流程图开始输入进行编码的字符串统计各个字符的频度，并对各叶子节点的权重赋值.初始化各节点的Lchild ， Rchild 和 parent进行哈弗曼编码是否是否最后一个字符该节点是否为根节点否是判断双亲输出各字符编码节点若为左孩子若为右孩子编码前插入 0编码前插入 1对字符串进行编码找到当前字符编码，复制到总编码中否是否最后一个字符是输出各字符串编码对哈弗曼码进
3、行译码输出译码结果.计算分析内存占用情况输出占用情况结束伪代码1.输入进行编码的字符串2.遍历字符串，并为叶子节点权重赋值3.依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入 0 ，若是双亲节点右孩子则编码钱插入 1。4.显示各字符的哈弗曼编码。5.对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。6.对字符串的哈弗曼码进行译码。自上往下，若是0，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。7.分析内存占用情况。若用ASCII 编码，每个字符占1 个字节，即8bit ，该情况下占用内存就是（
4、字符长度）*8 。若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。2.3 关键算法分析该程序关键算法即哈弗曼编码，语句如下：void CHTree:huffmancode()int i;if(n=1)return;m=2*n-1;for(i=1;i=n;i+)/叶子节点的初始化 hti.parent=0; hti.lchild=0; hti.rchild=0;for(;i=m;i+) /非叶子节点的初始化.hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i=m;+i)/构造哈夫曼树s1=select
5、(i-1);/ 函数在 ht1 到 hti-1 中选择 parent 为 0 且 weight 最小的结点， 并将结点序号返 s，并将 hts1.parent 设为 -1s2=select(i-1);hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;int c,f;for(i=1;i=n;+i) for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/逆向求叶子结点的哈夫曼编码if(htf.lchild=c)stri.insert(
6、0,0,0,1); /在字符串 stri 的第 0 位置插入字符“0”elsestri.insert(0,1,0,1); /在字符串 stri 的第 0 位置插入字符“ 1”分析：这段语句实现的功能是根据统计出来的各字符的频度，建立哈弗曼。 建立哈弗曼树的过程如程序所展示，每次选取权重最小且无双亲节点的节点组合，并将其权重之和赋给其双亲节点， 加入到总结中进行下次判断。哈弗曼树建立完全以后，开始对各字符进行编码，从下往上，以叶子节点为起始点，若它是双亲节点的左孩子，其编码前插入0 ，若是右孩子则插入1 。再判断双亲节点使其双亲节点的左孩子还是右孩子，以此类推直到根节点。依次对每个字符进行上述过
7、程编码。算法复杂度：最好情况为只有根结点和叶子节点：O（ n）最坏情况为满二叉树情况：O（ n*logn/2 ）.3.程序运行结果分析首先，要求用户输入进行编码的字符串，遍历字符串，并为叶子节点权重赋值。然后，依次对各字符进行哈弗曼编码， 自下往上， 若是双亲节点左孩子则编码前插入 0，若是双亲节点右孩子则编码钱插入 1。屏幕上显示各字符的哈弗曼编码。 接下来对字符串进行编码， 挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。对字符串的哈弗曼码进行译码。自上往下，若是0，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。最后分析内存
8、占用情况。若用ASCII 编码，每个字符占1 个字节，即8bit ，该情况下占用内存就是（字符长度）*8 。若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。3. 总结4.1 实验的难点和关键点本实验的难点和关键点是进行哈弗曼的编码与译码。编码之前先要遍历字符串，并统计各字符出现的频度。这里就要区分目前的字符是否出现过，若出现过则字符权重加一，若没.有出现则在结构体数组的当前末尾添加该元素。统计完频度以后开始编码。根据哈弗曼树的特点， 每次选取结点里权重最小，且双亲不为0 的节点结合， 依次添加直至根节点。编码过程是从下往上。 对于某字符所在叶子节点， 若是双亲节点左孩子则编
9、码前插入 0 ，若是双亲节点右孩子则编码钱插入 1直。到双亲节点移动到根节点， 所得到的编码即为该字符的编码。译码过程是编码的逆过程。依次读取哈弗曼码，自上往下，若是 0 ，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。4.2 心得体会通过哈弗曼树的程序编写， 更加深入了解了树这种数据结构的特点， 并且熟悉了这种数据结构的应用。同时，也对哈弗曼编码的优越性能有了根本的解释。附：程序代码#include#includeusing namespace std;#define max 1000/哈夫曼数存储的最大叶子节点数int judge;/初始化过程中
10、用于判断字符是否出现过struct HTNodechar c;int weight;int lchild,rchild,parent;class CHTreepublic:CHTree()ht=NULL; ;void Init();void huffmancode();intselect(int i);void Display();void canculate();void encoding();void decoding();private:HTNode* ht;int m;int n;/ 叶子结点数int s1;int s2;.string a;/ 存储输入的字符串string code;/存储对字符串的编码string strmax;/存储叶子结点的哈夫曼编码
