huffman.cpp

为得到使电文总长最短的二进制前缀编码

// Huffman.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include  "stdlib.h"
#include  "stdio.h"
#include "string.h"
#define   MAX    32767

//----------------定义-----------------------------
typedef struct
{
	unsigned int weight;               //权重
    unsigned int parent,lchild,rchild;//双亲与左右孩子
}HTNode,*HuffmanTree;//动态分配数组存储Huffman树
typedef char**HuffmanCode;//动态分配数组存储Huffman编码表

//--------------------函数声明----------------------------------
int min(HuffmanTree t,int i);//select要调用的函数
void select(HuffmanTree t,int i,int &s1,int &s2);//选取权值最小且双亲为0的字符
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n);//构造赫夫曼树,求出赫夫曼编码


//---------------------子函数区-----------------------------------
int min(HuffmanTree t,int i)//select要调用的函数
{
	int j,flag;
	unsigned int k=MAX;//K不应小于可能的值
	for(j=1;j<=i;j++)
		if(t[j].weight<k&&t[j].parent==0)
			k=t[j].weight,flag=j;
		t[flag].parent=1;
		return flag;
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{
	int j;
	s1=min(t,i);//选择parent=0，weight最小的两个接点，其序号是S1，S2
	s2=min(t,i);
	if(s1>s2)//保证S1为最小的两个值中序号小的那个
	{
		j=s1;
		s1=s2;
		s2=j;
	}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{//w存放n个字符的权值(均>0),构造Huffman树HT,并求出n个字符的Huffman编码HC
//方法一:在找到两个无双亲且权值最小的结点后,将序号小的结点作为左子树,序号大的结点作为右子树
	int m,i,s1,s2,start;
	unsigned c,f;
	HuffmanTree p;
	char *cd;
	if(n<=1)
		return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
	for(p=HT+1,i=1;i<=n;++i,++p,++w)
	{
		(*p).weight=*w;
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	for(;i<=m;++i,++p)
	(*p).parent=0;
	for(i=n+1;i<=m;++i)//建Huffman树
	{//在HT[1..i]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
		select(HT,i-1,s1,s2);
		HT[s1].parent=HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	//-----从叶子到根逆向求每个字符的Huffman编码-----
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
	cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
	cd[n-1]='\0';                    //编码结束符
	for(i=1;i<=n;i++)                //逐个字符求Huffman编码
	{
		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);//释放工作空间
 //方法二:无栈非递归遍历Huffman树,求Huffman编码
/*	int m,i,s1,s2;
	unsigned c,cdlen;
	HuffmanTree p;
	char *cd;
	if(n<=1)
		return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(p=HT+1,i=1;i<=n;++i,++p,++w)
	{
		(*p).weight=*w;
		(*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,s1,s2);
		HT[s1].parent=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));//分配求编码的工作空间
    c=m;
	cdlen=0;
	for(i=1;i<=m;++i)
		HT[i].weight=0;            //遍历Huffman树时用做结点状态标志
	while(c)
	{
		if(HT[c].weight==0)
		{
			HT[c].weight=1;
			if(HT[c].lchild!=0)
			{
				c=HT[c].lchild;
				cd[cdlen++]='0';
			}
			else if(HT[c].rchild==0)//登记叶子结点的字符的编码
			{
				HC[c]=(char*)malloc((cdlen+1)*sizeof(char));
				cd[cdlen]='\0';
				strcpy(HC[c],cd);//复制编码(串)
			}
		}
		else if(HT[c].weight==1)//向右
		{
			HT[c].weight=2;
			if(HT[c].rchild!=0)
			{
				c=HT[c].rchild;
				cd[cdlen++]='1';
			}
		}
		else
		{//退回
			HT[c].weight=0;
			c=HT[c].parent;
			--cdlen;//退到父结点,编码长度减1
		}
	}	
	free(cd);*/ 
}

//---------------------主函数-----------------------------------
void main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int *w,n,i;
	printf("请输入权值的个数(>1)：");
	scanf("%d",&n);
	w=(int*)malloc(n*sizeof(int));
	printf("请依次输入%d个权值(整型)：\n",n);
	for(i=0;i<=n-1;i++)
		scanf("%d",w+i);
	printf("权值依次为:\n");
	HuffmanCoding(HT,HC,w,n);
	for(i=1;i<=n;i++)
		puts(HC[i]);
}