ywf.txt

哈夫曼编/译码器

#define MAX_INIT_TREE 100
#define OK 1
#define ERROR 0
#define SCREENWIDTH 40
#define SCREENHEIGHT 40
#define MAX_FILENAME 20
#include<stdio.h>
typedef struct HTNode
{
 char character;
 int weight;
 int parent,lchild,rchild;
}HTNode,*HuffmanTree;
HuffmanTree HT;
void FillTree(int n)
{
 int i,weight,go,j;
 char ch;
 printf("There are %d TreeNodes requere!\nInput the 1 node!\n",n);
 printf("ch\n");
 scanf("%c",&ch);
 getchar();
 printf("weight\n");
 scanf("%d",&weight);
 getchar();
 HT[1].character=ch;
 HT[1].weight=weight;
 for(i=2;i<=n;)
 {
  go=OK;
  printf("There are %d TreeNodes requere!\nInput the %d node!\n",n,i);
  printf("ch\n");
  scanf("%c",&ch);
  getchar();
  printf("weight\n");
  scanf("%d",&weight);
  getchar();
  for(j=1;j<i;j++)
   if(HT[j].character==ch){
    printf("ERROR!\nHT[%d] is the same number!\nPlease reinput!\n",j);
    go=ERROR;
    break;
   }
  if(go){
   HT[i].character=ch;
   HT[i].weight=weight;
   i++;
  }
 }
}
void Select(int num,int *s1,int *s2){
 int i,num0,num1,num2;
 for(i=1;i<num;i++)if(!(HT[i].parent)){num1=i++;break;}
 for(;i<num;i++)if(!(HT[i].parent)){num2=i++;break;}
 if(HT[num1].weight>HT[num2].weight){
  num0=num1;num1=num2;num2=num0;
 }
 for(;i<num;i++){
  if(HT[i].weight<HT[num2].weight&&!(HT[i].parent))
   if(HT[i].weight<HT[num1].weight){
    num2=num1;num1=i;
   }else num2=i;
 }
 *s1=num1;*s2=num2;
}
int PrintFile(char *filename){
 FILE *fp;
 char ch;
 int i;
 printf("file:\t%s\n\n",filename);
 if(!(fp=fopen(filename,"r"))){
  printf("file %s is not exist!\n",filename);
  return ERROR;
 }
 while(!feof(fp))putchar(fgetc(fp));
 putchar('\n');
 fclose(fp);
 return OK;
}
int CreateHFTree(int *treenodes){
 int n,i,m,s1,s2;
 char ch;
 m=treenodes;
 printf("Tree has how many nodes?\n");
 scanf("%d",&n);getchar();
 if(n<=1||n>MAX_INIT_TREE){printf("Input ERROR!\n");return ERROR;}
 m=2*n;
 if(!(HT=(HuffmanTree)malloc(m*sizeof(HTNode))))printf("ERROR\n!");
 for(i=0;i<m;i++){
  HT[i].parent=0;
  HT[i].lchild=0;
  HT[i].rchild=0;
 }
 FillTree(n);
 for(i=n+1;i<m;i++){
  Select(i,&s1,&s2);
  HT[i].lchild=s1;
  HT[i].rchild=s2;
  HT[s1].parent=HT[s2].parent=i;
  HT[i].weight=HT[s1].weight+HT[s2].weight;
  HT[i].character='\0';
 }
 *treenodes=n+1;
 return OK;
}
void ClearScreen(){
 int i;
 for(i=0;i<SCREENHEIGHT;i++)putchar('\n');
 putchar('\n');
}
void HR(){
 int i;
 for(i=0;i<SCREENWIDTH;i++)putchar('=');
 putchar('\n');
}
int InCode(char *infile,int treenodes,char *outfile){
 FILE *in,*out;
 char ch,c[MAX_INIT_TREE];
 int self,parent,start,i;
 if(!(in=fopen(infile,"r"))){
  printf("file %s is not exist!\n",infile);
  return ERROR;
 }
 if(!(out=fopen(outfile,"w"))){
  printf("open file %s ERROR!\n",outfile);
  return ERROR;
 }
 while(!feof(in)){
  ch=fgetc(in);
  for(i=1;i<=treenodes;i++)
   if(ch==HT[i].character){
    start=MAX_INIT_TREE;
    c[--start]='\0';
    self=i;parent=HT[self].parent;
    while(parent){
     c[--start]=(HT[parent].lchild==self)?'0':'1';
     self=parent;
     parent=HT[self].parent;
    }
    while(start<MAX_INIT_TREE)fputc(c[start++],out);
    break;
   }
  if(i>=treenodes)printf("%c is not found in HuffmanTree!\n",ch);
 }
 fclose(in);
 fclose(out);
 return OK;
}
int OutCode(char *infile,int treenodes,char *outfile)
{
 FILE *in,*out;
 int self,child;
 char ch;
 if(!(in=fopen(infile,"r")))
 {
  printf("can not open file %s!\n",infile);
  return ERROR;
 }
 if(!(out=fopen(outfile,"w")))
 {
  printf("can not open file %s!\n",outfile);
  return ERROR;
 }
 while(!feof(in))
 {
  ch=fgetc(in);
  self=2*treenodes-3;
  if('0'==ch)child=HT[self].lchild;
  else child=HT[self].rchild;
  while(child)
  {
   self=child;
   child=('0'==fgetc(in))?HT[self].lchild:HT[self].rchild;
  }
  fputc(HT[self].character,out);
 }
 return OK;
}
void PrintTree(int root,int n){
 int i;
 getch();
 printf("[%c](%d)----",HT[root].character,HT[root].weight);
 if(HT[root].rchild)PrintTree(HT[root].rchild,n+1);
 else printf("NULL\n");
 for(i=0;i<=n;i++)printf("|          ");
 printf("\n");
 for(i=0;i<n;i++)printf("|          ");
 if(HT[root].lchild)PrintTree(HT[root].lchild,n);
 else printf("NULL\n");
}
main()
{
 char initfile[]={"D:\\stextfil.txt"},midfile[]={"D:\\codefile.txt"},lastfile[]={"D:\\textfile.txt"};
 int treenodes;
 ClearScreen();
 CreateHFTree(&treenodes);
 HR();getch();
 printf("The following is the tree you just inputed!\n\n");
 PrintTree(2*treenodes-3,0);HR();getch();
 PrintFile(initfile);HR();getch();
 InCode(initfile,treenodes,midfile);HR();
 PrintFile(midfile);HR();getch();
 OutCode(midfile,treenodes,lastfile);HR();getch();
 PrintFile(lastfile);HR();getch();
 printf("Now!OK!\n");
}