一、实验要求与目的
1、熟悉贪心算法的基本原理与适用范围。
2、使用贪心算法编程给出哈夫曼编码。
二、实验内容
编程实现哈夫曼编码，并给出测试实例
三、实现思想
运用优先队列的数据结构， 我们在考虑k元Huffman编码时，最大费用肯定是二叉的情况，因为深度越大，被加的次数会越多，另外，优先队列中数值大的优先级越高；但是最小费用和就是k叉了，与二叉不同的时，我们可以这样考虑，如果最后一次不足k叉，那么肯定不是最优解，那么我们只能通过补0的方式让最后一次又添加(k-1)个新的元素，即可实现。
四、实现代码
#include
#include
#include
#include
#include
using namespace std; #define mmax 999 int stone[mmax]; int max_stone(int n,int k){ priority_queue
q; //生成最大优先队列 for(int i=0;i
2){ sum=0; for(int i=0;i<2;i++) { sum+=q.top(); q.pop(); } max+=sum; q.push(sum); } while(!q.empty()){ max+=q.top(); q.pop(); } return max; } int min_stone(int n,int k){ priority_queue
,greater
> q; //生成最小优先队列 int m=(n-1)%(k-1); n=n+(k-1-m)%(k-1); //补充0 for(int i=0;i
k){ sum=0; for(int i=0;i
>n>>k; for(int i=0;i
>stone[i]; cout<
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/223173.html原文链接：https://javaforall.net
![Base64编码与图片互转工具[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
