5_47.cpp

C++程序设计技能百练随书配套光盘的源码

#include<iostream.h>
#include<iomanip.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个结点
	int i,k,l,r,n,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
	}
	cout<<"结点值  "<<"双亲值  "<<"权重  "<<"左孩子  "<<"右孩子  "<<endl;
	for (i=1;i<=2*n-1;i++)
	cout<<setw(2)<<ht[i].data<<setw(8)<<ht[i].parent<<setw(8)<<ht[i].weight
		<<setw(8)<<ht[i].left<<setw(8)<<ht[i].right<<endl;
}