14_3_2.cpp

王红梅编《数据结构》大多数的实验源码。内附详细的实验报告。

#include <iostream.h>
#include <iomanip.h>
#define MAX_SIZE 100

struct Element
{
	int rate;		// 字符出现的频率
	char ch;		// 字符
	int lchild;		// 左孩子
	int rchild;		// 右孩子
	int parent;		// 结点的双亲
};

/*
@ HuffmanTree
前置条件：	Huffman树不存在
功能：		构造一颗Huffman树
输入：		储存树的数组，
			字符出现的频率，
			以及储存字符的数组，
			字符的个数
输出：		无
后置条件：	创建了一颗Huffman树于huffTree数组
*/
void HuffmanTree(Element huffTree[], int rate[], char c[], int n)
{
	for (int i = 0; i <= 2 * n - 1; i++)
	{
		huffTree[i].parent = -1;
		huffTree[i].lchild = -1;
		huffTree[i].rchild = -1;
	}
	for (i = 0; i < n; i++)
	{
		huffTree[i].rate = rate[i];
		huffTree[i].ch	 = c[i];
	}
	int p = 0;
	for (i = n; i < 2 * n - 1; i++)
	{
		huffTree[i].lchild		= p;
		huffTree[i].rchild		= p + 1;
		huffTree[i].rate		= huffTree[p].rate + huffTree[p + 1].rate;
		huffTree[i].ch			= '-';
		huffTree[p].parent		= i;
		huffTree[p + 1].parent	= i;
		p = p + 2;
	}
	huffTree[ 2 * n - 1 ].rate = -1;
}

/*
@ PrintTree
前置条件：	Huffman树存在
输入：		储存树的数组，
			字符的个数
功能：		打印Huffman树的各个结点
输出：		无
后置条件：	树不变
*/
void PrintTree(Element huffTree[], int n)
{
	cout << setw(6) << "char";
	cout << setw(6) << "rate";
	cout << setw(6) << "parent";
	cout << setw(6) << "lchild";
	cout << setw(6) << "rchild";
	cout << endl;
	for (int i = 0; i < 2 * n - 1; i++)
	{
		cout << setw(6) << huffTree[i].ch;
		cout << setw(6) << huffTree[i].rate;
		cout << setw(6) << huffTree[i].parent;
		cout << setw(6) << huffTree[i].lchild;
		cout << setw(6) << huffTree[i].rchild;
		cout << endl;
	}
}

/*
@ PrintCode
前置条件：	Huffman树存在
输入：		储存树的数组，
			字符的个数
功能：		打印最佳的编码方案
输出：		无
后置条件：	树不变
*/
void PrintCode(Element huffTree[], int n)
{
	cout << setw(5) << "char";
	cout << setw(10) << "code" << endl;
	for (int i = 0; i < n; i++)
	{
		int rec[MAX_SIZE];
		int top = -1;
		int tmp = i;
		while (tmp != 2 * n - 1)
		{
			if (tmp == huffTree[huffTree[tmp].parent].lchild)
				rec[++top] = 0;
			else
				rec[++top] = 1;
			if (huffTree[tmp].parent != -1)
				tmp = huffTree[tmp].parent;
			else
				tmp = 2 * n - 1;
		}
		cout << setw(5) << huffTree[i].ch;
		cout << "   ";
		for (int j = top; j >= 0; j--)
			cout << rec[j];
		cout << endl;
	}
}

void main()
{
	int i = 0;

	cout << "请输入频率：（输入-1结束）" << endl;
	int rate[MAX_SIZE];
	int r;
	while (r != -1)
	{
		cin >> r;
		rate[i] = r;
		i++;
	}

	cout << "请输入对应的字符：（输入#结束）" << endl;
	char c[MAX_SIZE];
	char c2;
	i = 0;
	while (c2 != '#' && 2 * i - 1 < MAX_SIZE)
	{
		cin >> c2;
		c[i] = c2;
		i++;
	}

	Element huffTree[ MAX_SIZE / 2 ];
	HuffmanTree(huffTree, rate, c, i - 1);

	PrintTree(huffTree, i - 1);
	cout << endl;
	PrintCode(huffTree, i - 1);
}