下载文档原格式
数据结构实验报告实验名称：____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（）函数的循环调用。
