北邮数据结构实验—Huffman编码解码器

1、数 据 结 构实验报告实验名称：_Huffman编码/解码器_学生姓名：_班 级：_班内序号：_学 号：_日 期：_1实验要求利用二叉树结构实现哈夫曼编/解码器。基本要求：1.初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立哈夫曼树2.建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每 个字符的编码输出。3.编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。4.译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译 码，并输出译码结果。5.计算输入的字符串编码前和编码后的长度，

2、并进行分析，讨论赫夫曼 编码的压缩效果。2. 程序分析 2.1 存储结构 静态三叉链表Weight Lchild Rchild parent 2.2 程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)2.2.1.流程图 开始 输入进行编码的字符串统计各个字符的频度，并对各叶子节点的权重赋值初始化各节点的Lchild，Rchild和parent进行哈弗曼编码是否是否最后一个字符该节点是否为根节点判断双亲节点否是输出各字符编码若为右孩子编码前插入1若为左孩子编码前插入0对字符串进行编码找到当前字符编码，复制到总编码中否是否最后一个字符是输出各字符串编码对哈弗曼码进行译码输出译

3、码结果计算分析内存占用情况输出占用情况 结束 2.2.1.伪代码 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)/构造哈夫曼

5、树 s1=select(i-1);/函数在ht1到hti-1中选择parent为0且weight最小的结点， 并将结点序号返s，并将hts1.parent设为-1 s2=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.in

6、sert(0,0,0,1); /在字符串stri的第0位置插入字符 “0” else stri.insert(0,1,0,1); /在字符串stri的第0位置插入字符“1” 分析：这段语句实现的功能是根据统计出来的各字符的频度，建立哈弗曼。建立哈弗曼树的过程如程序所展示，每次选取权重最小且无双亲节点的节点组合，并将其权重之和赋给其双亲节点，加入到总结中进行下次判断。哈弗曼树建立完全以后，开始对各字符进行编码，从下往上，以叶子节点为起始点，若它是双亲节点的左孩子，其编码前插入0，若是右孩子则插入1。再判断双亲节点使其双亲节点的左孩子还是右孩子，以此类推直到根节点。依次对每个字符进行上述过程编码。

7、算法复杂度：最好情况为只有根结点和叶子节点：O（n）最坏情况为满二叉树情况：O（n*logn/2）3.程序运行结果分析首先，要求用户输入进行编码的字符串，遍历字符串，并为叶子节点权重赋值。然后，依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入0，若是双亲节点右孩子则编码钱插入1。屏幕上显示各字符的哈弗曼编码。接下来对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。对字符串的哈弗曼码进行译码。自上往下，若是0，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。最后分析内存占用情况。若用ASCII编码

8、，每个字符占1个字节，即8bit，该情况下占用内存就是（字符长度）*8。若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。3. 总结4.1实验的难点和关键点 本实验的难点和关键点是进行哈弗曼的编码与译码。编码之前先要遍历字符串，并统计各字符出现的频度。这里就要区分目前的字符是否出现过，若出现过则字符权重加一，若没有出现则在结构体数组的当前末尾添加该元素。统计完频度以后开始编码。根据哈弗曼树的特点，每次选取结点里权重最小，且双亲不为0的节点结合，依次添加直至根节点。编码过程是从下往上。对于某字符所在叶子节点，若是双亲节点左孩子则编码前插入0，若是双亲节点右孩子则编码钱插入1。直

9、到双亲节点移动到根节点，所得到的编码即为该字符的编码。译码过程是编码的逆过程。依次读取哈弗曼码，自上往下，若是0，则递归到左孩子，若是1，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。4.2心得体会 通过哈弗曼树的程序编写，更加深入了解了树这种数据结构的特点，并且熟悉了这种数据结构的应用。同时，也对哈弗曼编码的优越性能有了根本的解释。附：程序代码#include#includeusing namespace std;#define max 1000/哈夫曼数存储的最大叶子节点数int judge;/初始化过程中用于判断字符是否出现过struct HTNode char c;

10、 int weight; int lchild,rchild,parent; class CHTree public: CHTree()ht=NULL; ; void Init(); void huffmancode(); int select(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;/存储对字符串的编码 st

11、ring strmax;/存储叶子结点的哈夫曼编码 ; void CHTree:Init() int i=1;/用于记录叶子节点个数 int j=0; int x=0,ru; cout请输入进行编码的字符串：a; int l=a.length(); ht=(HTNode*)malloc(max)*sizeof(HTNode);/分配MAXSIZE个叶子结点的存储空间 while(xl) /统计字符出现的次数 judge=1; for(j=0;ji;j+) if(htj.c=ax)/如果字符ax已经出现过，则记录，权值加1 htj.weight+; judge=0; break; if(judg

12、e)/若字符没有出现过，字符入列，且权值设为1 n=i;/记录叶子节点数 hti.weight=1; hti.c=ax; i+; x+; int CHTree:select(int i)/函数在ht1到hti中选择parent为0且weight最小的结点，并将结点序号返回 int j=1;int k=1;int s; while(htj.parent!=0) j+;s=j; k=j+1; while(ki)return s; if(htj.weighthtk.weight) htj.parent=0;/如果第二次和第二次以后循环中发现有比htj权值还小的，将htj.parent重新设为0 j=

13、k;/始终令“htj”为二者中权值小的那一个 s=j; htj.parent=-1;/如果htj是权值较小的，将htj的parent记为-1， else s=j; htj.parent=-1; k+; return s; 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;

14、hti.rchild=0; for(i=n+1;i=m;+i)/构造哈夫曼树 s1=select(i-1);/函数在ht1到hti-1中选择parent为0且weight最小的结点， 并将结点序号返s，并将hts1.parent设为-1 s2=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)/

15、逆向求叶子结点的哈夫曼编码 if(htf.lchild=c)stri.insert(0,0,0,1); /在字符串stri的第0位置插入字符 “0” else stri.insert(0,1,0,1); /在字符串stri的第0位置插入字符“1” void CHTree:Display() couthuffman编码如下：n;cout字符t权值t哈夫曼编码endl; for(int i=1;i=n;i+) couthti.cthti.weighttstriendl; void CHTree:canculate()int m=0;for(int i=1;i=n;i+)m+=(hti.weight

16、)*(stri.length();/该字符所占位数为频度和每个字符huffman码长度乘积coutnn内存分析：n原始编码所占内存数为8*sizeof(char)*(a.length()bitendl;couthuffman编码所占内存数为mbitendl;void CHTree:encoding()for(int i=0;ia.length();i+)/循环变量i用于遍历输入字符串的字符for(int j=1;j=n;j+)/循环变量j用于寻找huffman编码中与该字符的相匹配的字符编码if(ai=htj.c)code+=strj;coutnn字符编码为codeendl;void CHTree:decoding()int i=0;int m=code.length();coutnn对编码译码后所得字符：;while(im)int parent=2*n-1;/根结点在HTree中的下表 while(htparent.rchild!=0|htparent.lchild!=0)/自根结点向叶子节点匹配编码，叶子节点左右孩子均为0，此时输出字符if(codei=0)parent=htpa