前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >哈夫曼树 编码-【UVA No. 12676】转换哈夫曼编码 Inverting Huffman

哈夫曼树 编码-【UVA No. 12676】转换哈夫曼编码 Inverting Huffman

作者头像
囍楽云
发布2022-12-29 09:20:14
3660
发布2022-12-29 09:20:14
举报
文章被收录于专栏:囍楽云博客

  【UVA No. 12676】转换哈夫曼编码

  洛谷题目地址

  【题意】

  静态哈夫曼编码是一种主要用于文本压缩的编码算法。给定一个由N 个不同字符组成的特定长度的文本,算法选择N 个编码哈夫曼树 编码,每个不同的字符都对应一个编码。使用这些编码压缩文本,当选择编码算法构建一个具有N 个叶子的二叉树时,对于N ≥2,树的构建流程如下。

  ① 对文本中的每个不同字符,都构建一个仅包含单个节点的树,其权值为该字符在文本中的出现次数。

  ② 构建一个包含上述N 棵树的集合S 。

  ③ 当S 包含多于一棵树时:①选择最小的权值t 1 ∈S ,并将其从S 中删除;②选择最小的权值t 2 ∈S ,并将其从S 中删除;③构建一棵新树t ,t 1 为其左子树,t 2 为其右子树,t 的权值为t 1 、t 2值之和;④将t 加入S 集合。

  ④ 返回保留在S 中的唯一一棵树。

  对于文本“”,由上述过程生成的树,可以像下面左图,其中每个叶子节点内都是该字符在文本中出现的次数(权值)。

  请注意获得的树不是唯一的,也可以像下面右图或其他,因为可能包含几个权值最小的树。

  对文本中的每个不同字符,其编码都取决于最终树中从根到对应字符的叶子之间的路径,编码的长度是这条路径中的边数。假设该算法构建的是左侧的树,“r”的代码长度为3,“d”的代码长度为4。根据算法选择的N 个代码的长度,找所有字符总数的最小值。

  【输入输出】

  输入:

  输入包含多个测试用例,每个测试用例的第1行都包含一个整数N (2≤N ≤50),表示在文本中出现的不同字符数。第2行包含N个整数Li (1≤Li ≤50,i =1,2,…,N ),表示由哈夫曼算法生成的不同字符的编码长度。假设至少存在一棵由上述算法构建的树,那么可以生成具有给定长度的编码。

  输出:

  对每个测试用例都输出一行,表示所有字符总数的最小值。

  【样例】

  【思路分析】

  本题不是简单的哈夫曼编码问题,而是根据编码长度哈夫曼树 编码,推测最小字符数。

  例如:

   4 //表示4个不同字符

代码语言:javascript
复制
    3 1 2 3 //每个[字符编码][2]长度

  其最长编码为3,即最大深度为3。底层节点的权值至少为1,每一层节点的权值至少是下一层节点权值的最大值。

  如果当前节点的权值比下一层节点的权值小,就会出现在下一层了,因为权值越小,出现的层次越大,如下图所示。

  根据编码长度推测,该文本至少有5个字符:1个a、1个d、1个c、2个b。

  【算法设计】

  ① 在每一层都用一个深度数组deep[]记录该层节点的权值,将该层每个节点的权值都初始化为0,等待推测权值。

  ② 根据输入的编码长度算出最大长度,即哈夫曼树的最大深度maxd。

  ③ 从最大深度maxd向上计算并推测,直到树根。开始时temp=1。

  【算法实现】

代码语言:javascript
复制
#include
#include
#include
using namespace std;
const int maxn=55;
vectordeep[maxn];
int main(){
    
    int n,x;
    while(cin>>n){
        
        for(int i=0;ix;
            deep[x].push_back(0);
            maxd=max(maxd,x);//求最大深度 
            
        }
        long long temp=1;
        
        for(int i=maxd;i>0;i--){
            
            for(int j=0;j
[1]: https://xuan.ddwoo.top/index.php/archives/244/
[2]: https://xuan.ddwoo.top/index.php/archives/249/                
        本文共 838 个字数,平均阅读时长 ≈ 3分钟
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档