《北邮数据结构实验—Huffman编码解码器》由会员分享，可在线阅读，更多相关《北邮数据结构实验—Huffman编码解码器（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称： Huffman 编码 / 解码器 学生： 班 级：班序号：学 号：日 期：1.实验要求利用二叉树构造实现哈夫曼编 /解码器。根本要求：1 .初始化（Init）：能够对输入的任意长度的字符串s进展统计，统计每个 字符的频度，并建立哈夫曼树2 .建立编码表（CreateTable）：利用已经建好的哈夫曼树进展编码，并将每 个字符的编码输出。字符串输出。码，并输出译码结果。编码的压缩效果。3 .编码（Encoding）:根据编码表对输入的字符串进展编码，并将编码后的4 .译码（Decoding）:利用已经建好的哈夫曼树对编码后的字符串进展译5 .计算输入的字符串编码前和编
2、码后的长度，并进展分析，讨论赫夫曼2.程序分析2.1 存储构造静态三叉链表Weight Lchild Rchild parent2.2程序流程（或程序构造、或类关系图等说明程序构成的容，一般为流程图2.2.1 流程图开场输入进展编码的字符串该节点是否为根节点是否最后一个字符是否最后一个字符.word.zl.初始化各节点的Lchild , Rchild和parent进展哈弗曼编码找到当前字符编码，复制到总编码中输出各字符串编码假设为右孩子编码前插子编码前插输出各字符编码对字符串进展编码假设为左孩统计各个字符的频度，并对各叶子节点 的权重赋值判断 双亲 节点对哈弗曼码进展译码输出译码结果计算分析内
3、存占用情况输出占用情况Y完毕2.2.1伪代码1 .输入进展编码的字符串2 .遍历字符串，并为叶子节点权重赋值3 .依次对各字符进展哈弗曼编码，自下往上，假设是双亲节点左孩子那么编码前插入0,假设是双亲节点右孩子那么编码钱插入1。4 .显示各字符的哈弗曼编码。5 .对字符串进展编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出 字符串的编码。6 .对字符串的哈弗曼码进展译码。自上往下，假设是0,那么递归到左孩子，假设是1,那么递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。7 .分析存占用情况。假设用 ASCII编码，每个字符占1个字节，即8bit,该情况下占用存 就
4、是字符长度*8。假设用哈弗曼编码，占用存是各字符频度 *每个字符占用位数 之和。8 .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(0,0,0,1); 在字符串
6、 stri的第 0 位置插入字符“0elsestri.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 的节点结合， 依次添加直至根节点。编码过程是从下往上。对于某字符所在叶子节点，假设是双亲节点左孩子那么编码前插入0 ，假
9、设是双亲节点右孩子那么编码钱插入 1。直到双亲节点移动到根节点，所得到的编码即为该字符的编码。译码过程是编码的逆过程。依次读取哈弗曼码，自上往下，假设是 0 ，那么递归到左孩子，假设是 1 ，那么递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。4.2 心得体会通过哈弗曼树的程序编写， 更加深入了解了树这种数据构造的特点， 并且熟悉了这种数据构造的应用。同时，也对哈弗曼编码的优越性能有了根本的解释。附：程序代码#include#include using 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();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 cod
11、e;/ 存储对字符串的编码string 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(htU.c=ax) 如果字符ax已经出现过，那么记录，权值加 1 htj.weight+;judge=0;bre
12、ak;if(judge)/ 假设字符没有出现过，字符入列，且权值设为 1n=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 重新设为 0j
13、=k;/ 始终令“ htj 为二者中权值小的那一个 s=j;htj.parent=-1; 如果 htj是权值较小的，将 htj的 parent 记为-1,elses=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;hti.rchild=0;for(i=n+1;i=m;+i)/ 构造哈夫曼树s1=select(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) fo
