hfm.cpp

数据结构清华大学出版社严蔚敏,吴为民编著的课后习题实验源代码

#include<stdio.h>   /* for size_t, printf()            */
#include<conio.h>   /* for getch()                     */
#include<ctype.h>   /* for tolower()                   */
#include<malloc.h>  /* for malloc(), calloc(), free()  */
#include<string.h>  /* for memmove(), strcpy()         */

/*树结构和全局结构指针*/
#define NODENUM 26

/*----------哈夫曼树结点结构-------------*/
struct node
  {
    char ch;
    int weight;
    int parent;
    int lchild,rchild;
    } *ht;   //指向哈夫曼树的存储空间的指针变量

/*----------字符编码结点结构-------------*/
struct HuffmanCoding
  { char ch;
    char coding[NODENUM];
    };

/*--------哈夫曼树遍历时栈的结点结构------*/
struct stacknode{
   int NodeLevel;
   int NodeElem;
   };

/*---------------常量文件名---------------*/
 const char *TableFileName  = "HfmTbl.txt";     //哈夫曼树数据文件
 const char *CodeFileName   = "CodeFile.txt";   //字符编码数据文件
 const char *SourceFileName = "SrcText.txt";    //需编码的字符串文件
 const char *EnCodeFileName = "EnCodeFile.txt"; //编码数据文件
 const char *DecodeFileName = "DecodeFile.txt"; //译码字符文件


/************************************************************/
/*               释放哈夫曼树数据空间函数                   */
/************************************************************/
 void free_ht()
 {
    if(ht != NULL)
      {
	free(ht);
	ht = NULL;
	}
    }

/************************************************************/
/*              从文件读取哈夫曼树数据函数                  */
/************************************************************/
int ReadFromFile()
{
    int i;
    int m;
    FILE *fp;

    if((fp=fopen(TableFileName,"rb"))==NULL)
    {
	printf("cannot open %s\n", TableFileName);
	getch();
	return 0;
    }
    fread(&m,sizeof(int),1,fp);  //m为数据个数
    free_ht();
    ht=(struct node *)malloc(m*sizeof(struct node));
    fread(ht,sizeof(struct node),m,fp);
    fclose(fp);
    return m;
    }
/************************************************************/
/*              吃掉无效的垃圾字符函数函数                  */
/*          从键盘读字符数据时使用，避免读到无效字符        */
/************************************************************/  
void EatCharsUntilNewLine()
{
    while(getchar()!='\n')
	continue;
}
/************************************************************/
/*              选择权值最小的两个根结点函数                */
/************************************************************/
void Select(struct node ht[],int n, int *s1,int *s2)
{ int i,j;
  //寻找第一个根结点
  *s1=0;
  while (*s1<=n&&ht[*s1].parent!=-1) ++(*s1);
  //寻找第一个权值最小的根结点
  i=(*s1)+1;
  while(i<=n)
    { if(ht[i].parent==-1&&ht[i].weight<ht[*s1].weight)  *s1=i;
      ++i;
      }
  //寻找第一个根结点，但不是第一个权值最小的根结点
   *s2=0;
   while(*s2<=n&&(ht[*s2].parent!=-1 || *s2==*s1)) ++(*s2);
   //寻找第二个权值最小的根结点
   j=*s2+1;
   while(j<=n)
    { if(j!=*s1&&ht[j].parent==-1&&ht[j].weight<ht[*s2].weight)  *s2=j;
      ++j;
      }
   return;
   }

/************************************************************/
/*               创建哈夫曼树和产生字符编码的函数           */
/************************************************************/
void Initialization()
 {
    int i=0,n,m,j,f,s1,s2,start;
    char cd[NODENUM];
    struct HuffmanCoding code[NODENUM];
    FILE *fp;

    printf("输入字符总数 n:");
    scanf("%d",&n);
    EatCharsUntilNewLine();

    m=2*n-1;
    ht=(struct node *)malloc(m*sizeof(struct node));//申请哈夫曼树的存储空间

   //输入字符和权值
    for(i=0;i<n;i++)
    {
	printf("\n请输入第%d个字符和权值:",i+1);
	scanf("%c%d",&ht[i].ch,&ht[i].weight);
	EatCharsUntilNewLine();
	ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
       }

 //初始化哈夫曼树
    for(i=n;i<m;i++)
     { ht[i].ch='*';
       ht[i].weight=0;
       ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
       }
  //建立哈夫曼树
    for(i=n;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;
       }

    //把哈夫曼树的数据存储到文件中
       if((fp=fopen(TableFileName,"wb"))==NULL)
	{
	  printf("cannot open %s\n", TableFileName);
	  getch();
	  return;
	  }
       fwrite(&m,sizeof(int),1,fp);
       fwrite(ht,sizeof(struct node),m,fp);
       fclose(fp);

     //产生字符编码
       cd[n-1]=0;
       for(i=0;i<n;i++)
	 { start=n-1;
	   for(j=i,f=ht[i].parent;f!=-1;j=f,f=ht[f].parent)
	     if(ht[f].lchild==j) cd[--start]='0';
	     else cd[--start]='1';
	   code[i].ch=ht[i].ch;
	   strcpy(code[i].coding,&cd[start]);
	   }
     //把字符编码数据存储到文件中
      if(!(fp=fopen(CodeFileName,"wb")))
	{
	  printf("cannot open %s\n", CodeFileName);
	  getch();
	  return;
	  }
      fwrite(&n,sizeof(int),1,fp);
      fwrite(code,sizeof(struct HuffmanCoding),n,fp);
      fclose(fp);
      free_ht();
      printf("\nInitial successfule!\n");
      getch();
   }

/************************************************************/
/*                       哈夫曼编码的函数                   */
/************************************************************/
void Encode(void)
{
    int i,j,n;
    char Encodestr[256];
    struct HuffmanCoding code[NODENUM];
    FILE *fp1, *fp2;
    
    //读字符编码数据
    if(!(fp1=fopen(CodeFileName,"rb")))
	{
	  printf("cannot open %s\n", CodeFileName);
	  getch();
	  return;
	  }
      fread(&n,sizeof(int),1,fp1);
      fread(code,sizeof(struct HuffmanCoding),n,fp1);
      fclose(fp1);
      
      //读需编码的字符串
      printf("输入编码字符串：");
      scanf("%s",Encodestr);

      //存储被编码的字符串数据到文件中
      if(!(fp1=fopen(SourceFileName,"wb")))
	{
	  printf("cannot open %s\n", SourceFileName);
	  getch();
	  return;
	  }
       fprintf(fp1,"%s\n",Encodestr);
       fclose(fp1);
       
       //打开存储编码的数据文件
       if((fp2=fopen(EnCodeFileName,"w"))==NULL)
	{
	  printf("cannot open %s\n", EnCodeFileName);
	  getch();
	  return;
	  }
       
       //字符编码
       i=0;
       while(Encodestr[i])
	{  
           for(j=0;j<n;j++)
	    if(code[j].ch==Encodestr[i])
	       { fprintf(fp2,"%s",code[j].coding);
		 printf("%s",code[j].coding);
		 i++;
		 break;
		 }
	    if(j==n)
	      {  printf("error charactor %c\n",Encodestr[i]);
		 getch();
		 fclose(fp2);
		 return;
		 }
	   }
       fclose(fp2);
   }
/************************************************************/
/*                       哈夫曼译码的函数                   */
/************************************************************/
void Decode()
{
    FILE *CFP, *TFP;
    char DeCodeStr[256];
    char ch;
    int f,m;
    
    //读哈夫曼树数据
    m=ReadFromFile();

    //打开编码数据文件
    if((CFP=fopen(EnCodeFileName,"r"))==NULL)
	{
	  printf("cannot open %s\n", EnCodeFileName);
	  getch();
	  return;
	  }
    //打开存放译码数据的文件
    if((TFP=fopen(DecodeFileName,"w"))==NULL)
	{
	  printf("cannot open %s\n", EnCodeFileName);
	  getch();
	  return;
	  }
    
    //译码--依次读入编码数字字符
    //从根结点开始，若是数字字符“0”，则沿其左分支下降，
    //              若是数字字符“1”，则沿其右分支下降
    // 直到页结点，则译出一个字符
    while(!feof(CFP))
    { f=m-1;
      while((!feof(CFP))&&ht[f].lchild!=-1)
       { ch=fgetc(CFP);
	 if(ch=='0')
	    f=ht[f].lchild;
	 else if(ch=='1')
	    f=ht[f].rchild;
	 }
       if(ht[f].lchild==-1&&ht[f].rchild==-1)
	{
	    fputc(ht[f].ch,TFP);
	    printf("%c",ht[f].ch);
	   }
	else if(feof(CFP)) break;
	else {
	   printf("Decode error\n");
	   getch();
	   break;
	   }
       }
    free_ht();
    fclose(CFP);
    fclose(TFP);
    printf("\n");
    getch();
}
/************************************************************/
/*               以凹式形式打印哈夫曼树的函数               */
/************************************************************/
void PrintHuffmanTree()
{ int i,node,child,level,m,top;
  struct stacknode stack[80];
  m=ReadFromFile();
  printf("\n%10c        Huffman TRee in Level\n",' ');
  printf("%10c--------------------------------------\n",' ');
  top=0;
  node=m-1;
  level=1;
  while((node!=-1)||(top!=0))
    {  while(node!=-1)
	  { for(i=1;i<20+2*level;i++) printf(" ");
	    printf("%d-%d %c\n",level,ht[node].weight,ht[node].ch);
	    if(ht[node].rchild!=-1)
	       { stack[top].NodeElem=ht[node].rchild;
		 stack[top].NodeLevel=level+1;
		 top++;
		}
	    node=ht[node].lchild;
	    if(node!=-1) level++;
	    }
	if(top!=0)
	  { top--;
	    node=stack[top].NodeElem;
	    level=stack[top].NodeLevel;
	    }
       }
    
    getch();
   }
/************************************************************/
/*                 打印哈夫曼字符编码的函数                 */
/************************************************************/
void PrintCharCoding()
 { int i,n;
   struct HuffmanCoding code[NODENUM];
   FILE *fp;
   if(!(fp=fopen(CodeFileName,"rb")))
	{
	  printf("cannot open %s\n", CodeFileName);
	  getch();
	  return;
	  }
      fread(&n,sizeof(int),1,fp);
      fread(code,sizeof(struct HuffmanCoding),n,fp);
      fclose(fp);

       printf("%18cchar    coding\n",' ');
       for(i=0;i<n;i++)
	  printf("%20c	   %s\n",code[i].ch,code[i].coding);
      getch();
   }
/************************************************************/
/*               以表的形式打印哈夫曼树的函数               */
/************************************************************/
void PrintHuffmanTable()
 { int i,m;
   FILE *fp;

   if((fp=fopen(TableFileName,"rb"))==NULL)
	{
	  printf("cannot open %s\n", TableFileName);
	  getch();
	  return;
	  }
       fread(&m,sizeof(int),1,fp);
       ht=(struct node *)malloc(m*sizeof(struct node));
       fread(ht,sizeof(struct node),m,fp);
       fclose(fp);
       /*输出哈夫曼树*/
       printf("\n%25cThe huffman Table\n",' ');
       printf("%8c-------------------------------------------------\n",' ');
       printf("%8cnumber character  weight   parent  lchild rchild\n",' ');
       for(i=0;i<m;i++)
	 printf("%10d%10c%9d%9d%9d%9d\n",i,ht[i].ch,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
       getch();
       free_ht();
   }
 int nemu()
{
    int num;
    printf("\n    ******* huffman arithmetic demonstration *********\n");
    printf("    *%15c1---Initial%23c\n",' ','*');
    printf("    *%15c2---Encode%24c\n",' ','*');
    printf("    *%15c3---Decode%24c\n",' ','*');
    printf("    *%15c4---Print huffmantree%13c\n",' ','*');
    printf("    *%15c5---Print huffman Table%11c\n",' ','*');
    printf("    *%15c6---Print char Coding%13c\n",' ','*');
    printf("    *%15c7---Quit%26c\n",' ','*');
    printf("    **************************************************\n");
    printf("%15cSelcet 1,2,3,4,5,6,7: ",' ');
    do{
	scanf("%d",&num);
	}while(num<1 ||num>7);
    return(num);
}

void main()
{
    while(1)
    {
	switch(nemu())
	{
	    case 1:
		Initialization();
		break;
	    case 2:
		Encode();
		break;
	    case 3:
		Decode();
		break;
	    case 4:PrintHuffmanTree();
		break;
	    case 5:PrintHuffmanTable();
		break;
	    case 6:PrintCharCoding();
		break;
	    case 7:
		free_ht();
                return;
        }
    }
}