d.cpp

这是一个数据结构常用的算法叫huffman编码.是对一棵二叉树进行huffman编码的算法

#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: 
   ; 
 }