#include "stdio.h"
#include "iostream.h"
#include <malloc.h>
#include <conio.h>
#define NULL 0
#define MAX 100
#define LEN sizeof (struct HuffmanTree)
struct HuffmanTree{
char data;
struct HuffmanTree *right,*left,*parent;
};
HuffmanTree *CreateHumanTree(){ //建立哈夫曼树
HuffmanTree *b,*a,*HT;
char A[MAX]={NULL},e;int B[MAX]={NULL},i=0,j=0,k=0,l=0,m;
cout<<"请输入要进行编码的字符:"<<endl;
e=getchar();
while(e!='\n')A[i]=e,i++,e=getchar();
for(j=0;j<i;j++)
cout<<"请为你输入第"<<j+1<<"的个字符权值:"<<endl,scanf("%d",&B[j]);
k=B[0];
for(j=0;j<i;j++)
if(B[j]!=NULL&&k>B[j])k=B[j],l=j;
HT=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元
HT->data=A[l]; HT->left=NULL;HT->right=NULL;
B[l]=NULL;
for(m=1;m<i;m++){
j=0;
while(B[j]==NULL&&j<i)j++;
k=B[j];l=j;
for(j=0;j<i;j++)
if(B[j]!=NULL&&k>B[j])k=B[j],l=j;
a=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元
a->data=A[l];B[l]=NULL;a->left=NULL;a->right=NULL;
b=(struct HuffmanTree *)malloc(LEN);//开辟一个新单元
b->left=a;a->parent=b;b->right=HT;HT->parent=b;
HT=b;
}
return HT;
}
void HuffmanCode(HuffmanTree *HT){//生成哈夫曼编码
int i=0,j;
if(HT->left==NULL)cout<<HT->data<<"的哈夫曼编码是:0\n";//当只有一个结点的时候编码为“0”
else{
loop: if(HT->left!=NULL){
HT=HT->left;i++;
cout<<HT->data<<"的哈夫曼编码是:";
for(j=1;j<i;j++)cout<<"1";
cout<<"0\n";
HT=HT->parent;HT=HT->right;
goto loop;}
cout<<HT->data<<"的哈夫曼编码是:";
for(j=0;j<i;j++)cout<<"1";
}
}
void main(){
HuffmanTree *HT;
HT=CreateHumanTree();
HuffmanCode(HT);
cout<<"\n完成"<<endl;
getch();
}