ht.cpp

这是数据结构学习过程中的实验 关于哈弗曼的编码和译码。 算法还有待改进

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


#define NO 100//最多no个叶子,编码、译码最大长度
#define MO 2*NO-1 //最多mo个结点

struct HT
{
	int weight;
	int lch, rch, parent;
};

HT ht[NO+1];//0单元不用

struct HNode
{
	char ch;
	char bit[NO];
	int start;
};

struct HNode ha[MO+1];
int n, m;
//判断次数

void select(int t, int &s1, int &s2)
{//从1~t里找出parent==0且权重为最小、次小
	int w1, w2, i;
	w1 = 32767;
	w2 = w1;
	s1 = s2 = 0;
	for(i = 1; i <= t; i++)		
	{	if(ht[i].parent == 0 && ht[i].weight < w1)
			{
					s2 = s1;//将最小的编号送给s2当次小编号
					w2 = w1;//将w1送到w2当次小
					w1 = ht[i].weight;
					s1 = i;
			}
		else	
			if(ht[i].parent == 0 && ht[i].weight < w2)
			{
					w2 = ht[i].weight;
					s2 = i;
			}
			
	}
	//for
}//select

void creatHT_HNode()
{
	int i,child, parent, s1, s2;
	struct HNode dx;
	cout << "请输入叶子数n：" << endl;
	cin >> n;
	m = 2*n-1;
	for(i = 1; i <= m; i++)
	{
		ht[i].lch = ht[i].rch = ht[i].parent = 0;	//初始化
	}

	for(i = 1; i <= n; i++)
	{
		cout << "请输入字符ch,权值weight: " << endl;
		cin >> ha[i].ch >> ht[i].weight;
	}
	cout << "构造树的过程" << endl;
	for(i = n+1; i <= m; i++)//生成树
	{
		{
			select(i-1, s1, s2);
			ht[i].weight = ht[s1].weight + ht[s2].weight;//父亲权重
			ht[i].lch = s1;
			ht[i].rch = s2;//父亲的左右孩子
			ht[s1].parent = ht[s2].parent = i;//孩子的父亲标号
		}

		{
				cout << ht[i].weight << "	" << endl;	
				cout << ht[s1].weight << " " << ht[s2].weight << endl;
				cout << endl;
		}
	}//构造树


	for( i = 1; i <= n; i++)//进行编码
	{
		dx.ch = ha[i].ch;
		dx.start = 0;//
		child = i;
		parent = ht[i].parent;
		while( parent != 0)
		{
			if(ht[parent].lch == child)//判断左孩子为其左子树
				dx.bit[ dx.start++] = '0';//左标记为0，且记号start+1
			else 
				if(ht[parent].rch == child)//判断右孩子为其右子树
				dx.bit[ dx.start++] = '1';//右标记为1，且记号start+1
			child = parent;//动态根结点下移到其子树
			parent = ht[child].parent;//子树的父亲重新赋值
		}
		ha[i] = dx;//将一个叶子的编码传递给对应的叶子结构体
	}
}

		
void printT(int root,int i)//输出树
{
	int j;
	for(j = 0; j <= i; j++)	
		cout << "   ";
	cout << ht[root].weight << " " << ha[root].ch << endl;
	if(ht[root].rch != 0 || ht[root].lch != 0)//判断左右子树是否为空
	{
		printT(ht[root].rch, ++i);	//进行递归
		printT(ht[root].lch, i++);	//进行递归
	}	
}//遍历构造出来的树



void print( HNode ha[],HT ht[])
{
	int i,k;
	for(i = 1; i<= m; i++)
	{
		cout << "字符：" << ha[i].ch;
		cout << "     权重：" << ht[i].weight;
		cout << "     编码：";
		for( k = ha[i].start-1; k >= 0; k--)
		{		
			cout << ha[i].bit[k];
		}
		cout << "     左孩子：" << ht[i].lch << "     右孩子：" << ht[i].rch << "     父亲：" << ht[i].parent << endl;
	}
}


void Coding()//进行编码
{
	int i,k,t,j = NO;
	cout << "请输入需要编码的字符串(最长100)：" << endl;
	char c[101];
	cin >> c;
	for(i = 0; i <= j; i++)//查找每个字符数组元素
	{
		for(t = 1;t <= n; t++)//查找叶子
		{
			if(ha[t].ch == c[i])//判断字符与叶子是否相同
			{
				for( k = ha[t].start-1; k >= 0; k--)//从各个叶子的相应记录开始输出
				{		  
					cout << ha[t].bit[k];//输出相应的编码
				}//for
			}//if
		}//if
	}//for

	cout<<endl;
}


void HTCoding(HT ht[])//进行译码
{
	int i = 0, j = NO;
	int  p;
	char c[NO];//c存放要译码的字符
	p = m;//p指向根结点
	cout << "请输入需要译码的字符串(最长100)：" << endl;
	cin >> c;
	while(c[i] != '\0')
	{
			{	
				if(c[i] == '0')	p = ht[p].lch;//判断c[i]中的值:0向左走
				else		p = ht[p].rch;  //1向右走
			}

			if(ht[p].rch == 0 && ht[p].rch == 0)//判断
			{	
				cout << ha[p].ch << " ";
				p = m;//p继续从根结点开始
			}

			i++;
	}

	cout<<endl;

}
void main()
{
	cout << "开始规定相应的字符 " << endl;
	creatHT_HNode();//建立相应的哈弗曼树
	cout << endl << "树为：" << endl;
	printT(m,0);//输出树
	cout << endl;
	print(ha,ht);//输出各个结点信息
	cout << endl << endl;
	while(1)
	{
		cout << "		主程序		" << endl;
		cout << "请输入想进行的操作：1.编码	      2.译码		3.退出" << endl;
		char z;
			cin >> z;
			switch(z)
			{
			case '1':
				Coding();   //编码
				continue;
			case '2':
				HTCoding(ht);  //译码
				continue;
			case '3':
				exit(1);
			default:;
			}
	}
}