/* ============== Program Description ============= */
/* Freshare's 5th of dswork */
/* ================================================== */
#include"stdio.h"
#include"string.h"
#define MAX 99
char cha[MAX],str[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;
for (i=1;i<=k;i++)
if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;
for (i=1; i<=k ; i++)
if (tree[i].parent==0 && i!=s1) break; s2=i;
for (i=1;i<=k;i++)
if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;
}
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[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)
{
int start,c,i,f;
code[n-1]='/0';
printf("/nHuffman Code:/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)
{if(tree[f].lchild==c)code[--start]='0';
else code[--start]='1';}
strcpy(hc[i],&code[start]);
printf(" %c --> %s/n",cha[i],hc[i]);
}
}
void tohuffmancode(int n)
{
int i=0,j;
printf("/nHuffman Code of the Sentence:/n>>> ");
for (;str[i]!='/0';i++)
{
j=0;
for(;str[i]!=cha[j]&&j<=n;) j++;
if (j<=n) printf("%s",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("please enter the code:/n>>> ");
scanf("%c",&b);
printf("Decode:");
while(b!=10) //遇到回车时，结束
{
if(b=='0')i=tree[i].lchild;
else i=tree[i].rchild;
if(tree[i].lchild==0)
{printf("%c",ch[i]);
j=i,i=m;
}
scanf("%c",&b);
}
if(tree[j].lchild!=0)
printf("/nERROR/n");
printf("/n/n");
}
void main()
{
int i=0,j=1,n;
int *w,weight[MAX],st[199]={0};
char code[MAX],ch;
huftree tree[MAX];
w=weight;
printf("Please enter a sentence:/n>>>");
gets(str);
for(;str[i]!='/0';i++) st[str[i]]++;
i=0;
for(;i<=199;i++) if (st[i]!=0) { cha[j]=i,weight[j]=st[i];j++;}
i=1;
for (n=j-2;i<j-1;i++) printf("%c --> %d /t",cha[i],weight[i]);
printf("/n");
huffman(tree,w,n); //生成huffman树
huffmancode(tree,code,n); //编码A
tohuffmancode(n); //编码B
decode(cha,tree,n); //译码
}