#include<stdio.h>
#include <malloc.h>
#include <iostream.h>
#include <string.h>
#include <process.h>
#include <conio.h>
#include<iomanip.h>
const int max=10000; //初始设定的最大权值
typedef struct
{
char message;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
HuffmanTree Readdata(HuffmanTree HT,int n,int m)
{
int i;
HT=(HTNode*)malloc((m+1)*sizeof(HTNode));
//初始化0.....n-1;
HTNode* p=NULL;
for(p=HT,i=0;i<n;++i,++p)
{
p->lchild=0;
p->rchild=0;
p->parent=0;
cout<<"请输入第"<<i<<"个结点的字符:"<<endl;
cin>>p->message;
cout<<"请输入第"<<i<<"个结点的权值:"<<endl;
cin>>p->weight;
}
//初始化n......2*n-1;
for(;i<=m;++i,++p)
{
p->lchild=0;
p->rchild=0;
p->parent=0;
p->message=' ';
p->weight=0;
}
return HT;
}
HuffmanCode Coding(HuffmanTree HT,HuffmanCode HC,int n,int m)
{
int i,start,f,c;
char *cd=(char *)malloc (n*sizeof(char));
cd=(char*)malloc(n*sizeof(char));//分配编码的工作空间
cd[n-1]=' ';//编码结束
for(i=0;i<=n;i++)//各个字符求编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//叶子到根逆向求编码
if(HT[f].lchild==c)cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc( (n-start) * sizeof(char) );//求第I个字符编码
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}
void Showchange(HuffmanTree HT,int m)
{
int i;
for(i=0;i<m;i++)//
{
cout<<setw(10)<<"weight"<<ends<<"parent"<<ends<<"lchild"<<ends<<"rchild"<<endl;
cout<<"第"<<i<<"个结点的信息:"<<endl;
cout<<setw(10)<<HT[i].weight<<ends<<ends<<ends<<ends<<HT[i].parent<<ends<<ends<<ends<<ends<<HT[i].lchild<<ends<<ends<<ends<<ends<<ends<<HT[i].rchild<<endl;
}
}
void showcode(HuffmanTree HT,HuffmanCode &HC,int n)
{
int i;
for(i=0;i<n;i++)
cout<<"字符"<<i<<":"<<HT[i].message<<"权值:"<<HT[i].weight<<"编码:"<<HC[i]<<endl;
}
HuffmanTree Init(HuffmanTree HT,int n,int m)
{
int m1,m2,s1,s2,i,j;//m1,m2找出最小的两个.
for(i=n;i<m;++i)//建赫夫曼树
{
m1=m2=max;
s1=s2=0;
for(j=0;j<i;++j)
{
if((HT[j].weight!=0)&&HT[j].weight<m1 && HT[j].parent==0)
{ m2=m1;
s2=s1;
m1=HT[j].weight;
s1=j;
}
else if( (HT[j].weight!=0)&&HT[j].weight<m2 && HT[j].parent==0 )
{
m2=HT[j].weight;
s2=j;
}
}
//将找出的两棵权值最小的子树合并为一棵子树,并且小的在左边;
{
if(s1>s2)
{
int temp;
temp=s1;s1=s2;s2=temp;
}
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<<"After select s1,s2:"<<s1<<" , "<<s2<<endl;
Showchange(HT,m);
}
}
return HT;
}
void main()
{
int n,m;
cout<<"Huffman.cpp运行结果:n"<<endl;
cout<<"请输入结点个数>1 的整数"<<endl;
cin>>n;
m=2*n-1;
HTNode* HT=NULL;
HT=Readdata(HT,n,m);
HT=Init(HT,n,m);
char** HC=(HuffmanCode)malloc((n)*sizeof(char *));//分配N个字符编码的头指针向量
HC=Coding(HT,HC,n,m);
showcode(HT,HC,n);
}
