bian.cpp

哈夫曼编码的算法编辑文件

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<conio.h>
//#include<graphics.h>
#define n 26

void main()
{
int i,wt,child,start;
unsigned int f,c;
char ch;
char *cd,*str;
typedef char * *Huffmancode;
Huffmancode HC;
typedef struct
{unsigned int w;
  unsigned int pt,lc,rc;
  }HTN;
  HTN *p,*h;
//  clrscr();
  h=p=(HTN *)malloc(2*n*sizeof(HTN));
  printf("Please input the weigth of a,b,******.\n");
  for(i=1;i<=n;i++,p++)
  {scanf("%u",&p->w);
   p->pt=p->lc=p->rc=0;
   }
   for(;i<=2*n-1;i++,p++)
   p->w=p->pt=p->lc=p->rc=0;
  // printf("After initiate the huffman tree is:\n");
  // for(i=1,p=h;i<=2*n-1;i++,p++)
  // printf("%u  %u  %u  %u\n",p->w,p->pt,p->lc,p->rc);



   for(i=n+1;i<=2*n-1;i++)
   {for(p=h;p-h+1<i;p++)
    if(p->pt==0)
    {wt=p->w;
     child=p-h+1;
     break;
    }
    for(p=h;p-h+1<i;p++)
    {
     if(p->pt==0)
     if(p->w<wt)
    {wt=p->w;
     child=p-h+1;
     }
    }
    (h+i-1)->w=wt;
    (h+i-1)->lc=child;
    (h+child-1)->pt=i;


    for(p=h;p-h+1<i;p++)
    if(p->pt==0)
     {wt=p->w;
      child=p-h+1;
      break;
      }
    for(p=h;p-h+1<i;p++)
    if(p->pt==0)
    if(p->w<wt)
    { wt=p->w;
      child=p-h+1;
      }
     ((h+i-1)->w)+=wt;
     (h+i-1)->rc=child;
     (h+child-1)->pt=i;
     }
   //  printf("After building the tree it is:\n");
   //  for(i=1,p=h;i<=2*n-1;i++,p++)
   //  printf("%u   %u   %u  %u\n",p->w,p->pt,p->lc,p->rc);



     HC=(Huffmancode)malloc((n+1)*sizeof(char *));
     cd=(char *)malloc(n*sizeof(char));
     cd[n-1]='\0';
     for(i=1,p=h;i<=n;i++,p++)
     {start=n-1;
      for(c=i,f=p->pt;f!=0;c=f,f=(p+f-i)->pt)
      if((p+f-i)->lc==c)
      cd[--start]='0';
      else
      cd[--start]='1';

      HC[i]=(char *)malloc((n-start)*sizeof(char));
      strcpy(HC[i],&cd[start]);
      }
      free(cd);
      printf("The haffmancode is:\n");
      for(i=1;i<=n;i++)
      printf("%c: %s ",i+96,HC[i]);

loop0:printf("\nPlease input any key except 'n'to continue.\n");
      if(getch()=='n')
     {free(HC);
      free(h);
      free(str);
      exit(1);
      }


     printf("\nPlease input a string.\n");
     str=(char*)malloc(20*sizeof(char));
    if(!str)
    exit (1);
    *str='\0';
   loop1: ch=getch();
    if(('a'<=ch)&&(ch<='z'))
    {putch(ch);
     strcat(str,HC[ch-97+1]);
     goto loop1;
     }
     if(ch==' ')
     {putch(ch);
      goto loop1;
      }
     printf("\nThe code of the string is:%s\n",str);



   loop2:if(strlen(str)!=0)
     for(i=1;i<=n;i++)
     if(strstr(str,HC[i])==str)
     {printf("%c",96+i);
      str=str+strlen(HC[i]);
      goto loop2;
      }
      goto loop0;
      }