经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
Huffman树及其编解码
来源：cnblogs　　作者：头发是我最后的倔强　　时间：2019/10/8 9:09:59　　对本文有异议

Huffman树——编解码

介绍：

Huffman树可以根据输入的字符串中某个字符出现的次数来给某个字符设定一个权值，然后可以根据权值的大小给一个给定的字符串编码，或者对一串编码进行解码，可以用于数据压缩或者解压缩，和对字符的编解码。

可是Huffman树的优点在哪？

1、就在于它对出现次数大的字符（即权值大的字符）的编码比出现少的字符编码短，也就是说出现次数越多，编码越短，保证了对数据的压缩。
??2、保证编的码不会出现互相涵括，也就是不会出现二义性，比如a的编码是00100，b的编码是001，而c的编码是00，，这样的话，对于00100就可能是a，也可能是bc，而Huffman树编码方式不会出现这种问题。

如何实现

实现Huffman树的编解码需要三种数据类型，一个是优先级队列，用来保存树的结点，二是树，用来解码，三是表，用来当作码表编码。下面我们先一一介绍一下三种数据结构：

1、优先级队列

优先级队列里存放的是一个一个的树的结点，根据树结点中存放的字符的权值来确定其优先级，权重越小，优先级越小，放的位置越靠前。也就是说第一个结点存放的优先级最小，权值最小。
优先级队列

数据类型
  1. //优先级队列,struct TNode表示树的结点，在后面介绍
  2. typedef struct QNode
  3. {
  4.     struct TNode* val;          //树的结点,其实也就是数据域
  5.     int priority;               //优先级
  6.     struct QNode* next;         //指针域
  7. }*Node;
  9. typedef struct Queue
  10. {
  11.     int size;           //队列大小
  12.     struct QNode* front;        //队列头指针
  13. }queue;

2、树

树里面存放的是字符，以及指向自己的左右孩子结点的指针。比如下图，虽然下图中看起来书中存放了该字符的优先级，但其实可以不加，感觉比较繁琐，所以我取了，但是为了理解方便起见，我在图上标注了出来。
在这里插入图片描述

数据类型
  1. //树
  2. typedef struct TNode
  3. {
  4.     char data;              //字符值
  5.     struct TNode* left;         //左孩子
  6.     struct TNode* right;                //右孩子
  7. }*Tree;

3、表

这个表其实就是一张编码表，里面存放了字符和该字符的编码，用于编码的时候查看。
在这里插入图片描述

数据类型
  1. //表
  2. typedef struct BNode
  3. {
  4.     char code[256];             //编码
  5.     char symbol;                //字符
  6.     struct BNode* next;         //指向下一个
  7. }*bNode;
  9. typedef struct Table
  10. {
  11.     struct BNode* first;                //表头
  12.     struct BNode* last;             //表尾
  13. }*table;

思路

为了简单起见我们讲述的时候就先将权值设置为用户输入而不是根据出现频率统计，因为我们作业也刚好是用户输入，文章最后我会贴出根据出现频率统计的代码，有兴趣可以看看。因为用到了很多数据类型所以可能写到一半会觉得有点晕，所以我们开始之前先理一下思路：

先设定a，b，c三个数据，它们的权值分别为6，1，2

1、首先要根据用户输入的每个字符的权值，创建出一个一个的树结点，然后将其按照优先级的大小存入优先级队列中，按从小到大的顺序，具体实现我会在后面贴。

2、根据优先级队列中存放的树的结点构建起一棵树。

先出队前两个结点，然后创建一个新的树的结点，新的树的结点的权值就等于出队的两个结点的权值之和，但其没有字符域，也就是说它不是一个真正的树的结点，我们称其为假树结点，对应称为真树结点。
??让出队的两个真树结点作为新得到的假树结点的左右孩子，优先级小的真树结点（也就是先出队的真树结点）作为左孩子，另一个为右孩子。

在这里插入图片描述
出队后
在这里插入图片描述
b和c为真树结点，最上面权值为3的为假树结点
在这里插入图片描述

最后将新创建的假树结点又入队，继续循环操作，直到队列只剩一个结点，那个结点就是假树结点，最后也要作为Huffman树的根节点root。

新的假树结点入队后
在这里插入图片描述
到最后就是下面这样
队列只剩最后一个假树结点，而且作为所构建Huffman树的根节点root
在这里插入图片描述
在这里插入图片描述

3、遍历整棵树建起一张码表，通过观察我们发现，真正有意义的真树结点其实都是叶子节点，所以我们在遍历的时候将所有的叶子节点的编码和字符存入表中即可。
??我们规定遍历树建立表的时候，往左孩子访问一层给码值加0，往右就加1。比如刚刚介绍树的时候贴的那张图，b是00，c是01，a是1。

下面是建立起来的码表
在这里插入图片描述

构建Huffman树和创建编码表的实现过程

??看完思路之后再看实现过程，我们先看创建队列时候的一系列操作：

因为为了方便我用了部分C++语法，所以分配内存会是用new，释放内存就是delete，就和C语言里malloc和free是一个作用，其他的都一样。

?队列的初始化：

  1. queue Init_queue()
  2. {
  3.     queue q;
  4.     q.size = 0;
  5.     q.front = new struct QNode;
  6.     if (!q.front)
  7.     {
  8.         printf("分配失败！\n");
  9.         exit(1);
  10.     }
  11.     q.front->next = NULL;
  12.     return q;
  13. }

?队列的插入：

  1. //插入，根据优先级
  2. bool EnQueue(queue& q, Tree avl, int weight)
  3. {
  4.     Node newp = new struct QNode;
  5.     newp->val = avl;
  6.     newp->priority = weight;
  7.     if (q.size == 0 || q.front == NULL)         //空表
  8.     {
  9.         newp->next = NULL;
  10.         q.front = newp;
  11.         q.size = 1;
  12.         return true;
  13.     }
  14.     else        //中间位置，需要迭代
  15.     {
  16.         if (weight <= q.front->priority)    //比第一个都小
  17.         {
  18.             newp->next = q.front;
  19.             q.front = newp;
  20.             q.size++;
  21.             return true;
  22.         }
  23.         else    //中间位置
  24.         {
  25.             Node beforp = q.front;
  26.             while (beforp->next != NULL)
  27.             {
  28.                 if (weight <= beforp->next->priority)
  29.                 {
  30.                     newp->next = beforp->next;
  31.                     beforp->next = newp;
  32.                     q.size++;
  33.                     return true;
  34.                 }
  35.                 else
  36.                 {
  37.                     beforp = beforp->next;
  38.                 }
  39.             }
  40.             //需要插在队列最后
  41.             if (beforp->next == NULL)
  42.             {
  43.                 newp->next = NULL;
  44.                 beforp->next = newp;
  45.                 q.size++;
  46.                 return true;
  47.             }
  48.         }
  49.     }
  50.     return true;
  51. }

创建一个队列：
需要用户输入每个字符和对应的优先级

  1. //创建队列
  2. queue Create_Queue()
  3. {
  4.     queue q = Init_queue();
  5.     while (1)
  6.     {
  7.         char symbol;
  8.         int weight;
  9.         cin >> symbol >> weight;    //C++里的输入，输入symnol和weight
  10.         if (weight == 0)  //如果输入的权值为0，表示输入结束
  11.             break;
  12.         Tree t = new struct TNode;
  13.         t->data = symbol;
  14.         t->left = NULL;
  15.         t->right = NULL;
  16.         EnQueue(q, t, weight);
  17.     }
  18.     return q;
  19. }

弹出队列中优先级最小的结点：

  1. //弹出队列优先级最小的
  2. Tree Dequeue(queue& q)
  3. {
  4.     if (q.front == NULL)
  5.     {
  6.         cout << "空队！" << endl;
  7.         exit(1);
  8.     }
  9.     Node p = q.front;
  10.     q.front = p->next;
  11.     Tree e = p->val;
  12.     q.size--;
  13.     delete[] p;
  14.     return e;
  15. }

树的函数，根据优先级队列创建一棵树：

  1. //树的函数
  2. //创建一棵树
  3. Tree Create_Tree(queue& q)
  4. {
  5.     while (q.size != 1)
  6.     {
  7.         int priority = q.front->priority + q.front->next->priority;
  8.         Tree left = Dequeue(q);
  9.         Tree right = Dequeue(q);
  11.         Tree newTNode = new struct TNode;
  12.         newTNode->left = left;
  13.         newTNode->right = right;
  15.         EnQueue(q, newTNode, priority);
  16.     }
  17.     Tree root = new struct TNode;
  18.     root = Dequeue(q);
  19.     return root;
  20. }

表的函数，根据树创建一张表：

  1. //创建一张表
  2. table Create_Table(Tree root)
  3. {
  4.     table t = new struct Table;
  5.     t->first = NULL;
  6.     t->last = NULL;
  7.     char code[256];
  8.     int k = 0;
  9.     travel(root, t, code, k);
  10.     return t;
  11. }

表的函数，对travel函数的实现：
travel函数表示对树的遍历，从而建立起表，采用表尾插入法

  1. void travel(Tree root, table& t, char code[256], int k)
  2. {
  3.     if (root->left == NULL && root->right == NULL)
  4.     {
  5.         code[k] = '\0';
  7.         bNode b = new struct BNode;
  8.         b->symbol = root->data;
  9.         strcpy(b->code, code);
  10.         b->next = NULL;
  12.         //尾部插入法
  13.         if (t->first == NULL)       //空表
  14.         {
  15.             t->first = b;
  16.             t->last = b;
  17.         }
  18.         else
  19.         {
  20.             t->last->next = b;
  21.             t->last = b;
  22.         }
  23.     }
  24.     if (root->left != NULL)
  25.     {
  26.         code[k] = '0';
  27.         travel(root->left, t, code, k + 1);
  28.     }
  29.     if (root->right != NULL)
  30.     {
  31.         code[k] = '1';
  32.         travel(root->right, t, code, k + 1);
  33.     }
  34. }

编解码

至此，Huffman树以及编码表已经构建完毕，现在就来实现编解码的函数来检验上述的Huffman树。

编码：
需要传入编码表来进行编码

  1. void EnCode(table t, char* str)
  2. {
  3.     cout << "EnCodeing............./" << endl;
  4.     int len = strlen(str);
  5.     for (int i = 0; i < len; i++)
  6.     {
  7.         bNode p = t->first;
  8.         while (p != NULL)
  9.         {
  10.             if (p->symbol == str[i])
  11.             {
  12.                 cout << p->code;
  13.                 break;
  14.             }
  15.             p = p->next;
  16.         }
  17.     }
  18.     cout << endl;
  19. }

解码：
需要传入Huffman树来进行编码

  1. void DeCode(Tree root, char* str)
  2. {
  3.     cout << "DeCode............./" << endl;
  4.     Tree p = root;
  5.     int len = strlen(str);
  6.     for (int i = 0; i < len; i++)
  7.     {
  8.         if (p->left == NULL && p->right == NULL)
  9.         {
  10.             cout << p->data;
  11.             p = root;
  12.         }
  13.         if (str[i] == '0')
  14.             p = p->left;
  15.         if (str[i] == '1')
  16.             p = p->right;
  17.         if (str[i] != '0' && str[i] != '1')
  18.         {
  19.             cout << "The Input String Is Not Encoded correctly !" << endl;
  20.             return;
  21.         }
  22.     }
  23.     if (p->left == NULL && p->right == NULL)
  24.         cout << p->data;
  25.         cout << endl;
  26. }

测试数据

  1. int main()
  2. {
  3.     queue q = Create_Queue();
  4.     Tree root = Create_Tree(q);
  5.     table t = Create_Table(root);
  6.     char str[256];
  7.     cout << "请输入要编码的字符：" << endl;
  8.     cin >> str;
  9.     EnCode(t, str);
  10.     cout << "请输入要解码的码值：" << endl;
  11.     char str1[256];
  12.     cin >> str1;
  13.     DeCode(root, str1);
  14. }

附上截图：
在这里插入图片描述

原文链接：http://www.cnblogs.com/vfdxvffd/p/11622261.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？
  • 《花100块做个摸鱼小网站! 》第三篇—热搜表结构设计和热搜数据存储
  • Fluent Editor：一个基于 Quill 2.0 的富文本编辑器，功能强大、开箱即用！
  • 方法的三种调用形式
  • 《花100块做个摸鱼小网站! 》第二篇—后端应用搭建和完成第一个爬虫
  • 《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(4)-再识Wireshark - 北京-宏哥
  • 《软件性能测试分析与调优实践之路》(第2版) 读书笔记（二）总体介绍（下）-真正从性能分析与调优来看性能测试
  • 架构知识点（三）
  • 《花100块做个摸鱼小网站! 》第一篇—买云服务器和初始化环境

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号