哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含100,000个字符的文件,各字符出现频率不同,如下表所示。 有多种方式表示文件中的信息,若用0,1码表示字符的方法,即每个字符用唯一的一个0,1串表示。若采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300,000位;若采用变长编码表示,给频率高的字符较短的编码;频率低的字符较长的编码,达到
//4d4 贪心算法 哈夫曼算法
#include "stdafx.h"
#include "BinaryTree.h"
#include "MinHeap.h"
#include <iostream>
using namespace std;
const int N = 6;
template<class Type> class Huffman;
template<class Type>
BinaryTree<int> HuffmanTree(Type f[],int n);
template<class Type>
class Huffman
{
friend BinaryTree<int> HuffmanTree(Type[],int);
public:
operator Type() const
{
return weight;
}
//private:
BinaryTree<int> tree;
Type weight;
};
int main()
{
char c[] = {'0','a','b','c','d','e','f'};
int f[] = {0,45,13,12,16,9,5};//下标从1开始
BinaryTree<int> t = HuffmanTree(f,N);
cout<<"各字符出现的对应频率分别为:"<<endl;
for(int i=1; i<=N; i++)
{
cout<<c[i]<<":"<<f[i]<<" ";
}
cout<<endl;
cout<<"生成二叉树的前序遍历结果为:"<<endl;
t.Pre_Order();
cout<<endl;
cout<<"生成二叉树的中序遍历结果为:"<<endl;
t.In_Order();
cout<<endl;
t.DestroyTree();
return 0;
}
template<class Type>
BinaryTree<int> HuffmanTree(Type f[],int n)
{
//生成单节点树
Huffman<Type> *w = new Huffman<Type>[n+1];
BinaryTree<int> z,zero;
for(int i=1; i<=n; i++)
{
z.MakeTree(i,zero,zero);
w[i].weight = f[i];
w[i].tree = z;
}
//建优先队列
MinHeap<Huffman<Type>> Q(n);
for(int i=1; i<=n; i++) Q.Insert(w[i]);
//反复合并最小频率树
Huffman<Type> x,y;
for(int i=1; i<n; i++)
{
x = Q.RemoveMin();
y = Q.RemoveMin();
z.MakeTree(0,x.tree,y.tree);
x.weight += y.weight;
x.tree = z;
Q.Insert(x);
}
x = Q.RemoveMin();
delete[] w;
return x.tree;
}