1.cpp

哈夫曼树和哈夫曼编码： 从终端输入若干个字符及其对应的整数

#include "iostream"
#include "malloc.h"
#include "string"
#include "iomanip"
using namespace std;
typedef struct {
	int data;
	unsigned int weight;//定义权值
	unsigned int parent,lchild,rchild;//定义父母，左右孩子
}HTNode,*HTree;
int n;
void CreateHTree(HTree &T) {   //创建哈夫曼树
	int m,i;
	cout<<"请输入节点个数：";
	cin>>n;
	m=2*n-1;//权值个数
	T=(HTree)malloc((m+1) * sizeof(HTNode));
	for(i=1;i<=n;++i) {
		char d=NULL;
		int w=NULL;
		cout<<"请输入第"<<i<<"节点的权重：";
		cin>>w;
		T[i].data=i;
		T[i].weight=w;
		T[i].parent=NULL;
		T[i].lchild=NULL;
		T[i].rchild=NULL;
	}
	for(;i<=m;++i) {
		T[i].data=i;
		T[i].weight=NULL;
		T[i].parent=NULL;
		T[i].lchild=NULL;
		T[i].rchild=NULL;
	}
	cout<<"排序前的赫夫曼表："<<endl;
	cout<<"order"<<setw(10)<<"weight"<<setw(10)<<"parent"<<setw(10)<<"lchild"<<setw(10)<<"rchild"<<endl;
	for(int z=1;z<=m;++z)
	cout<<T[z].data<<setw(10)<<T[z].weight<<setw(10)<<T[z].parent<<setw(10)<<T[z].lchild<<setw(10)<<T[z].rchild<<endl;
	cout<<endl;
		for(int j=1;j<=n-1;++j) {
			unsigned int m1,m2;
			m1=m2=1000;
			unsigned int x1,x2;
			x1=x2=1;
			for(int k=1;k<=n+j-1;++k) {
				if(T[k].weight<m1 && T[k].parent==0) {
					m2=m1;
					x2=x1;
					m1=T[k].weight;
					x1=k;
				}
				else if(T[k].weight<m2 && T[k].parent==0) {
					m2=T[k].weight;
					x2=k;
				}
			}
			T[x1].parent=n+j;
			T[x2].parent=n+j;
			T[n+j].weight=T[x1].weight+T[x2].weight;
			T[n+j].lchild=x1;
			T[n+j].rchild=x2;
		}
		cout<<"排序后的赫夫曼表："<<endl;
		cout<<"order"<<setw(10)<<"weight"<<setw(10)<<"parent"<<setw(10)<<"lchild"<<setw(10)<<"rchild"<<endl;
		for(int x=1;x<=m;++x)
		cout<<T[x].data<<setw(10)<<T[x].weight<<setw(10)<<T[x].parent<<setw(10)<<T[x].lchild<<setw(10)<<T[x].rchild<<endl;
		cout<<endl;
}

void Coding(HTree &T) {   //输入哈夫曼编码
	for(int i=1;i<=n;++i) {
		string str1,str2;
		int j=i;
		while(T[j].parent!=NULL) {
			if(T[T[j].parent].lchild==j) {
				j=T[j].parent;
				str1='0';
				str1+=str2;
				str2=str1;
			}
			else if(T[T[j].parent].rchild==j) {
				j=T[j].parent;
				str1='1';
				str1+=str2;
				str2=str1;
			}
		}
		cout<<T[i].data<<"->"<<str2<<endl;
	}
	cout<<endl;
}

void PrintHTree(HTree &T,int i) {   //打印哈夫曼树
	if(T[i].lchild)
		PrintHTree(T,T[i].lchild);
	cout<<T[i].weight<<" ";
	if(T[i].rchild)
		PrintHTree(T,T[i].rchild);
}

void main()
{
	HTree HT;
	CreateHTree(HT);
	cout<<"赫夫曼编码为："<<endl;
	Coding(HT);
	cout<<"中序打印树为：";
	PrintHTree(HT,2*n-1);
	cout<<endl;
}