数据结构（C）实验：哈夫曼编码和译码（附完整代码配套严蔚敏版教材）

1.实验内容

（1）输入一段100—200字的英文短文，存入一文件a中。
（2）写函数统计短文出现的字母个数n及每个字母的出现次数
（3）写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。
（4）用每个字母编码对原短文进行编码，码文存入文件b中。
（5）用Haffman树对文件b中码文进行译码，结果存入文件c中，比较a,c是否一致，以检验编码、译码的正确性。

2.构造哈夫曼树的步骤

注意：
这种建树的方法只适用于进行哈夫曼编码，因为两个互为兄弟的叶子节点之间并无关系，而对于后面排序要讲到的判定树（不等概率查找）时，想要建立一个最优二叉树的代价是巨大的，所以我们用次优二叉树来代替最优二叉树。
比如
这是一个判定树，它不是按照哈夫曼编码建树的规则建立，但是它确确实实是一棵哈夫曼树（最优二叉树），小编在这里就是想提醒一下大家不要把这种算法当成建立哈夫曼树的独一无二的方法。

3，完整代码（配套教材严蔚敏版）

注意：在你运行时，会自动创建“article.txt”和“barticle.txt”,前者用来存放输入的字符数据，后者用来存放该文段的哈夫曼编码，都以#结束，默认的译码函数是从“barticle.txt”文件中译码，也可以自己设置从其他文件中读取，但译码之前确保已经建成相应的哈夫曼树（即已经确定好每个字符的编码）。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define maxnumber 10000000
typedef  struct art
{
    char*  code;
	char letter;
	int   num;
}ART,*INK;
typedef  struct
{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

void PutArticle()
{
	FILE*fp;
	char ch='0';
	if ((fp=fopen("article.txt","w"))==NULL)//打开文件，不存在此文件则新建
	{
      fp=fopen("article.txt","w");
    }
      printf("请属于一段英文段落以#结束\n");
      while(ch!='#')
      {
	   ch=getchar();
	   fputc(ch,fp);
	  }
	  fclose(fp);
}
	
int SearchArticle(INK &p,int &n)
{
	FILE *fp;
	int i,k;
	char *INK,ch='0';
    if ((fp=fopen("article.txt","r"))==NULL)//打开文件
       {
           printf("\n记录文件不存在!");
		   exit(0);
       }
	while(ch!='#')
	{   
		ch=fgetc(fp);
		if(ch>=65&&ch<=90||ch>=97&&ch<=122)
		{  
		 	for( i=0,k=0;i<=n;i++)
		 	{
		 		if(ch==p[i].letter)
				 {
		 		     p[i].num++;
		 		     k=1;
			     }
		   }
		   if(k==0)
	      {
		       p[n].letter=ch;
	           p[n].num=1;
               n++;
				     
          }
        }
    }fclose(fp);
return 0;
}

int *CreatW(int n,INK p)
{
	int  *w=(int  *)malloc((n)*sizeof(int));
	for(int i=0;i<n;i++)
	{
		w[i]=p[i].num;
		
	}
	return w;
}

void select(HTNode*HT,int n,int&s1,int&s2)
{
	int min=maxnumber; int min2=maxnumber+1;
	int p,q;
   
	for(int i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
      {

		if(HT[i].weight<=min&&HT[i].weight<min2)
		  { min2=min; min=HT[i].weight;
		     q=p; p=i;              }
		if(HT[i].weight<min2&&HT[i].weight>min)
          { min2=HT[i].weight;
		    q=i;                }
	
      }
	}
	s1=p;

	s2=q;
}


void HuffmanCreat(HuffmanTree &HT,HuffmanCode &HC,int*w,int n)
{
	if(n<=1) return;
	int m=2*n-1,s1=0,s2=0;
	int i;
	HTNode *p;
	HT=(HTNode *)malloc((m+1)*sizeof(HTNode));//因为为了号码方便，第0号不用
	p=HT;
    for( i=1;i<=n;++i)
	  p[i]={w[i-1],0,0,0};//为n个叶子节点赋初值，顺序刚好和字母排列的顺序相同也就是w里面的顺序
    for(;i<=m;++i)
	  p[i]={0,0,0,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*));//创建一个指针数组，每个元素为数组指针指向一个字符串，同理数组长度为n+1
   char *cd=(char*)malloc(n*sizeof(char));//创建一个数组指针，长度为n,因为有n个被编码的叶子就有n-1层，就最多需要n-1位二进制，但是为了保证每串字符能有结尾的标识符所以长度设为了n
   cd[n-1]='\0';//字符串结尾标志
   for(int i=1; i<=n; ++i)
   {
      int start = n-1;//编码中的倒数第二位
     for(int 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]=(char*) malloc((n-start)*sizeof(char));//1.防止浪费过多空间2.编码中没有赋值的不用输出
      strcpy(HC[i], &cd[start]);
  }
   free(cd);//动态存储记得free
}

void CodeArticle(char *a,int n,INK p)
{
   
	FILE *fp1,*fp2;
	int i;
	fp1=fopen("article.txt","r");
	 if ((fp2=fopen("barticle.txt","w"))==NULL)
	{fp2=fopen("barticle.txt","w");}
	char ch=fgetc(fp1);
	while(ch!='#')
	{
	    for( i=0;i<n;i++)
		  if(ch==p[i].letter)
		    break;
		if(i<n) {
		fprintf(fp2,"%s",p[i].code);
       }
		else    {fputc(ch,fp2);}
		ch=fgetc(fp1);
	}
	fputc('#',fp2);
	fclose(fp1);
	fclose(fp2);
}

void TransCode(HuffmanTree HT,int n,INK p)//依次读入电文，根据哈夫曼树译码
{
	printf("\n译码结果如下\n");
	char ch;
	int i=2*n-1;//从根节点开始往下搜索
	FILE *fp=fopen("barticle.txt","r");
	ch=fgetc(fp);
   while(ch!='#')
 {
  if(ch!='0'&&ch!='1')
	printf("%c",ch);
  if(ch=='0')
   i=HT[i].lchild;   //走向左孩子
  else if(ch=='1')
   i=HT[i].rchild;   //走向右孩子
  if(HT[i].lchild==0&&HT[i].lchild==0)     //tree[i]是叶结点
  {
   printf("%c",p[i-1].letter);
   i=n*2-1;      //回到根结点
  }
    ch=fgetc(fp);
  }
 printf("\n");
 if(i!=n*2-1&&ch=='#')   //电文读完，但尚未到叶子结点
  printf("\nERROR\n");  //输入电文有错
  fclose(fp);
}//decode

int main()
{
	INK p=(INK)malloc(52*sizeof(ART));
	int n1=0;
	PutArticle();
    SearchArticle(p,n1);
    
	printf("\n总个数:%d\n",n1);
	HuffmanTree HT;
	HuffmanCode HC;
	int s1,s2;
	int *w=CreatW(n1,p);
	FILE*fp2;
	HuffmanCreat(HT,HC,w,n1);
	printf("字母   权值    编码\n");
	for(int i=0;i<n1;i++)
	{

    printf("%c\t",p[i].letter);
    printf("%d\t",p[i].num);
 	p[i].code=HC[i+1];
    printf("%s\n",p[i].code);
    }





    CodeArticle("article.txt", n1, p);
    TransCode(HT, n1, p);
    
    free(HT);
    free(HC);
    free(w);system("pause");
	return 0;


}

//遇到调试过程中的断点，尤其是在malloc,一定要往前找，肯定之前的malloc出错1了

结果展示