using namespace std;
#define N 20 /*待编码字符的个数，即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/
#include <iostream>
using namespace std;
#define N 20 /*待编码字符的个数，即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/
class Huffman{
private:
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; //树的结构
HTNode *HT;
typedef struct{
char data; //待编码的字符
int weight; //字符的权值
char code[N]; //字符的编码
}HTCode; //编码表
HTCode *HC;
char *cd; //需要的编码空间
int n;
public:
Huffman();
~Huffman();
void SetValue(); //设置字符数,和权值
void Select(int k,int &s1,int &s2); //选择parent为0且weight最小的2个结点
void HuffmanCoding();
};
Huffman::Huffman(){
HT=new HTNode[N];
HC=new HTCode[M];
cd=new char[N];
n=0;
}
Huffman::~Huffman(){
delete []HT;
delete []HC;
delete []cd;
}
void Huffman::SetValue(){
int i;
cout<<"Input code number: "<<endl;
cin>>n;
cout<<"Input "<<n<<" charactor: "<<endl;
for(i=0;i<n;++i)
cin>>HC[i].data;
cout<<"Input code weight: "<<endl;
for(i=0;i<n;++i)
cin>>HC[i].weight;
}
void Huffman::Select(int k,int &s1,int &s2){
int i;
for(i=0;i<k;++i)
if(!HT[i].parent)
s1=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&HT[i].weight<HT[s1].weight)
s1=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&i!=s1)
s2=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
void Huffman::HuffmanCoding(){
//构造赫夫曼树HT,求出n个字符的赫夫曼编码HC
int i,m=0,s1=0,s2=0;
m=2*n-1;
for(i=0;i<m;++i) //初始化赫夫曼树
{
if(i<n)
HT[i].weight=HC[i].weight;
else
HT[i].weight=0;
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(i=n;i<m;++i) //构造赫夫曼树
{
Select(i,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
cout<<"\nHuffmanTree: "<<endl;
cout<<"weight\tparent\tlchild\trchild"<<endl;
for(i=0;i<m;++i)
cout<<HT[i].weight<<"\t"<<HT[i].parent
<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
cout<<endl<<endl;
cd[n-1]='\0';
int c=0,f=0,start=0;
for(i=0;i<n;++i) //逐个求赫夫曼编码
{
start=n-1; //编码结束符下标
for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)//从叶子到根结点求编码
if(HT[f].lchild==c)
cd[--start]='1';//左分支1
else
cd[--start]='0'; //右分支0
strcpy(HC[i].code,&cd[start]);
}
for(i=0;i<n;++i)
cout<<HC[i].data<<" --- "<<HC[i].code<<endl;
}
int main(){
Huffman h;
h.SetValue();
h.HuffmanCoding();
system("pause");
return 0;
}
Huffman::Huffman(){
HT=new HTNode[N];
HC=new HTCode[M];
cd=new char[N];
n=0;
}
Huffman::~Huffman(){
delete []HT;
delete []HC;
delete []cd;
}
void Huffman::SetValue(){
int i;
cout<<"Input code number: "<<endl;
cin>>n;
cout<<"Input "<<n<<" charactor: "<<endl;
for(i=0;i<n;++i)
cin>>HC[i].data;
cout<<"Input code weight: "<<endl;
for(i=0;i<n;++i)
cin>>HC[i].weight;
}
void Huffman::Select(int k,int &s1,int &s2){
int i;
for(i=0;i<k;++i)
if(!HT[i].parent)
s1=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&HT[i].weight<HT[s1].weight)
s1=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&i!=s1)
s2=i;
for(i=0;i<k;++i)
if(!HT[i].parent&&HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
void Huffman::HuffmanCoding(){
//构造赫夫曼树HT,求出n个字符的赫夫曼编码HC
int i,m=0,s1=0,s2=0;
m=2*n-1;
for(i=0;i<m;++i) //初始化赫夫曼树
{
if(i<n)
HT[i].weight=HC[i].weight;
else
HT[i].weight=0;
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(i=n;i<m;++i) //构造赫夫曼树
{
Select(i,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
cout<<"\nHuffmanTree: "<<endl;
cout<<"weight\tparent\tlchild\trchild"<<endl;
for(i=0;i<m;++i)
cout<<HT[i].weight<<"\t"<<HT[i].parent
<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
cout<<endl<<endl;
cd[n-1]='\0';
int c=0,f=0,start=0;
for(i=0;i<n;++i) //逐个求赫夫曼编码
{
start=n-1; //编码结束符下标
for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)//从叶子到根结点求编码
if(HT[f].lchild==c)
cd[--start]='0';//左分支0
else
cd[--start]='1'; //右分支1
strcpy(HC[i].code,&cd[start]);
}
for(i=0;i<n;++i)
cout<<HC[i].data<<" --- "<<HC[i].code<<endl;
}
int main(){
Huffman h;
h.SetValue();
h.HuffmanCoding();
system("pause");
return 0;
}
[[it] 本帖最后由 无聊人士 于 2008-6-10 23:01 编辑 [/it]]
----------------解决方案--------------------------------------------------------
偶以前写的,码有点糙.. 希望对你有帮助！
----------------解决方案--------------------------------------------------------
楼上要是早点给出啦。。我就不写了。。呵呵。。
----------------解决方案--------------------------------------------------------