hfmmodel.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));//申请哈夫曼树的存储空间

    /********************************************************/   
    /*                   创建哈夫曼树                       */
    /*     1、输入字符和权值                                */
    /*     2、初始化哈夫曼树                                */
    /*     3、建立哈夫曼树                                  */
    /********************************************************/
     

    //把哈夫曼树的数据存储到文件中
       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);

    /*********************************************************/   
    /*                   产生字符编码                        */
    /*     从页结点开始，沿父结点上升，直到根结点 ，若沿     */
    /*  父结点的左分支上升，则得编码字符“0”， 若沿父结     */
    /*  点的右分支上升，则得编码字符“1”                    */
    /*********************************************************/
       
     //把字符编码数据存储到文件中
      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;
    
    /********************************************************/   
    /*                   字符编码                           */
    /*     1、读字符编码数据                                */
    /*     2、读需编码的字符串                              */
    /*     3、存储被编码的字符串数据到文件中                */
    /*     4、打开存储编码的数据文件                        */
    /*     5、字符编码                                      */
    /*        方法：依次从被编码的字符串中取一个字符，然后  */
    /*          字符编码表中查找对应字符，若找到，则把对应  */
    /*          的编码输出到编码数据文件中。                */
    /********************************************************/

   }
/************************************************************/
/*                       哈夫曼译码的函数                   */
/************************************************************/
void Decode()
{
    FILE *CFP, *TFP;
    char DeCodeStr[256];
    char ch;
    int f,m;
    
    /********************************************************/   
    /*                   字符译码                           */
    /*  1、读哈夫曼树数据                                   */
    /*  2、打开编码数据文件                                 */
    /*  3、打开存储译码的数据文件                           */
    /*  4、字符译码                                         */
    /*     方法：依次从编码数据文件中读取编码字符，并从     */
    /*       哈夫曼树开始，若是数字字符“0”，则沿其左分    */
    /*       支下降到孩子结点；若是数字字符“1”，则沿其    */
    /*       右分支下降到孩子结点；如此反复，直到页结点，   */
    /*       则输出页结点对应的字符到译码数据文件中，并     */
    /*       显式。每当译出一个字符，又从页结点开始，如     */
    /*       此重复若找到，直到读完编码数据文件中所有字符。 */
    /********************************************************/
    
    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;
    /********************************************************/   
    /*                   打印字符编码                       */
    /*     1、读字符编码数据                                */
    /*     2、打印字符编码数据                              */
    /*        格式：                                        */
    /*                 charactor coding                     */
    /*              ------------------------                */
    /*               charactor       coding                 */
    /*                                                      */
    /*                                                      */
    /********************************************************/
   }
/************************************************************/
/*               以表的形式打印哈夫曼树的函数               */
/************************************************************/
void PrintHuffmanTable()
 { int i,m;
   FILE *fp;

    /************************************************************/   
    /*                   打印字符编码                           */
    /*     1、读哈夫曼树数据                                    */
    /*     2、打印哈夫曼树数据                                  */
    /*        格式：                                            */
    /*                      Huffman  Table                      */
    /*     ------------------------------------------------     */
    /*     Number charactor weight  Parent  Lchild  Rchild      */
    /*                                                          */
    /*                                                          */
    /************************************************************/  

     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;
        }
    }
}