#include<stdio.h>
#include<string.h>
#define MAX 99
char cha[MAX];
char hc[MAX-1][MAX];
int s1,s2; //设置全局变量，以便在方法(函数)select中返回两个变量

typedef struct //huffman树存储结构
{
unsigned int weight;//权值
int lchild,rchild,parent;
}huftree;

void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点
{
int i;
for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;//初始化s1
for (i=1;i<=k;i++)
if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;//把最小值赋给s1
for (i=1; i<=k ; i++)
if (tree[i].parent==0 && i!=s1) break; s2=i;//初始化s2
for (i=1;i<=k;i++)
if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;//把最小值赋给s2
}

void huffman(huftree tree[],int *w,int n) //生成huffman树
{ int m,i;
if (n<=1) return;
m=2*n-1;
for (i=1;i<=n;i++)//给tree中每个结点权值赋值，且分别给左右孩子及双亲初始化
{ tree[i].weight=w[i]; tree[i].parent=0;
tree[i].lchild=0; tree[i].rchild=0; }
for (i=n+1;i<=m;i++)//给除了叶子结点下的其它结点初始化
{ tree[i].weight=0; tree[i].parent=0;
tree[i].lchild=0; tree[i].rchild=0; }
for (i=n+1;i<=m;i++)//最终结果
{ select(tree, i-1);
tree[s1].parent=i;
tree[s2].parent=i;
tree[i].lchild=s1;
tree[i].rchild=s2; 
tree[i].weight =tree[s1]. weight+ tree[s2].weight;
}
}

void huffmancode(huftree tree[],char code[],int n)//输出huffman编码
{
int start,c,i,f;
printf("哈夫曼树：");//输出hufftree
for(i=1;i<=2*n-1;i++)
printf("5d%",i);
printf("5d%",tree[i].weight);
printf("5d%",tree[i].parent);
printf("5d%",tree[i].lchild);
printf("5d%",tree[i].rchild);
printf("\n");
code[n-1]='\0';//
printf("哈夫曼编码:\n");
for(i=1;i<=n;i++)
{start=n-1;
for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)//输出huffman编码
{if(tree[f].lchild==c)code[--start]='0';//把编码存入code
else code[--start]='1';}
strcpy(hc[i],&code[start]);//把code分别复制给hc
printf("%s",cha[i]);
printf("-->");
printf("%s",hc[i]);
printf("\n");//分别输出编码 for是满足条件进入
}
}


void tohuffmancode(int n)//编码部分
{
int i=0,j;
char anychar[9999];
printf("请输入你要编码的字符串:\n");
printf(">>>");
gets(anychar);
printf("编码为:");
for (;anychar[i]!='\0';i++)
{
j=0;
for(;anychar[i]!=cha[j]&&j<=n;) j++;
if (j<=n) 
printf("%d",hc[j]);
}
printf("\n");
}

void decode(char ch[],huftree tree[],int n)//译码
{
int i,j,m;char b;
m=2*n-1;
i=m;
printf("请输入编码:\n");
printf(">>>");
scanf("%d",b);
printf("译码为:");
while(b!=10) //遇到回车时，结束
{

if(b=='0')i=tree[i].lchild;
else i=tree[i].rchild;
if(tree[i].lchild==0)
{printf("%d",ch[i]);
j=i,i=m;
}

}
if(tree[j].lchild!=0)
printf("\nERROR\n");
}

main()
{
int i=0,n=0;
int *w,weight[MAX];
char code[MAX];
huftree tree[MAX];
w=weight;
char in;
while (in!='5')
{
printf(" ---------------哈夫曼编码-------------\n");
printf("1 建立初始化哈夫曼树 2 输出哈夫曼编码 3 编码 4 译码 5 退出\n");
printf("请输入(1--5):");
scanf("%d",in);
printf("\n");
switch (in)
{
case '1': printf("请输入待编码字符个数:");
scanf("%d",&n); 
printf("请输入字符及对应权值:");
for(i=1;i<=n;i++)
{
printf(">>>");
scanf("%s",cha[i]);
scanf("%d",weight[i]);
}
huffman(tree,w,n); break; //生成huffman树
case '2':huffmancode(tree,code,n);break;
case '3':tohuffmancode(n);break;
case '4':decode(cha,tree,n);break;

}
}
}