huffman.cpp

关于哈弗曼树的编码译码

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define CL 16          //编码的长度
#define NULL 0
#define N 50          //用于存储基本字符集的字符数组的长度
#define TL 50         //电文长度
typedef struct
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
	char date;
}HTNode,*HuffmanTree;
typedef char**HuffmanCode;

void Select(HuffmanTree &HT,unsigned n,int&s1,int&s2)
{// 在HT[1..i-1]中选择parent为0且weight最小的两个结点
	int min=-1;
	for(unsigned i=1;i<=n;i++)
	{
		if(min<0&&HT[i].parent==0){min=HT[i].weight;s1=i;}
		else if(min>HT[i].weight&&HT[i].parent==0){min=HT[i].weight;s1=i;}
	}
	min=-1;
	for(unsigned j=1;j<=n;j++)
	{
		if(min<0&&HT[j].parent==0&&j!=s1){min=HT[j].weight;s2=j;}
		else if(min>HT[j].weight&&HT[j].parent==0&&j!=s1){min=HT[j].weight;s2=j;}
	}
}

void InitHfmTree() 
{ // w存放n个字符的权值(均>0)，构造哈夫曼树HT, 并求出n个字符的哈夫曼编码HC
  FILE*fp;
  HuffmanTree HT;
  int n,i,j,s1,s2,root,w[N];   
  char str[N],ch;	
  printf("请输入字符总数：\n");
  scanf("%d",&n);
  ch=getchar();  //接收执行scanf时最后输入的回车
  root=2*n-1;
  printf("请输入字符串：\n");
  gets(str);
  printf("请依次输入权值：\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&w[i]);
		ch=getchar();  //接收执行scanf时最后输入的回车
	}
  if(n<=1)return;
  root=2*n-1;
  HT=(HuffmanTree)malloc((root+1)*sizeof(HTNode));  // 0号单元未用
  for (i=1; i<=n; i++) 
  { //初始化
    HT[i].weight=w[i-1];
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
	HT[i].date=str[i-1];
  }
  for (i=n+1; i<=root; i++)
  { //初始化
    HT[i].weight=0;
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
	HT[i].date=14;
  }
  printf("\n哈夫曼树的构造过程如下所示：\n");
  printf("HT初态:\n  结点  weight  parent  lchild  rchild   date");
  for (i=1; i<=root; i++)
    printf("\n%4d%8d%8d%8d%8d%8c",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild,HT[i].date);
    printf("    按任意键，继续 ...");
  ch=getchar();
  for (i=n+1; i<=root; ++i) 
  {  // 建哈夫曼树
    Select(HT, i-1, s1, s2);// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，其序号分别为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;
    printf("\nselect: s1=%d   s2=%d\n", s1, s2);
    printf("  结点  weight  parent  lchild  rchild   date");
    for (j=1; j<=i; j++)
      printf("\n%4d%8d%8d%8d%8d%8c",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild,HT[j].date);
    printf("    按任意键，继续 ...");//程序执行暂停
    ch=getchar();
  }
  //---建立文件hfmTree并将哈弗曼树存入文件---
	if((fp=fopen("htmTree","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=1;i<=root;i++)
		if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	printf("*********哈弗曼树已存入文件htmTree*********\n");
	free(HT);
} //  HuffmanTree
void EnCoding()//编码函数
{ //对电文tbt进行编码并存储到文件CodeFile中
	FILE*fp;
	char *cd,TBT[TL];
	int  start,root=0,n,tbl;
	unsigned int i,flag=0,c,f;
	HuffmanTree HT;
	HuffmanCode hc,HC;
	HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	hc=(HuffmanCode)malloc(TL*sizeof(char*));
	HC=(HuffmanCode)malloc(N*sizeof(char*));
	//---从文件hfmTree读取哈弗曼树---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
	n=(root+1)/2;
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd = (char *)malloc(n*sizeof(char));    // 分配求编码的工作空间
	cd[n-1] = '\0';                         // 编码结束符。
	for (i=1; i<=n; ++i)                    // 逐个字符求哈夫曼编码
	{                  
		start = n-1;                          // 编码结束符位置
		for (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));// 为第i个字符编码分配空间
		strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
	}	
	free(cd);// 释放工作空间	
	printf("请输入电文：\n");
	gets(TBT);
	for(tbl=0;TBT[tbl]!=NULL;tbl++)
	{
		i=1;
		while(TBT[tbl]!=HT[i].date&&TBT[tbl]!=NULL&&HT[i].date!=NULL)i++;
		if(TBT[tbl]==HT[i].date){hc[tbl]=(char*)malloc(CL*sizeof(char));strcpy(hc[tbl],HC[i]);}
		else hc[tbl]=NULL;
	}
	printf("电文编码如下：\n");
	for(i=0;i<tbl;i++)printf("%s ",hc[i]);
	printf("\n");
	//---建立文件codeFile并将电文编码存入文件---
	if((fp=fopen("codeFile","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<tbl;i++)
		if(fwrite(hc[i],CL*sizeof(char),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	free(HT);
	free(HC);
	free(hc);	
}//EnCoding
void DeCoding()//译码函数
{
	FILE*fp;
	char TBT[TL];
	int tbl=0,flag=0,root=0;
	HuffmanTree HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	HuffmanCode hc=(HuffmanCode)malloc(TL*sizeof(char*));;
	unsigned i,m;
	//---从文件hfmTree读取哈弗曼树---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//---从文件codeFile读取电文编码---
	if((fp=fopen("codeFile","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}	
	hc[tbl]=(char*)malloc(CL*sizeof(char));
	flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	while(flag==1)
	{
		tbl++;
		hc[tbl]=(char*)malloc(CL*sizeof(char));
		flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	}
	fclose(fp);
	printf("电文如下：\n");
	for(i=0;i<tbl;i++)
	{	
		m=root;
		int j=0;
		while(HT[m].lchild!=0&&HT[m].rchild!=0&&hc[i][j]!=NULL)
		{
			if(hc[i][j]=='0'){m=HT[m].lchild;j++;}
			else if(hc[i][j]=='1'){m=HT[m].rchild;j++;}
			else {printf("ERROR!\n");break;}
		}
		TBT[i]=HT[m].date;
	};
	TBT[tbl]=NULL;
	//建立文件textFile并将译码结果存入文件
	if((fp=fopen("textFile","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<tbl;i++)
		if(fwrite(&TBT[i],sizeof(char),1,fp)!=1)printf("FILE WRITE ERROR!\n");
	fclose(fp);
	printf("%s\n",TBT);
}//DeCoding
void Print()//以紧凑格式输出
{
	FILE*fp;
	HuffmanCode hc=(HuffmanCode)malloc(TL*sizeof(char*));
	int tbl=0,flag=0;
	char str[TL*CL];
	//---从文件codeFile读取电文编码---
	if((fp=fopen("codeFile","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}	
	hc[tbl]=(char*)malloc(CL*sizeof(char));
	flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	while(flag==1)
	{
		tbl++;
		hc[tbl]=(char*)malloc(CL*sizeof(char));
		flag=fread(hc[tbl],CL*sizeof(char),1,fp);
	}
	fclose(fp);
	strcpy(str,hc[0]);
	for(unsigned i=1;i<tbl;i++)strcpy(str,strcat(str,hc[i]));
	printf("紧凑格式的电文编码如下：\n");
	for(i=0;str[i]!=NULL;i++)
	{
		printf("%c",str[i]);
		if((i+1)%50==0)printf("\n");
	}
	printf("\n");
	//---建立文件codePrin并将紧凑格式编码写入文件---
	if((fp=fopen("codePrin","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	if(fwrite(str,strlen(str),1,fp)!=1)printf("FILE WRITE ERROR!");
	fclose(fp);
}//Print
void PrintTree()//以凹入表示法输出
{
	FILE*fp;
	char type,ch=2,**str;
	int flag=0,root=0,level[2*N-1][2],top,n,i,j=0,l,width=4;
	HuffmanTree stack,HT=(HuffmanTree)malloc((2*N-1)*sizeof(HTNode));
	HTNode p;
	HT[0].weight=-1;
	//---从文件hfmTree读取哈弗曼树---
	if((fp=fopen("htmTree","rb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	flag=fread(&HT[root+1],sizeof(HTNode),1,fp);
	while(flag==1)
	{
		root++;
		flag=fread(&HT[root+1],sizeof(HTNode),1,fp);	
	}
	fclose(fp);
	//------------------------------
	str=(char**)malloc(root*sizeof(char*));
	stack=(HuffmanTree)malloc(root*sizeof(HTNode));
	top=1;
	stack[top]=HT[root];
	level[top][0]=0;
	level[top][1]=2;
	while(top>0)
	{
		l=0;
		str[j]=(char*)malloc(100*sizeof(char));
		p=stack[top];
		n=level[top][0];
		switch(level[top][1])
		{
		case 0:type='0';break;//左节点之前输出(0)
		case 1:type='1';break;//右节点之前输出(1)
		case 2:type='r';break;//根节点之前输出(r)
		}
		//把凹入表示法表示的一行存入一个字符串
		for(i=1;i<=n;i++)str[j][l++]=' ';
		str[j][l++]=p.date;str[j][l++]='(';str[j][l++]=type;str[j][l++]=')';
		for(i=n;i<=root;i++)str[j][l++]=ch;
		str[j][l++]='\0';
		top--;
		if(HT[p.rchild].weight!=-1)
		{
			top++;
			stack[top]=HT[p.rchild];
			level[top][0]=n+width;
			level[top][1]=1;
		}
		if(HT[p.lchild].weight!=-1)
		{
			top++;
			stack[top]=HT[p.lchild];
			level[top][0]=n+width;
			level[top][1]=0;
		}
		j++;
	}
	printf("凹入表示法表示的哈弗曼树如下：\n");
	for(i=0;i<root;i++)printf("%s\n",str[i]);
	//---建立文件treePrint并将凹入表示法表示的哈弗曼树写入文件---
	if((fp=fopen("treePrint","wb"))==NULL)
	{printf("CANNOT OPEN FILE!\n");return;}
	for(i=0;i<root;i++)
		if(fwrite(str[i],strlen(str[i]),1,fp)!=1)printf("FILE WRITE ERROR!");
	fclose(fp);
}//PrintTree
int main()
{
	bool s=1;
	char sw,ch;
	while(s)
	{	
		printf("请选择操作:\n1:初始化'i'\n2:编码'e'\n3:译码'd'\n4:印代码'p'\n5:凹入表输出't'\n6:退出程序'q'\n");
		scanf("%c",&sw);
		ch=getchar(); 
		switch(sw)
		{
		case'i':InitHfmTree();printf("初始化完毕\n");break;
		case'e':EnCoding();printf("编码完毕\n");break;
		case'd':DeCoding();printf("译码完毕\n");break;
		case'p':Print();printf("印代码完毕\n");break;
		case't':PrintTree();printf("凹入表输出完毕\n");break;
		case'q':s=0;break;
		default:printf("输入错误!");break;
		}
	}
}