哈弗曼编码与译码

2023-10-14 04:48
文章标签 编码 译码 弗曼

本文主要是介绍哈弗曼编码与译码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目的链接为： http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1022
题目的描述为：
哈夫曼编码与译码
时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:343            测试通过:123

描述

已知电文包括的字符集为{A，C，I，M，N，P，T，U}，输入对应权值，对字符集合进行哈夫曼编码，完成电文的哈夫曼编码与译码工作。

输入


共三行：
第一行为对应字符集{A，C，I，M，N，P，T，U}的权值
第二行为一段字符串表示的电文(长度不超过1000）；
第三行为一段电文的哈夫曼编码。

输出


共十行：

前八行为各字符的编码；

第九行是与第二行输入对应的哈夫曼编码；

第十行是与第三行输入对应的电文。


样例输入

1 2 3 4 5 6 7 8
NUPTICPCACM
1111011111100

样例输出

A: 11110
C: 11111
I: 1110
M: 100
N: 101
P: 110
T: 00
U: 01
1010111000111011111110111111111011111100
ACM

哈弗曼编码，是一种很常用的压缩数据的方式。它将频率出现得高的用短编码，频率出现得低的字母用长编码。对哈夫曼编码的理解，就是对压缩的理解。
如对于A，C，I，M，N，P，T，U
他们出现的频率为1,2,3,4,5,6,7,8
首先将他们全都变为单个的树节点，然后将权重小的组成树，即选择1,2组成树，这个树的权重为3，左子树为1，右子树为2，将新的树放入集合。
3(1,2),3,4,5,6,7,8
最小的是权重为3的两颗树，将其合并为新的树，并放入集合：
4,5,6,6（3（1,2），3），7,8
依次类推，就可以建立一颗哈弗曼树。哈夫曼树从节点到左子树根节点为0，到右子树根节点为1。按照这个规则，我们可以根据从根节点到叶子节点的路径，得知叶子节点所代表的字母的编码。译码即逆向思维。
其实对树比较熟悉的话，这道题比较容易就能够做出来。
代码如下：
C++代码 复制代码
  1. #include<iostream>   
  2. #include<algorithm>   
  3. #include<string>   
  4. #define MAXNUM 1001   
  5. using namespace std;   
  6. //哈夫曼树的节点   
  7. typedef struct node{   
  8.   
  9.     //树节点的标志    
  10.     char data;         
  11.     //树节点的权重   
  12.     int weight;   
  13.     //左右孩子   
  14.     int lchild;   
  15.     int rchild;   
  16.     //是否已经被放入树中    
  17.     bool tag;    
  18. }myNode;    
  19. bool compare(myNode mynode1,myNode mynode2)   
  20. {   
  21.     return mynode1.weight<mynode2.weight;    
  22. }   
  23. myNode nodes[100];   
  24. char mycode[100];   
  25. char ch[]={'A','C','I','M','N','P','T','U'};   
  26. int index=-1;   
  27. int index1=-1;   
  28. //记录每个字母的哈弗曼编码    
  29. string str[8];   
  30. myNode recordNode;   
  31. bool judge()   
  32. {   
  33.    int record=0;   
  34.    for(int i=0;i<=index;i++)   
  35.    {   
  36.         if(nodes[i].tag==false)   
  37.         {   
  38.            record++;   
  39.            recordNode=nodes[i];   
  40.         }    
  41.    }    
  42.    if(record==0||(record==1&&recordNode.data=='#'))   
  43.    {   
  44.         return true;   
  45.    }   
  46.    return false;   
  47. }   
  48. int findNode()   
  49. {   
  50.    for(int i=0;i<=index;i++)   
  51.    {   
  52.         if(nodes[i].tag==false)   
  53.         {   
  54.              nodes[i].tag=true;   
  55.              return i;   
  56.         }   
  57.    }    
  58.    return -1;   
  59. }   
  60. //编码   
  61. bool code(myNode *root,char ch1)   
  62. {   
  63.    bool tag=false;   
  64.    if(root->data==ch1)   
  65.    {   
  66.          return true;    
  67.    }   
  68.    int arr[2];   
  69.    arr[0]=root->lchild;   
  70.    arr[1]=root->rchild;   
  71.    for(int i=0;i<2;i++)   
  72.    {   
  73.        if(arr[i]!=-1)   
  74.        {      
  75.            tag=code(&nodes[arr[i]],ch1);   
  76.            if(tag)   
  77.            {   
  78.                if(i==0)   
  79.                {   
  80.                       mycode[++index1]='0';    
  81.                }    
  82.                else if(i==1)   
  83.                {   
  84.                       mycode[++index1]='1';    
  85.                }    
  86.            }    
  87.            if(tag)   
  88.            {   
  89.                 return tag;    
  90.            }   
  91.        }    
  92.    }   
  93.   
  94.    return tag;   
  95. }    
  96. //创建哈弗曼树    
  97. void createTree()   
  98. {   
  99.     while(!judge())   
  100.     {   
  101.          //按照权重由小到大排序    
  102.          sort(nodes,nodes+index+1,compare);    
  103.                
  104.          myNode newNode;   
  105.          newNode.data='#';   
  106.          newNode.lchild=findNode();   
  107.          newNode.rchild=findNode();   
  108.          newNode.weight=nodes[newNode.lchild].weight+nodes[newNode.rchild].weight;   
  109.          newNode.tag=false;   
  110.           
  111.          nodes[++index]=newNode;   
  112.     }   
  113. }   
  114. //输出字母对应的编码    
  115. void outputCode(char cha)   
  116. {   
  117.     for(int i=0;i<8;i++)   
  118.     {   
  119.          if(cha==ch[i])   
  120.          {   
  121.              cout<<str[i];   
  122.              break;    
  123.          }    
  124.     }   
  125. }   
  126. //译码   
  127. void decode1(string inputstr)   
  128. {   
  129.     int kkindex=-1;   
  130.     int len=inputstr.length();   
  131.     while(kkindex<len)   
  132.     {   
  133.            bool find=false;   
  134.            myNode tempNode=nodes[index];   
  135.            char ch;   
  136.            while(!find&&kkindex<len)   
  137.            {   
  138.                   ++kkindex;   
  139.                   if(inputstr[kkindex]=='0')   
  140.                   {   
  141.                        tempNode=nodes[tempNode.lchild];    
  142.                   }   
  143.                   else  
  144.                   {   
  145.                        tempNode=nodes[tempNode.rchild];   
  146.                   }   
  147.                   ch=tempNode.data;   
  148.                   if(ch!='#')   
  149.                   {   
  150.                         find=true;   
  151.                   }   
  152.            }   
  153.            if(ch!='#')   
  154.            {   
  155.               cout<<ch;   
  156.            }   
  157.     }   
  158. }    
  159. void input()   
  160. {   
  161.     for(int i=0;i<8;i++)   
  162.     {   
  163.          int data;   
  164.          cin>>data;   
  165.             
  166.          nodes[++index].data=ch[i];   
  167.          nodes[index].weight=data;   
  168.          nodes[index].lchild=-1;   
  169.          nodes[index].rchild=-1;   
  170.          nodes[index].tag=false;   
  171.     }    
  172.        
  173.     //构造哈夫曼树    
  174.     createTree();   
  175.        
  176.     //recordNode故为树的根    
  177.     for(int i=0;i<8;i++)   
  178.     {   
  179.          index1=-1;   
  180.          code(&(nodes[index]),ch[i]);   
  181.          str[i]="";   
  182.          for(int j=index1;j>=0;j--)   
  183.          {   
  184.              str[i]+=mycode[j];   
  185.          }   
  186.     }   
  187.        
  188.     //输出   
  189.     for(int i=0;i<8;i++)   
  190.     {   
  191.          cout<<ch[i]<<": ";   
  192.          cout<<str[i]<<endl;    
  193.     }    
  194.        
  195.     //获得输入的字符串   
  196.     string inputstr;   
  197.     cin>>inputstr;   
  198.     for(int i=0;i<inputstr.length();i++)   
  199.     {   
  200.         outputCode(inputstr[i]);    
  201.     }    
  202.     cout<<endl;   
  203.        
  204.     //输出译码结果   
  205.     cin>>inputstr;    
  206.     decode1(inputstr);   
  207.     cout<<endl;   
  208. }   
  209. int main()   
  210. {   
  211.    input();   
  212.       
  213.    system("pause");   
  214.    return 0;    
  215. }  

这篇关于哈弗曼编码与译码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/208242。

相关文章

Python使用自带的base64库进行base64编码和解码

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意
阅读更多...
VSCode中C/C++编码乱码问题的两种解决方法

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一：通过 Code Runner 插件调整编码配置步骤方法二：在 PowerShell
阅读更多...
Python如何实现读取csv文件时忽略文件的编码格式

Python如何实现读取csv文件时忽略文件的编码格式

《Python如何实现读取csv文件时忽略文件的编码格式》我们再日常读取csv文件的时候经常会发现csv文件的格式有多种,所以这篇文章为大家介绍了Python如何实现读取csv文件时忽略文件的编码格式... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍我们再日常读取csv文件的时候经常
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
form表单提交编码的问题

form表单提交编码的问题

浏览器在form提交后，会生成一个HTTP的头部信息"content-type"，标准规定其形式为Content-type: application/x-www-form-urlencoded; charset=UTF-8        那么我们如果需要修改编码，不使用默认的，那么可以如下这样操作修改编码，来满足需求： hmtl代码：   <meta http-equiv="Conte
阅读更多...
4-4.Andorid Camera 之简化编码模板（获取摄像头 ID、选择最优预览尺寸）

4-4.Andorid Camera 之简化编码模板（获取摄像头 ID、选择最优预览尺寸）

一、Camera 简化思路 在 Camera 的开发中，其实我们通常只关注打开相机、图像预览和关闭相机，其他的步骤我们不应该花费太多的精力 为此，应该提供一个工具类，它有处理相机的一些基本工具方法，包括获取摄像头 ID、选择最优预览尺寸以及打印相机参数信息 二、Camera 工具类 CameraIdResult.java public class CameraIdResult {
阅读更多...
Python字符编码及应用

Python字符编码及应用

字符集概念 字符集就是一套文字符号及其编码的描述。从第一个计算机字符集ASCII开始，为了处理不同的文字，发明过几百种字符集，例如ASCII、USC、GBK、BIG5等，这些不同的字符集从收录到编码都各不相同。在编程中出现比较严重的问题是字符乱码。 几个概念 位：计算机的最小单位二进制中的一位，用二进制的0，1表示。 字节：八位组成一个字节。（位与字节有对应关系） 字符：我们肉眼可见的文字与符号。
阅读更多...
在Eclipse环境下修改Tomcat编码的问题

在Eclipse环境下修改Tomcat编码的问题

问题： 由于BMS需要设置UTF-8编码，要不就会出现中文乱码问题； 一、项目保持UTF-8格式； 二、由于可能会多次移除项目、加载项目，不想每次都要修改tmp0\conf 原因： 如果在eclipse中配置了tomcat后，其实，tomcat所用的所有tomcat配置文件，都不是catalina_home/config下面的xml文件，而是在eclipse所创建的Serve
阅读更多...
在Unity环境中使用UTF-8编码

在Unity环境中使用UTF-8编码

为什么要讨论这个问题         为了避免乱码和更好的跨平台         我刚开始开发时是使用VS开发,Unity自身默认使用UTF-8 without BOM格式,但是在Unity中创建一个脚本,使用VS打开,VS自身默认使用GB2312(它应该是对应了你电脑的window版本默认选取了国标编码,或者是因为一些其他的原因)读取脚本,默认是看不到在VS中的编码格式,下面我介绍一种简单快
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2