Huffman编码
huffman编码的一个过程，统计字符总数，每个字符的出现频率。然后进行编码，下面是模拟这个过程。
先建立huffman树，然后按照一定的规则进行编码，便于译码时对照编码规则。
文件"tree.h"
#include<iostream>
using namespace std;
//栈模版
template<class T>
class My_stack;
template<class T>
class Node //结点类
{
private:
T data;
Node<T> *next;
public:
Node()
{
next=NULL;
}
Node(T d)
{
data=d;
next=NULL;
}
friend My_stack<T>;
};
template<class T>
class My_stack
{
private:
Node<T> *head;
public:
My_stack()
{
head=new Node<T>();
}
~My_stack()
{
clean();
delete head;
}
bool empty() const
{
return (head->next==0);
}
void push(T d) //入栈
{
Node<T> *p=new Node<T>(d);
p->next=head->next;
head->next=p;
}
T top() //返回栈顶元素
{
if(empty())
{
cout<<"stack is empty."<<endl;
exit(1);
}
Node<T> *p=head->next;
T temp=p->data;
return temp;
}
void pop() //弹出栈顶元素
{
Node<T> *p=head->next;
head->next=p->next;
delete p;
}
void clean() //清除整个栈
{
Node<T> *p=head->next;
while(p)
{
head->next=p->next;
delete p;
head->next=p;
}
}
};
class HuffmanTree;
class HuffmanNode
{
int data;
int parent,lchild,rchild;
friend HuffmanTree;
};
class HuffmanTree
{
public:
void Create_HuffmanTree(HuffmanNode *&HT,int w[],int n) //构建树
{
//用w申请的数组暂时保存权值（暂时设定全都大于0）
if(n<1)
{
cout<<"参数不合理"<<endl;
return ;
}
int m=2*n-1;
HT=new HuffmanNode[m]; //分配m个huffman结点
int i;
for(i=0;i<n;i++)
{
HT[i].data=w[i];
HT[i].lchild=-1;
HT[i].rchild=-1;
HT[i].parent=-1;
}
for(int j=i;j<m;j++)
{
HT[j].data=0;
HT[j].lchild=-1;
HT[j].rchild=-1;
HT[j].parent=-1;
}
//结点初始化完成，下面开始构造huffman树
int s1=-1,s2=-1;
for(i=n;i<m;i++)
{
Select(HT,i-1,s1,s2); //在HT[0...i-1]中选出parent为-1的且data最小的两个结点，序号分别用s1,s2返回
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].data=HT[s1].data+HT[s2].data;
}
cout<<"____huffman树构造完成____"<<endl;
}
void Select(HuffmanNode *HT,int n,int &a,int &b)
{
struct temp
{
int data;
int pos;
}c[100];
HuffmanNode *head=HT;
int i,k=0;
for(i=0;i<=n;i++)
{
if(head[i].parent==-1)
{
c[k].data=head[i].data;
c[k].pos=i;
k++;
}
}
//下面是简单的冒泡排序
bool flag;
for(int j=0;j<k-1;j++)
{
flag=false;
for(i=0;i<k-1-j;i++)
{
if(c[i].data>c[i+1].data)
{
temp q;
q.data=c[i+1].data;
q.pos=c[i+1].pos;
c[i+1].data=c[i].data;
c[i+1].pos=c[i].pos;
c[i].data=q.data;
c[i].pos=q.pos;
flag=true;
}
}
if(!flag)
break;
}
a=c[0].pos;
b=c[1].pos;
}
void Traverse(HuffmanNode *HT,int n) //观察
{
int m=2*n-1;
for(int i=m-1;i>=n;i--)
{
cout<<HT[i].data<<"={";
cout<<HT[HT[i].lchild].data<<',';
cout<<HT[HT[i].rchild].data<<'}';
cout<<endl;
}
}
void Huffman_Coding(HuffmanNode *HT,int n)
{
HuffmanNode *q;
int f,temp,p;
My_stack<int> s;
for(int i=0;i<n;i++)
{
q=HT;
f=i;
p=q[f].parent;
while(p!=-1)
{
if(q[p].lchild==f)
temp=0;
else
temp=1;
s.push(temp);
f=p;
p=q[p].parent;
}
cout<<"第"<<i+1<<"个字符的huffman编码为：";
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
cout<<endl;
}
}
};
测试函数“main.cpp”
#include"tree.h"
int main()
{
int n,*p;
cout<<"输入要编码的字母数目：";
cin>>n;
p=new int[n];
cout<<"输入各个字母频率权值大小：";
for(int i=0;i<n;i++)
cin>>p[i];
cout<<"____构造huffman树____"<<endl;
HuffmanTree tree;
HuffmanNode *HT;
tree.Create_HuffmanTree(HT,p,n);
cout<<"huffman树的结构为："<<endl;
tree.Traverse(HT,n);
cout<<endl;
tree.Huffman_Coding(HT,n);
return 0;
}
输入：
8
7 19 2 6 32 3 21 10
构建的huffman树的形状如下：
输出结果：
输入要编码的字母数目：8
输入各个字母频率权值大小：7 19 2 6 32 3 21 10
____构造huffman树____
____huffman树构造完成____
huffman树的结构为：
100={40,60}
60={28,32}
40={19,21}
28={11,17}
17={7,10}
11={5,6}
5={2,3}
第1个字符的huffman编码为：1 0 1 0
第2个字符的huffman编码为：0 0
第3个字符的huffman编码为：1 0 0 0 0
第4个字符的huffman编码为：1 0 0 1
第5个字符的huffman编码为：1 1
第6个字符的huffman编码为：1 0 0 0 1
第7个字符的huffman编码为：0 1
第8个字符的huffman编码为：1 0 1 1
Press any key to continue