huffman.c

哈夫曼编码——构建哈夫曼树并对其进行编码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXNODE 20                  //需要编码的字符的最大个数
#define MAXWEIGHT 200               //权值最大值            
#define MAXCHARS 200                //所给文章的最大字符数
#define MAX     1000                //01序列的最大字符数


//------------哈夫曼树和哈夫曼编码的存储表示---------------
typedef struct{
    char data;
	int weight;
	int parent,lchild,rchild;
}HTnode,*HuffmanTree;                 //动态分配数组存储哈夫曼数
typedef char ** HuffmanCode;          //动态分配数组存储哈夫曼编码表


//------------------------函数说明-----------------------------
void Huffmanlist(HuffmanTree HT,int *W,char *D,int n,int m);
   //W存放n个字符的权值（均为〉0的整数）,D存放的是需要编码的字符,构造哈夫曼树HT.
void Huffmancoding(HuffmanTree HT,HuffmanCode HC,int n,int m);
   //根据已编的哈夫曼树给字符编码
void Select(HuffmanTree HT,int num,int *s1,int *s2);
   //选择两个权值最小的结点，并且以s1,s2返回
void Messagecoding(HuffmanTree HT,HuffmanCode HC,int n);
   //给一段字符串编码
void FMessagecoding(HuffmanTree HT,HuffmanCode HC,int n);
   //给一段01码译码成原文 
void Substring(char Message[],char Temp[],int front,int rear);
   //求从front到rear的一段子串，用Temp带回子串

main()
{
	int nodenumber;               //需要编码的字符的数目
	int wweight[MAXNODE];         //权值
	int *WEIGHT=wweight;
	char ddata[MAXNODE];	      //字符
	char *DATA=ddata;
	HuffmanTree HT;                
	HuffmanCode HC;
	int i;
	int m;            //实际需要的存储单元
	printf("输入需编码的字符个数(最多输%d个):\n",MAXNODE);
	scanf("%d",&nodenumber);
	printf("输入需编码的字符(不间断连续输入)");
	scanf("%s",ddata);
    printf("依次输入对应的字符的权值(最大为%d):\n",MAXWEIGHT);
	for(i=0;i<nodenumber;++i)
		scanf("%d",&wweight[i]);
    m=2*nodenumber-1;               //有nodenumber个结点的哈夫曼树具有（2nodenumber-1）个结点
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTnode));         //0号单元不用
	Huffmanlist(HT,WEIGHT,DATA,nodenumber,m);
	HC=(HuffmanCode)malloc((nodenumber+1)*sizeof(char *));          //分配nodenumber个字符的头指针向量
	Huffmancoding(HT,HC,nodenumber,m);                    //字符编码
	Messagecoding(HT,HC,nodenumber);                      //一段文字编码
	FMessagecoding(HT,HC,nodenumber);	                  //一段01码译码成原文
}

void Huffmanlist(HuffmanTree HT,int *W,char *D,int n,int m)
{
	int i;
	int s1,s2;                    //weight最小的两个结点
	if(n<=1)
		return;
	for(i=1;i<=n;++i)              //叶子结点给初值
	{
		HT[i].data=*(D++);
		HT[i].weight=*(W++);
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)           //非叶子结点给初值
	{
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
    for(i=n+1;i<=m;++i)             //建哈夫曼树
	{
		//在HT[1..i-1]选择perent为0且weight最小的两个结点，其序号分别为s1,s2. 
		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;
	}
	
}

//------------从叶子到根逆向求每个字符的哈夫曼编码---------------
void Huffmancoding(HuffmanTree HT,HuffmanCode HC,int n,int m)
{
	char *cd;
	int i;
	int c,f;
	int start;            
	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';                          //左孩子编码为0
			else cd[--start]='1';                         //右孩子编码为1
		}
		HC[i] = (char *)malloc((n-start)*sizeof(char));          //为第i个字符编码分配空间
		strcpy(HC[i],&cd[start]);                 //从cd复制编码（串）到HC
	}
	free(cd);                            //释放工作空间
	printf("编码情况：\n");
	for(i=1;i<=n;i++)
	{
	   printf("%c:%s\n",HT[i].data,HC[i]);            //输出编码
	}

}

void Select(HuffmanTree HT,int num,int *s1,int *s2)
{
	int i;
	int temp1,temp2;            //temp1中存最小的数，temp2中存次小的数
	temp1=temp2=MAXWEIGHT;      //给temp1,temp2赋初值
	for(i=1;i<=num;++i)                 //选择perent为0且weight最小的结点。
	{
		if(HT[i].parent==0 && HT[i].weight<temp1)
		{
			temp1=HT[i].weight;
			*s1=i;
		}
	}
	for(i=1;i<=num;++i)                  //选择perent为0且weight次小的结点。
	{
		if(HT[i].parent==0 && HT[i].weight<temp2 && i!=*s1)
		{
			temp2=HT[i].weight;
			*s2=i;
		}
	}
}

void Messagecoding(HuffmanTree HT,HuffmanCode HC,int n)          
{
	int i,j;
	char message[MAXCHARS];                  //文字字符存储
	printf("以下是给一段字符编码：\n请输入一段正文（最多%d个字符），由以上字符组成:\n",MAXCHARS);
	scanf("%s",message);
	for(i=0;message[i]!='\0';i++)
	{
		for(j=1;j<=n;j++)
		{
			if(message[i]==HT[j].data)          //字符相匹配
				printf("%s",HC[j]);             //输出字符对应的码
		}
	}
}

void FMessagecoding(HuffmanTree HT,HuffmanCode HC,int n)
{   
	int i,j,t;
	char ch;
	char message[MAX];               //01字符串存储
	char temp[MAXNODE];
	printf("\nDo you want to code these 0&1 character string into prototype?\n");
	printf("Y:continue\nN:exit\n");
    ch=getchar();
	while(ch=='\n')
		ch=getchar();
	if(ch=='Y')              //继续译码求过程
	{
		printf("请输入01字符序列（最多%d个字符）:\n",MAX);
        scanf("%s",message);
		i=j=0;
		while(message[i]!='\0')
		{
			Substring(message,temp,i,j);           //得到从i到j的子串
		    for(t=1;t<=n;t++)
			{
			   if(strcmp(temp,HC[t])==0)          //字串相匹配
			   {
				   printf("%c",HT[t].data);       //输出字串对应的字符
				   i=j+1;                         //i指针后移
				   j=i;
				   break;
			   }   
			}//for
			if(t==n+1)
				j++;
		}//while
	}//if
	else if(ch=='N')             //结束程序
	    exit(0);
}

void Substring(char Message[],char Temp[],int front,int rear)
{
    int t;
	int i;
	for(i=0,t=front;t<=rear;t++,i++)
	{
		Temp[i]=Message[t];
	}
	Temp[i]='\0';
}