hafuman.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()
{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:");
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);
}