[数据结构与算法]C语言——哈夫曼树的应用

C语言——哈夫曼树的应用

内容

从键盘输入一串电文字符与权值，输出对应的哈夫曼编码；从键盘输入一串二进制代码，输出对应的电文字符串。具体步骤如下：

1. 构造一棵哈夫曼树；
2. 实现哈夫曼编码；
3. 对哈夫曼编码生成的二进制串进行译码；
4. 要求程序中字符和权值是可变的，实现程序的灵活性。

实验代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_MA 1000
#define MAX_ZF 100

typedef struct
{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void Select(HuffmanTree HT,int len,int &s1,int &s2);                 //权值选取
void CreateHuffmanTree(HuffmanTree &HT,int n);                       //创建
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n);        //编码
void HuffmanDecode(HuffmanTree HT,char a[],char zf[],char b[],int n);//译码

void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
	int i;
	//int min1=10000,min2=10000;
	//for(i=1;i<=len;i++)
	//{
	//	if(HT[i].weight<min1&&HT[i].parent==0)
	//	{
	//		min1=HT[i].weight;
	//		s1=i;
	//	}
	//	t=HT[s1].weight;
	//	HT[s1].weight=10000;
	//}
	//for(i=1;i<=len;i++)
	//{
	//	if(HT[i].weight<min2&&HT[i].parent==0)
	//	{
	//		min2=HT[i].weight;
	//		s2=i;
	//	}
	//}
	//HT[s1].weight=t;
	s1 = s2 = 0;                                                //算法优化
	for(i=1;i<=len;i++)
	{
		if(HT[i].parent==0 && HT[i].weight<HT[s1].weight)
		{
			s1 = i;
		}
		else if(HT[i].parent==0 && HT[i].weight<HT[s2].weight)
		{
			s2 = i;
		}
	}
}
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
	int s1,s2;
	if(n<=1)
		return;
	int m,i;
	m=2*n-1;
	HT=new HTNode[m+1];
	memset(HT,0,sizeof(HTNode)*(m+1));
	printf("请依次输入%d个叶子结点的权值： ",n);
	for(i=1;i<=n;i++)
	{	
		scanf("%d",&HT[i].weight);
	}
	fflush(stdin);
	HT[0].weight = 10000;
	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;
	}
	printf("哈夫曼树创建成功\n");
}
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{
	int i,start;
	int c,f;
	HC=new char* [n+1];
	char *cd = new char [n];
	cd[n-1]=0;
	for(i=1;i<=n;i++)
	{
		start=n-1;
		c=i;
		f=HT[i].parent;
		while(f!=0)
		{
			start--;
			if(HT[f].lchild==c)
				cd[start]='0';
			else
				cd[start]='1';
			c=f;
			f=HT[f].parent;
		}
	   HC[i]=new char[n-start]; 
	   strcpy(HC[i],&cd[start]);
	}
	delete cd;
}
void HuffmanDecode(HuffmanTree HT,char a[],char zf[],char b[],int n)
{
	int q = 2*n-1;
	int k=0;
	int i;
	for(i=0;a[i]!='\0';i++)
	{
		if(a[i]=='0')
		{
			q=HT[q].lchild;
		}
		else if(a[i]='1')
		{
			q=HT[q].rchild;
		}
	   if(HT[q].lchild==0&&HT[q].rchild==0)
	   {
		   b[k++]=zf[q];
		   q=2*n-1;
	   }
	}
	b[k]='\0';
}
void main()
{
	int num;
	int i;
	char *a = (char*)malloc(MAX_ZF);
	char *b = (char*)malloc(MAX_ZF);
	char *zf = (char*)malloc(MAX_ZF);
	HuffmanTree HT = NULL;
	HuffmanCode HC = NULL;
	printf("请输入字符个数: ");
	scanf("%d",&num);
	fflush(stdin);
	printf("请依次%d输入字符：",num);
	for(i=1;i<=num;i++)
	{
		scanf("%c",zf + i);
	}
	CreateHuffmanTree(HT,num);
	CreateHuffmanCode(HT,HC,num);
	printf("  哈夫曼编码   \n");
	printf("结点\t字符\t权值\t编码\n");
	for(i=1;i<=num;i++)
	{
		printf("%d\t%c\t%d\t%s\n",i,zf[i],HT[i].weight,HC[i]);
	}
    printf("  哈夫曼译码   \n");
	printf("请输入二进制编码：");
	scanf("%s",a);
	HuffmanDecode(HT,a,zf,b,num);
	printf("二进制编码对应的字符串：%s\n",b);

实验结果

总结

1、创建哈夫曼树主要是找到权值最小的两个叶子节点进行合并，删除，通过for循环实现这一操作。
2、哈夫曼树的编码基本思想是为出现次数较多的字符编以较短的编码，在进行此算法编写过程中，应注意回溯过程是向上回溯，得到的编码顺序是从右向左。
3、哈夫曼树的译码算法完成后因没有字符结束符出现报错，所以在一次次的调试程序实现算法。