hefuman.cpp

这是一个霍夫曼编码运用的程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//赫夫曼树结点的结构体
typedef struct HTNode
{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;   //动态分配数组存储赫夫曼树
 //动态分配数组存储赫夫曼编码表
typedef char * * HuffmanCode;  
int s1,s2;   //用于存放权值最小的两个结点
//选择权值最小的两个结点
void Select(HTNode *HT,int n)
{
	int m;   //临时记录编码表的位置
	int x;   //暂存比较的值的大小

	for(x=9999,m=1;m<=n;m++)   //寻找s1的值
	{
		
		if(((HT[m].weight)<x)&&(HT[m].parent==0))
		{
			x=HT[m].weight;
			s1=m;
		}
	}
	for(x=9999,m=1;m<=n;m++)   //寻找s2的值
	{
		if((m!=s1)&&((HT[m].weight)<x)&&(HT[m].parent==0))
		{
			x=HT[m].weight;
			s2=m;
		}
	}
}
//建立赫夫曼树并打印每个字母的赫夫曼编码
HuffmanCode HuffmanCoding(int *w,int n)   //w存放n个字符的权值（均〉0）
{
	int m,i,start,c,f;   //m为总结点数，i,start,c,f均为计数器
	HTNode *p;   //指向结点的临时指针
	HTNode *HT;   //赫夫曼编码表
	HuffmanCode HC;   //储存字符编码
	char *cd;   //暂存所求的编码
	
	if(n<=1)
		printf("\n请输入两个以上的元素！\n");
	else
	{
		p=(HTNode *)malloc(sizeof(HTNode));
		m=2*n-1;   //总结点数
        HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));   //零号单元不用
		p=HT;
		for(p++,i=1,c=0;i<=n;i++,p++,c++)   //赋初值
		{
			p->weight=w[c];
			p->parent=0; 
			p->lchild=0;
			p->rchild=0;
		}

		for(;i<=m;i++,p++)
		{
			p->weight=0;
			p->parent=0; 
			p->lchild=0;
			p->rchild=0;
		}
        for(i=n+1;i<=m;i++)   //建立赫夫曼树
		{
			Select(HT,i-1);
			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个字符编码的头指针向量
	cd=(char *)malloc(n*sizeof(char));   //分配求编码的工作空间
    cd[n-1]='\0';
	p=HT;

	printf("\n");
	for(i=1,p++;i<=n;i++,p++)
	{
		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]);
		printf("%c的赫夫曼编码为：",char(i+64));
		printf("%s\n",HC[i]);   //打印编码

	}
	printf("\n\n");
	free(cd);   //释放临时空间
	return HC;
}
//将字母串译为赫夫曼编码
void ziTOhe(char string[],HuffmanCode HC,char code[500],char temp[500])
{
	int i=0,k=0,j=0; //计数器。i指向string，用于处理每一个字母；k指向code，用于依次存放0或1；
	char *c; //字符型指针，指向HC表，用于提取每一个0或1
	
	for(;string[i]!='\0';i++)//依次提取用户输入的字母
	{
		for(c=HC[string[i]-64];(*c)!='\0';c++,k++,j++)//从HC表中取出相应字母的赫夫曼编码
		{
			code[k]=(*c);//将该字母的赫夫曼编码依次存入最终要输出的赫夫曼编码的数组中
            temp[j]=(*c);//该数组存放每个元素的赫夫曼编码，并用空格分隔
		}
		temp[j]=' ';
		j++;		
	}
	code[k]='\0';
	temp[j]='\0';
	printf("将字符串译为赫夫曼编码后为：\n");
	printf("%s\n",code);
}
//将赫夫曼编码译为字符串
void heTOzi(HuffmanCode HC,char temp[500])
{
	int i=0,j=0;
	char *c;
	char string[10];
	c=temp;
	printf("\n译码之后的字符串为：\n");
	for(;(*c)!='\0';c++)
	{
		for(i=0;(*c)!=' ';c++,i++)
			string[i]=*c;
		string[i]='\0';
		for(i=1;i<=26;i++)
		{
		
			if(strcmp(HC[i],string)==0)
			{	
				printf("%c",char(i+64));
				break;				
			}
		}
	}
	printf("\n\n");

}
//主函数
void main()
{
	char string[100]; //存放字符串
	int weight[26]={0};   //存放各字母的权值
	char code[500]; //存放翻译为赫夫曼编码的数组
	char temp[500]; //临时数组
    int i;  //计数器

    HuffmanCode HC;
    printf("\n\n          ********** 赫夫曼编码的应用 **********\n\n");
	printf("请输入一串字符串，用大写英文字母表示（不含除英文字母之外的符号）：\n");
    scanf("%s",string);
	for(i=0;string[i]!='\0';i++) //利用ASCII代码将每个字母出现的次数作为权值保存至weight数组中
		weight[string[i]-65]++;
	printf("\n");
	for(i=0;i<26;i++)		
        printf("字母%c出现的次数为：%d\n",char(i+65),weight[i]);
    HC=HuffmanCoding(weight,26);	//将权值数组和结点数(26个)传入函数
    ziTOhe(string,HC,code,temp);
    heTOzi(HC,temp);
    
}