#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0
#define OK 1
int n; //全局变量n

typedef struct HTNode{
char c; //待编码的字符
int weight; //权值
HTNode *parent,*lchild,*rchild;
}HTNode,*HuffmanTree;

typedef struct HTCode{ //编码结果
char a[100];
char c;
int weight;
}HTCode,*HuffmanCode;

int Select(HTNode *HT,int i,int *s1,int *s2)
{
int a[100],j,c; //a[100]用来存储权值以进行比较
HuffmanTree p;
*s1=1;
*s2=1;
for(j=1,p=HT;j<=i;++j,++p)
a[j]=p->weight;
for(j=1,c=a[1];j<i;j++) //找出权值最小的序号
if(c>a[j+1]){
c=a[j+1];
*s1=j+1;
}
a[*s1]=10000;
for(j=1,c=a[1];j<i;j++)
if(c>=a[j+1]){ //找出第二小权值的序号
c=a[j+1];
*s2=j+1;
}
return OK;
}

int HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC) //编码函数
{
int m,i,s1,s2,*ss1,*ss2,start;
char cd[100];
HuffmanTree p;
HuffmanCode q;
ss1=&s1; //用指针做参数传递，不需要返回值
ss2=&s2;
printf("输入要编码的字符数:\n");
scanf("%d",&n);
if(n<=1||n>=100){ //定义要编码的符号个数在1-100之间
printf("输入错误!\n");
return OK;
}
getchar(); //吃掉上面scanf留的空格
m=2*n-1; //m为结点数
(*HT)=(HTNode *)malloc((m+1)*sizeof(HTNode)); //申请m+1个结点的空间,0号结点未用
for(p=(*HT)+1,i=1;i<=n;i++,++p){
printf("输入第%d个要编码的字符\n",i);
scanf("%c",&p->c);
getchar();
printf("输入其权值\n");
scanf("%d",&p->weight);
getchar();
}
for(;i<=m;++i,++p){ //将其余结点全部置零
p->c=NULL;
p->weight=NULL;
p->lchild=NULL;
p->rchild=NULL;
}
p=(*HT);
for(i=n+1;i<=m;++i){
Select((*HT)+1,i-1,ss1,ss2);//在(*HT)[1..i-1]选择parent为0且weig(*HT)最小的两个结点,其
//序号分别为s1和s2,ss1,ss2分别为其指针
(p+s1)->parent=p+i; //构造一颗新的二叉树,且新的二叉树的根结点的权值为
(p+s2)->parent=p+i; //其左右子树上根结点的权值之和
if((p+s1)->weight==(p+i-1)->weight){
(p+i)->rchild=p+s1;
(p+i)->lchild=p+s2;
}
else{
(p+i)->rchild=p+s2;
(p+i)->lchild=p+s1;
}
(p+i)->weight=(p+s1)->weight+(p+s2)->weight;
(p+s1)->weight=10000; //将权值置为10000,即废弃不用
(p+s2)->weight=10000;
}
(*HC)=(HuffmanCode)malloc((n+1)*sizeof(char *));
(*HT)->weight=0;
for(i=1;i<=n;++i){
start=n-1;
cd[n-1]='\0';
for(p=(*HT)+i;p!=*HT+m;p=p->parent)
if(p->parent->lchild==p)
cd[--start]='0';
else
cd[--start]='1';
strcpy(((*HC)+i)->a,&cd[start]);
((*HC)+i)->c=((*HT)+i)->c;
}
for(q=(*HC)+1,i=1;i<=n;++q,++i){
printf("%c",((*HC)+i)->c);
printf("-----------------%s\n",((*HC)+i)->a);
}
*HT=(*HT)+m;
return OK;
}

int Visit(HuffmanTree HT)
{
if(HT->c>=65&&HT->c<=122){
printf("%c",HT->c);
return OK;
}
else
return ERROR;
}

int HuffmanDecoding(HuffmanTree *HT,int (* Visit)(HuffmanTree HT)) //译码函数
{
int i=0;
char a[100];
HuffmanTree p;
p=*HT;
printf("输入待解码的电文\n");
gets(a);
printf("译码后为\n");
for(i=0;a[i]!='\0';i++)
if(a[i]=='0')
if(Visit(p->lchild))
p=*HT;
else
p=p->lchild;
else
if(Visit(p->rchild))
p=*HT;
else
p=p->rchild;
printf("\n");
return OK;
}

int menu() //菜单函数
{
int c;
printf("1.赫夫曼编码\n"
"2.赫夫曼译码\n"
"3.退出\n");
scanf("%d",&c);
getchar();
return c;
}

int main()
{
HTNode *HT;
HTCode *HC;
while(1){
switch(menu()){
case 1:
HuffmanCoding(&HT,&HC);
break;
case 2:
HuffmanDecoding(&HT,Visit);
break;
case 3:
return OK;
}
}
}