网上答案4.txt

这是一个实现哈夫曼编码的代码

#include<stdio.h> 
#include<malloc.h> 
#include<string.h> 
#include<stdlib.h> 
typedef struct 
{ 
int weight; 
char ch; 
int parent,lchild,rchild; 
}HTNode,*HuffmanTree; 
typedef struct 
{ 
char ch; 
char *chs; 
}HuffmanCode; 
typedef struct 
{ 
char ch; 
int weight; 
}sw; 
typedef struct 
{ 
HuffmanTree HT; 
HuffmanCode *HC; 
}huf; 
void select(HTNode * HT,int n,int *n1,int *n2) 
{ 
int i=1; int n3; 
while(HT[i].parent!=0) 
i++; 
*n1=i; 
i++; 
while(HT[i].parent!=0) i++; 
*n2=i; 
if(HT[*n1].weight<HT[*n2].weight) 
{ n3=*n1;*n1=*n2;*n2=n3;} 
for(i++;i<=n;i++) 
{ 
if(HT[i].parent==0) 
{ if(HT[i].weight<HT[*n1].weight) 
*n1=i; 
else if(HT[i].weight<HT[*n2].weight) 
*n2=i; 
} 
} 
} 

huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF) 
{int m,i,s1,s2,start,c,f; 
HuffmanTree p; 
char *cd; 

if(n<=1) return 0; 
m=2*n-1; 
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
for(p=HT+1,i=1;i<=n;i++,p++,w++) 
{p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;} 
for(;i<=m;i++,p++) 
{p->weight=0;p->ch='^';p->parent=0;p->lchild=0;p->rchild=0;} 
for(i=n+1;i<=m;i++) 
{ 
select(HT,i-1,&s1,&s2); 
HT[s1].parent=i;HT[s2].parent=i; 
HT[i].lchild=s1;HT[i].rchild=s2; 
HT[i].weight=HT[s1].weight+HT[s2].weight; 
} 
HC=(HuffmanCode *)malloc((n+1)*sizeof(char)); 
cd=(char *)malloc(n*sizeof(char)); 
cd[n-1]='\0'; 
for(i=1;i<=n;i++) 
{ start=n-1; 
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) 
if(HT[f].lchild==c)cd[--start]='0'; 
else cd[--start]='1'; 
HC[i].ch=HT[i].ch; 
HC[i].chs=(char*)malloc((n-start)*sizeof(char)); 
strcpy(HC[i].chs,&cd[start]); 
printf("%c %-10s\n",HC[i].ch,HC[i].chs); 
} 

HUF->HT=HT; 
HUF->HC=HC; 
return HUF; 
} 
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n) 
{ 
char *p=chars; int i; 
strcpy(chars1,""); 

while(*p) 
{ 
i=1; while(hc[i].ch!=*p&&i<=n) i++; 
strcat(chars1,hc[i].chs); p++; 
} 

printf("the chars translate are:%s\n",chars1); 
return chars1; 
} 
void transcode(HuffmanTree ht,char *chars2,char*chars3) 
{ 
int i=1,p; char *q=chars2;char *r=chars3; 

while(ht[i].parent!=0) i++; 
p=i; 

while(*q) 
{ 
while(ht[p].lchild!=0 && *q) 
{ 
if(*q=='0') 
p=ht[p].lchild; 
else p=ht[p].rchild; 
q++; 
} 
if(ht[p].lchild==0) 
{*r=ht[p].ch;r++;} 
p=i; 

} 

*r='\0'; 
printf("the chars are:"); 
puts(chars3); 

} 


void input(int *n,sw *w) 
{ 
int i; 
printf("input the mount of char:"); 
scanf("%d",n); 

for(i=1;i<=*n;i++,w++) 
{printf("input the %dth char and weight:",i); 
fflush(stdin); 
scanf("%c%d",&w->ch,&w->weight); 
} 

} 
void main(void) 
{HTNode HT; 
HuffmanCode HC,*hc; 
HuffmanTree ht; 
huf *HUF,huf2; 
int n; 
sw w[40]; 
char ch,inchar[500],outchar[1000]; 
char *abc; 
char *p=inchar; 
input(&n,w); 
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2); 
printf("input chars to translate,ends of '#':"); 
fflush(stdin);//清除流,解决输入干扰 
ch=getchar(); 
while(ch!='#') 
{*p=ch; 
p++; 
ch=getchar(); 
} 
*p='\0'; 
hc=HUF->HC; 
ht=HUF->HT; 
abc=convert(inchar,outchar,hc,n); 
transcode(ht,abc,outchar); 
}