5_48.cpp

《c++程序设计技能百练》源代码,内有99个实例。

#include<iostream.h>
#define Max 21
typedef struct  //Huffman树的节点结构
{
	char data;  //节点值
	int weight;  //权值
	int parent;  //双亲节点下标
	int left;  //左孩子下标
	int right;  //右孩子下标
}HuffNode;
typedef struct  //存放Huffman编码的数组元素结构
{
	char cd[Max];  //数组
	int start;  //编码的起始下标
}HuffCode;

void main()
{
	HuffNode ht[2*Max];  //n个叶子节点的Huffman树共2n-1个节点
	HuffCode hcd[Max],d;
	int i,k,f,l,r,n,c,m1,m2;
	cout<<"元素个数:";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"第"<<i<<"个元素=>\t节点值:";
		cin>>ht[i].data;
		cout<<"\t\t权  重:";
		cin>>ht[i].weight;
	}
	for (i=1;i<=2*n-1;i++)  //n个叶子节点共有2n-1个节点
		ht[i].parent=ht[i].left=ht[i].right=0;  //初值为0
	for (i=n+1;i<=2*n-1;i++)  //构造Huffman树,每次循环构造一棵二叉树
	{
		m1=m2=32767;  //设定初值，用于求最小权重节点
		l=r=0;  //l和r为最小权重的两个节点位置
		for(k=1;k<=i-1;k++)  //每次找出权值最小的两个节点
			if(ht[k].parent==0)
				if(ht[k].weight<m1)
				{
					m2=m1;
					r=l;
					m1=ht[k].weight;
					l=k;
				}
				else if(ht[k].weight<m2)
				{
					m2=ht[k].weight;
					r=k;
				}
			ht[l].parent=i;  //给双亲节点编号
			ht[r].parent=i;
			ht[i].weight=ht[l].weight+ht[r].weight;  //双亲节点权重
			ht[i].left=l;  //左孩子为l
			ht[i].right=r;  //右孩子为r
	}
	for (i=1;i<=n;i++)  //根据Huffman树求编码
	{
		d.start=n+1;
		c=i;
		f=ht[i].parent;
		while(f!=0)  //由叶子节点向上直到根节点
		{
			if(ht[f].left==c)
				d.cd[--d.start]='0';  //左孩子节点编码为0
			else 
				d.cd[--d.start]='1';
			c=f;
			f=ht[f].parent;
		}
		hcd[i]=d;
	}
	cout<<"输出Huffman编码:\n";
	for (i=1;i<=n;i++)  //输出叶子节点的Huffman编码
	{
		cout<<"  "<<ht[i].data<<":";
		for(k=hcd[i].start;k<=n;k++)
			cout<<hcd[i].cd[k];
		cout<<endl;
	}
}