数据结构huffman解码与编码ppt

数据结构实验报告实验名称：____Huffman编码/解码器_____学生姓名：__________________班级：__________________班内序号：__________________学号：__________________日期：___________________1．实验要求利用二叉树结构实现哈夫曼编/解码器。

基本要求：1.初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2.建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

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

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

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

2. 程序分析存储结构静态三叉链表程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)流程图伪代码1.输入进行编码的字符串2.遍历字符串，并为叶子节点权重赋值3.依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入‘0’，若是双亲节点右孩子则编码钱插入‘1’。

4.显示各字符的哈弗曼编码。

5.对字符串进行编码，挨个遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。

6.对字符串的哈弗曼码进行译码。

自上往下，若是‘0’，则递归到左孩子，若是‘1’，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。

7.分析内存占用情况。

若用ASCII编码，每个字符占1个字节，即8bit，该情况下占用内存就是（字符长度）*8。

若用哈弗曼编码，占用内存是各（字符频度）*（每个字符占用位数）之和。

关键算法分析该程序关键算法即哈弗曼编码，语句如下：void CHTree::huffmancode(){int i;if(n<=1)return;m=2*n-1;for(i=1;i<=n;i++)arent=0;ht[i].lchild=0;ht[i].rchild=0;}for(;i<=m;i++) eight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}for(i=n+1;i<=m;++i)arent设为-1s2=select(i-1);ht[s1].parent=i;ht[s2].parent=i;ht[i].lchild=s1;ht[i].rchild=s2;ht[i].weight=ht[s1].weight+ht[s2].weight;}int c,f;for(i=1;i<=n;++i) {for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)child==c){str[i].insert(0,"0",0,1);} nsert(0,"1",0,1);} 序运行结果分析首先，要求用户输入进行编码的字符串，遍历字符串，并为叶子节点权重赋值。

Huffman树及其编解码Huffman树——编解码介绍： Huffman树可以根据输⼊的字符串中某个字符出现的次数来给某个字符设定⼀个权值，然后可以根据权值的⼤⼩给⼀个给定的字符串编码，或者对⼀串编码进⾏解码，可以⽤于数据压缩或者解压缩，和对字符的编解码。

可是Huffman树的优点在哪？ 1、就在于它对出现次数⼤的字符（即权值⼤的字符）的编码⽐出现少的字符编码短，也就是说出现次数越多，编码越短，保证了对数据的压缩。

2、保证编的码不会出现互相涵括，也就是不会出现⼆义性，⽐如a的编码是00100，b的编码是001，⽽c的编码是00，，这样的话，对于00100就可能是a，也可能是bc，⽽Huffman树编码⽅式不会出现这种问题。

如何实现 实现Huffman树的编解码需要三种数据类型，⼀个是优先级队列，⽤来保存树的结点，⼆是树，⽤来解码，三是表，⽤来当作码表编码。

下⾯我们先⼀⼀介绍⼀下三种数据结构：1、优先级队列 优先级队列⾥存放的是⼀个⼀个的树的结点，根据树结点中存放的字符的权值来确定其优先级，权重越⼩，优先级越⼩，放的位置越靠前。

也就是说第⼀个结点存放的优先级最⼩，权值最⼩。

数据类型//优先级队列,struct TNode表⽰树的结点，在后⾯介绍typedef struct QNode{struct TNode* val; //树的结点,其实也就是数据域int priority; //优先级struct QNode* next; //指针域}*Node;typedef struct Queue{int size; //队列⼤⼩struct QNode* front; //队列头指针}queue;2、树 树⾥⾯存放的是字符，以及指向⾃⼰的左右孩⼦结点的指针。

⽐如下图，虽然下图中看起来书中存放了该字符的优先级，但其实可以不加，感觉⽐较繁琐，所以我取了，但是为了理解⽅便起见，我在图上标注了出来。

数据类型//树typedef struct TNode{char data; //字符值struct TNode* left; //左孩⼦struct TNode* right; //右孩⼦}*Tree;3、表 这个表其实就是⼀张编码表，⾥⾯存放了字符和该字符的编码，⽤于编码的时候查看。

Huffman编解码问题 --------------- 讲解2.5 Huffman编码问题实验四一一题目2:利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(lnit):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable):利用己经建好的哈夫曼树进行编码，并将每个字符的编码输岀。

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

4、译码(Decoding):利用己经建好的哈夫曼树对编码后的字符串进行译码，并输岀译码结果。

5、打印(Print):以直观的方式打印哈夫曼树(选作)6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式(选作)实验讲解：Huffman编解码的实验按照模块化分，可以划分成如下部分：a)统计输入的字符串中字符频率b)创建Huffman树c)打印Huffman树d)创建Huffman编码表e)对输入的字符串进行编码并输岀编码结果f)对编码结果进行解码，并输岀解码后的字符串g)最后编写测试函数，测试上述步骤的正确性。

根据模块化分，设计Huffman的存储结构如下：1) Huffman树的结点结构struct HNode {int weight; 〃结点权值jnt pare nt; //双亲指针int LChild ; 〃左孩子指针int RChild ；//右孩子指针｝；2）编码表结点结构（如 右图2-6所 示）struct HCode ｛ char data ； char codeu oo 】；｝；图2-6 Huffman树编码结构3)Huffman 类结构 classHuffma nprivate :HNode * HTree ; //Huffman 树HCode * HCodeTable ; //Huffman 编码char str [1024]; char 表leaf [256]; int a [256]; //输入的原始字符串//叶子public :节点对应的字符 // 记录每个岀现字符的个数{int n ;//叶子节点数void init ();//初始化void CreateHTree (); 〃仓曜 huffman 树voidSelectMin(int &x , int &y , int s , int e void CreateCodeTableo ; 〃 创建编码表 void Encode(char *d ); 〃编码void Decode(char *s, char *d ); 〃解码void print(int i , int m ); 〃打印 Huffman 树 ? Huffman ();根据实验要求，分步骤实现如下： 步骤1 ：统计输入的字符串中字符频率Huffman 编码的第一步需要使用字符岀现的频率作为输入，本实验使用从键盘输入的方 进行，需要的解决得问题有 2个：一是输入的字符串中间有空格如何处理？二是如何使统 率更高？ 例如: str[1024];cin>>str;data code 0 Z 100 1 C 101 2 B 11 3A式 计效20进行读取，因此需要指定结束读取的标志字符，才能停止get（）函数的循环调用。

数据结构——哈夫曼（Huffman）树+哈夫曼编码前天acm实验课，⽼师教了⼏种排序，抓的⼀套题上有⼀个哈夫曼树的题，正好之前离散数学也讲过哈夫曼树，这⾥我就结合课本，整理⼀篇关于哈夫曼树的博客。

哈夫曼树的介绍Huffman Tree，中⽂名是哈夫曼树或霍夫曼树，它是最优⼆叉树。

定义：给定n个权值作为n个叶⼦结点，构造⼀棵⼆叉树，若树的带权路径长度达到最⼩，则这棵树被称为哈夫曼树。

这个定义⾥⾯涉及到了⼏个陌⽣的概念，下⾯就是⼀颗哈夫曼树，我们来看图解答。

(01) 路径和路径长度定义：在⼀棵树中，从⼀个结点往下可以达到的孩⼦或孙⼦结点之间的通路，称为路径。

通路中分⽀的数⽬称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

例⼦：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。

(02) 结点的权及带权路径长度定义：若将树中结点赋给⼀个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

例⼦：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。

(03) 树的带权路径长度定义：树的带权路径长度规定为所有叶⼦结点的带权路径长度之和，记为WPL。

例⼦：⽰例中，树的WPL= 1*100 + 2*50 +3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。

⽐较下⾯两棵树上⾯的两棵树都是以{10, 20, 50, 100}为叶⼦节点的树。

左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=350左边的树WPL > 右边的树的WPL。

你也可以计算除上⾯两种⽰例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树。

⾄此，应该堆哈夫曼树的概念有了⼀定的了解了，下⾯看看如何去构造⼀棵哈夫曼树。

Huffman编解码问题——讲解2.5 Huffman编码问题实验四——题目2:利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(lnit):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用己经建好的哈夫曼树进行编码，并将每个字符的编码输出。

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

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

5、打印(Print):以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）实验讲解：Huffman编解码的实验按照模块化分，可以划分成如下部分：a)统计输入的字符串中字符频率b)创建Huffman树c)打印Huffman树d)创建Huffman编码表e)对输入的字符串进行编码并输出编码结果f)对编码结果进行解码，并输出解码后的字符串g)最后编写测试函数，测试上述步骤的正确性。

根据模块化分，设计Huffman的存储结构如下：1) Huffman树的结点结构structHNode {int weight; //结点权值int parent; //双亲指针int LChild; //左孩子指针20data code 0Z 100 1 C 101 2 B 11 3A511private :HNode * HTree ; HCode * HCodeTable ; char str [1024]; char leaf [256]; int a [256]; public ://Huffman 树 //Huffman 编码表//输入的原始字符串 //叶子节点对应的字符 //记录每个出现字符的个数int RChild ; //右孩子指针}；2)编码表结点结构（如右图2-6所示）struct HCode { char data ; char code [100];};图2-6 Huffman 树编码结构3)Huffman 类结构 class Huffman{int n ; //叶子节点数 void init (); //初始化void CreateHTree (); //创建 huffman 树 voidSelectMin(int &x , int &y , int s , int e ); void CreateCodeTable (); //创建编码表 void Encode(char *d ); //编码void Decode(char *s , char *d ); //解码void print(int i , int m ); //打印 Huffman 树 〜Huffman ();}根据实验要求，分步骤实现如下： 步骤1：统计输入的字符串中字符频率Huffman 编码的第一步需要使用字符出现的频率作为输入，本实验使用从键盘输入的方 式进行，需要的解决得问题有2个：一是输入的字符串中间有空格如何处理？二是如何使统 计效率更高？ 例如：charstr[1024]; cin>>str;//记录每一个字符出现的次数//统计字符出现的次数 //记录原始字符串 //读取下一个字符上述代码运行后输入字符串，但cm >>str 遇到空格就停止本次读取，所以我们需要使用 其它的方法来进行输入，即需要使用cm .get ()函数进行字符串读取。

《数据结构的课程设计》报告题目：Huffman编码与解码班级：1612401学号：3姓名：张修鸣指导老师：孙涵完成日期：目录七．体验感悟需求分析对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。

程序主要功能（1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。

（2）在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符’0’和’1’表示。

（3）提供读编码文件生成原文件的功能。

程序运行平台该程序是用VC++制做的，使用Microsoft Visual C++ 运行该程序，具体操作是：打开Microsoft Visual C++ ，菜单栏里点文件→打开工作区→找到“图书管理系统.dsw”这个文件→打开，或者在资源管理器中双击该文件，此时，VC++会自动打开，并载入该系统相关资源，点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。

程序类说明二叉树类记录typedef struct{int weight,flag,parent;char c;int lchild,rchild;}hnodetype;赫夫曼类typedef struct{int Bit[3000];int Start;}hcodetype;函数分析：void create(int T[]) 创建二叉树void Visit(int i,int n) 显示元素的权值int IN(int i,int n) 中序遍历void htree() 赫夫曼解码模块分析我设计的系统，主要分为两大模块1编码模块2解码模块该系统主要完成以下功能：编码模块：1 从文章中读取信息2 构建赫夫曼树3 进行赫夫曼编码并保存在文件中解码模块：1 从文件中读取赫夫曼码2 进行解码3保存在文件中文章信息元素权值赫夫曼解码结果存在的不足与对策由于自身能力有限，所以没有起到真正的压缩文件的功能。

佛山科学技术学院实验报告课程名称数据结构实验项目用Huffman树进行编码与解码算法专业班级网络工程2 姓名陈浩明学号 2010394223指导教师成绩日期2011.11.13一、实验目的1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种算法2、熟悉用Huffman树进行电文的加密与解密算法二、实验内容1、Huffman树的存储方式2、加密与解密算法在电文编码中的应用三、实验原理给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。

哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。

n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

四、实验步骤1、统计电文中字符的出现频率。

2. 用统计频率建立Hffman树。

3．生成前缀码；4．建立huffman树的解码算法．5．用随机输入的电文完成编码与解码过程。

五、程序源代码及注释#include<iostream.h>#include<string.h>const int MAX=20;struct huffnode{int weight;int lchild,rchild,parent;};struct huffinit //输入的权值信息的结构{char data;int weight;};struct huffcode //哈夫曼树编码的结构{char data;char code[MAX+1];};class HuffTree //哈夫曼树类的声明{ public:HuffTree(huffinit w[],int n);~HuffTree() { }void Select(int &min1,int &min2,int m);void Output(); //输出哈夫曼树最终状态（tree数组）void Encode(); //编码void Decode(char code[]); //解码private:huffnode tree[2*MAX-1]; //存储哈夫曼树huffcode cd[MAX]; //存储各个哈夫曼编码int size; //哈夫曼树的叶子结点数};HuffTree::HuffTree(huffinit w[],int n){size=n;for(int i=0;i<2*n-1;i++){tree[i].parent=-1;tree[i].lchild=-1;tree[i].rchild=-1;}for(i=0;i<n;i++){tree[i].weight=w[i].weight;cd[i].data=w[i].data;}int min1=-1;int min2=-1;int m=size;for(int k=n;k<2*n-1;k++){Select(min1,min2, m);tree[min1].parent=k;tree[min2].parent=k;tree[k].weight=tree[min1].weight+tree[min2].weight;tree[k].lchild=min1;tree[k].rchild=min2;m++;}}void HuffTree::Select(int &min1,int &min2,int m)//选择两个权值最小的结点{int a=100;int b=100;for(int i=0;i<m;i++){if(tree[i].weight<a&&tree[i].parent==-1){a=tree[i].weight;min1=i;}}for(i=0;i<m;i++){if(tree[i].weight<b&&tree[i].parent==-1&&i!=min1){b=tree[i].weight;min2=i;}}}void HuffTree::Output(){for(int i=0;i<2*size-1;i++){cout<<tree[i].weight<<" "<<tree[i].parent<<" "<<tree[i].lchild<<" "<<tree[i].rchild<<endl;}}void HuffTree::Encode() //编码{int m;int a;int j; char b[100]; int k;for(int i=0;i<size;i++){m=i;j=0;while(tree[m].parent!=-1){a=m;m=tree[m].parent;if(tree[m].lchild==a)b[j++]='0';elseb[j++]='1';}for(k=0,j=j-1;j>=0;j--)cd[i].code[k++]=b[j];cd[i].code[k]='\0';cout<<cd[i].data<<"--->"<<cd[i].code<<endl;; }}void HuffTree::Decode(char code[]) //解码{int n=strlen(code);int a=2*size-2;//根节点的下标for(int i=0;i<n;i++){if(code[i]=='0'){a=tree[a].lchild;}if(code[i]=='1')a=tree[a].rchild;if(tree[a].lchild==-1&&tree[a].rchild==-1){cout<<cd[a].data;a=2*size-2;}elseif(code[i+1]=='\0')cout<<"error";}cout<<endl;}void main(){huffinit w[20];int n;char s[100];cout<<"请输入字符个数：";cin>>n;for(int i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个字符及权值：" ;cin>>w[i].data;cin>>w[i].weight;}HuffTree H(w,n);cout<<"已经建好的节点信息为"<<endl;H.Output();cout<<"已经建好的节点编码信息为"<<endl;H.Encode();char q;do{cout<<"请输入密码：";cin>>s;H.Decode(s);cout<<endl;cout<<"还要继续解码吗?(Y/N)";cin>>q;}while(q=='Y');}结果截图:六、实验结果分析及实验体会通过用Huffman树进行编码与解码算法的实验后，对于huffman树的理解和应用都有了进一步的了解，但对于快速构建huffman树还有些有欠纯熟，还要多加炼金，并且要对基础的二叉树等知识要多加练习。