/*huffman coder & decoder*/
include<stdio.h>
#ifndef N
#define N 27
#endif
#define M (2*N-1)
#define Max (100*N)
#define Min 5
/*define each node's imformation*/
typedef struct nodetype
{
int weight ;
int lch;
int rch;
int parent;
char data;
}node;
/*structure code*/
typedef struct codetype
{
int bits[N];/*0,1*/
int start;/*1..n*/
}code;
/*assistant variable*/
typedef struct sign
{
int wt;
int num;
}tag;
/*typedef node huftree;
typedef code hufcode;*/
/*create huftree*/
void Create(struct nodetype ht0[],struct codetype hcd0[])
{
int h,i,j,l,k;
int wt;
int c1,sgn=0,r=1;
char chr;
tag flag[M];
tag md;
code cd;
for(i=1;i<=M;i++)
{
ht0[i-1].parent=0;
ht0[i-1].lch=ht0[i-1].rch=0;
}
for(i=1;i<=N;i++)
{
getchar();
printf("\n\t\t请输入第%d个数",i);
printf("\n\t\t请输入数据信息：字符--");
chr=getchar();
if(((chr>='a')&&(chr<='z'))||((chr>='A')&&(chr<='Z')))
ht0[i-1].data=chr;
else
{
printf("\n\t\t太不小心了吧！Again!AgainAgain!!");
i++;
continue;
}
printf("\n\t\t请输入数据信息：权重--");
scanf("%d",&wt);
ht0[i-1].weight=wt;
}
printf("\n\t\t辛苦了:).上帝是仁慈的，瞧!有结果了.仰天长笑吧！哈－哈哈!");
for(i=N+1;i<=M;i++)
{
for(k=1,j=0;k<=i-1;k++)
if(ht0[k-1].parent==0)
{
j++;
flag[j-1].wt=ht0[k-1].weight;
flag[j-1].num=k;
}
for(l=1;l<j;l++)
{
for(h=l+1;h<=j;h++)
if(flag[l-1].wt>flag[h-1].wt)
{
md=flag[l-1];
flag[l-1]=flag[h-1];
flag[h-1]=md;
}
}
ht0[flag[1-1].num-1].parent=i;
ht0[flag[2-1].num-1].parent=i;
ht0[i-1].lch=flag[1-1].num;
ht0[i-1].rch=flag[2-1].num;
ht0[i-1].weight=ht0[flag[1-1].num-1].weight+ht0[flag[2-1].num-1].weight;
}
/**/
for(i=0;i<=N;i++)
cd.bits[i-1]=0;
for(r=1;r<=N;r++)
{
cd.start=N;
c1=r;
sgn=ht0[c1-1].parent;
while(sgn)
{
if(ht0[sgn-1].lch==c1)
cd.bits[cd.start-1]=0;
else if(ht0[sgn-1].rch==c1)
cd.bits[cd.start-1]=1;
cd.start--;
c1=sgn;
sgn=ht0[sgn-1].parent;
}
hcd0[r-1]=cd;
}
}
/**/
void Table(struct nodetype ht[],struct codetype hcd[])
{
int i,j;
Create(ht,hcd);
for(i=1;i<=N;i++)
{
printf("\n%c\t",ht[i-1].data);
for(j=hcd[i-1].start+1;j<=N;j++)
{
printf("%d",hcd[i-1].bits[j-1]);
}
}
}
/**/
void Coding(node ht2[],code hcd2[])
{
char str1[Max];
int h,i,j,k=0;
Create(ht2,hcd2);
printf("\n\t请输入正文:\n");
for(h=0;(str1[h]=getchar())!='#';h++);/*great!!!!!!!!!!!!*/
while(str1[k]!=0)
{
for(i=1;i<=N;i++)
if(ht2[i-1].data==str1[k])
for(j=hcd2[i-1].start+1;j<=N;j++)
printf("%d",hcd2[i-1].bits[j-1]);
k++;
}
printf("\n\t\t哇塞!太幸福了.");
}
/**/
void Decoding(node ht3[],code hcd3[])
{
char *str2=" ";
node q;
Create(ht3,hcd3);
printf("\t\t请输入编码:\n");
scanf("%s",str2);
while(*str2)
{
q=ht3[M-1];
while(q.lch!=0)
{
if(*str2=='0')
{
q=ht3[q.lch-1];
str2++;
}
else if (*str2=='1')
{
q=ht3[q.rch-1];
str2++;
}
}
printf("%c",q.data);
}
printf("\n\t\t呼呼!看不懂得01真的很浪漫哟:)");
}
/**/
void main()
{
char ctrl,ctrl1,ctrl2;
int i=0;
node ht1[M];
code hcd1[N];
do
{
printf("\n\t\t欢迎你来到哈夫曼王国!!\n\t\t该系统具有以下功能：\n\t\t(1)：建立哈夫曼编码树\n\t\t(2):输出编码表\n\t\t(3):编码\n\t\t(4):译码\n\t\t(0):退出。再见!!!!\n\t\t选择 :--|0|1|2|3|4|\n\t\t可实现你的要求:--");
i++;
scanf("%c",&ctrl);
scanf("%c",&ctrl2);
if(ctrl=='1')
Create(ht1,hcd1);
else if(ctrl=='2')
Table(ht1,hcd1);
else if(ctrl=='3')
Coding(ht1,hcd1);
else if(ctrl=='4')
Decoding(ht1,hcd1);
else if(ctrl=='0')
goto loop;
else if(Min-i>0)
{
printf("\n\t哈哈!你错了哟!看一看提示吧：)\n\t要珍惜机会哦!!\n\t\tp(^_^)q\n");
}
if ((Min-i)==0)
printf("\n\t欢迎再来!\n\tBye,HAVE A GOOD DAY!\n\t\t\t ");
else
{
printf("\n\t\t只有%d次机会了",Min-i);
printf("\n\t\t还要继续吗？加油喔:)\n\n\t\t\t\ty|n");
printf("\n\n\t\t\t\t");
scanf("%c",&ctrl1);
}
getchar();/*waiting*/
}while((ctrl1=='y')&&(i<=Min-1));
loop:
;
}
