Huffman编解码问题——讲解.docx

2.5 Huffman编码问题 实验四——题目2: 利用二叉树结构实现哈夫曼编/解码器。 基本要求： 1、 初始化(lnit):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度， 并建立哈夫曼树 2、 建立编码表(CreateTable)：利用己经建好的哈夫曼树进行编码，并将每个字符的 编码输出。 3、 编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的字符串输 出。 4、 译码(Decoding):利用己经建好的哈夫曼树对编码后的字符串进行译码，并输出 译码结果。 5、 打印(Print):以直观的方式打印哈夫曼树（选作） 6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压 缩效果。 7、 可采用二进制编码方式（选作） 实验讲解： Huffman编解码的实验按照模块化分，可以划分成如下部分： 统计输入的字符串中字符频率 创建Huffman树 打印Huffman树 创建Huffman编码表 对输入的字符串进行编码并输出编码结果 对编码结果进行解码，并输出解码后的字符串 最后编写测试函数，测试上述步骤的正确性。 根据模块化分，设计Huffman的存储结构如下： 1) Huffman树的结点结构 struct HNode { int weight; //结点权值 int parent; //双亲指针 int LChild; //左孩子指针 int RChild ; //右孩子指针 }； 20 datacode0Z1001C1012B113A0 5 2)编码表结点结构（如右图2-6所示） 11 struct HCode { char data; char code[100]; }; 图2-6 Huffman树编码结构 3) Huffman类结构class Huffman private: HNode* HTree; HCode* HCodeTable; char str[1024]; char leaf[256]; int a[256]; public: //Huffman 树 //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个：一是输入的字符串中间有空格如何处理？二是如何使统 计效率更高？ 例如： char str[1024]; cinstr; 上述代码运行后输入字符串，但cmstr遇到空格就停止本次读取，所以我们需要使用 其它的方法来进行输入，即需要使用cm.get()函数进行字符串读取。get()方法每调用一次， 读取一个字符，该字符的ASCII码作为返回值返回，换行回车等控制字符也当作普通字符 进行读取，因此需要指定结束读取的标志字符，才能停止get()函数的循环调用。 本实验中可以将字符读取和统计结合在一起进行。示例代码如下： //记录每一个字符出现的次数 //统计字符出现的次数 //记录原始字符串 //读取下一个字符 int nNum[256]= {0}; int ch = cin.get(); int i=0; while((ch!=V) (ch!=’\n’)) { nNum[ch]++; str[i++] = ch; ch = cin.get(); } str[i]=，\0’ 其中，整型数组变量nNum用来记录每一个字符出现的次数（若该字符未出现，则对应 的nNum[ch]的值为0)，可以把读取的字符ch的ASCII码当成，当ch出现时，nNum[ch]自 动加一。 当然，数组nNum中的等于零的字符会有很多，不方便后续hufman树的创建，因此可 以进行过滤，仅留下出现次数大于零的字符。因此，完整的初始化代码如下： void Huffman::init() { ①?⑧ n = 0; for ( i=0;i256;i++) { if (nNum[i]0) //若