huffmantree1.cpp

一个关于数据结构哈夫曼编/译码的程序

#include <iostream.h>
#include <fstream.h>
#include <string.h>

class Data {
public:
	char ch;
	Data(){
		ch = NULL;
	}
};

typedef class Huffman {
public:
	Data data;
	int weight;
	int parent, lchild, rchild;
	Huffman(){
		weight = parent = lchild = rchild = NULL;
	}
} * HuffmanTree;

typedef char ** HuffmanCode;

// 在数组中选择两个小的权的数据
void Select(int *tw, int n, int &s1, int &s2)
{
	// 建立临时变量temp_w,用来存放最小的weight
	int temp_w, i = 1;
	while(!tw[i])
	{
		i++;
	}
	temp_w = tw[i];
	s1 = i;
	// 第一遍先确定s1
	for(; i<=n; i++)
	{
		if(temp_w > tw[i])
		{
			if(tw[i] != NULL)
			{
				temp_w = tw[i];
				s1 = i;
			}// ifin
		}// if
	}//for
	i = 1;
	while(!tw[i] || i == s1)
	{
		i++;
	}
	temp_w = tw[i];
	s2 = i;
	for(; i<=n; i++)
	{
		if(i == s1)
			goto loop;
		if(temp_w > tw[i])
		{
			if(tw[i])
			{
				temp_w = tw[i];
				s2 = i;
			}// ifin
		loop:;
		}// if
	}// for
	// 使权小的放到s1
	if(tw[s1]>tw[s2])
	{
		temp_w = s1;
		s1 = s2;
		s2 = temp_w;
	}// if
	// 取得两个小的位置后,将备用temp_array_w位置上的权抹去,表示已经被访问
	tw[s1] = tw[s2] = NULL;
	tw[0] = tw[0]-2;
}

void Initialization (HuffmanTree &HT, HuffmanCode &HC, int n)
{
	// 给文件一编码个数的个标记,放在HT[0]行中
	HT[0].weight = n;
	HT[0].data.ch = 3;
	int i;
	// 建立一个辅助建立树用的权组
	int *temp_array_w = new int[2*n];
	// 初始化数组里的权都为0
	for(i = 1; i<=2*n -1; i++)
		temp_array_w[i] = 0;
	for(i = 1; i<=n; i++)
	{
		cout << "输入字符: ";
		cin >> HT[i].data.ch;
		if(HT[i].data.ch == '\32')
			HT[i].data.ch = '|';
		cout << "输入权: ";
		cin >> HT[i].weight;
		// 把辅助权组赋和权一样的值
		temp_array_w[i] = HT[i].weight;
		// 用不用的0号单元记录个数
		temp_array_w[0] = i;
	}// for
	// 建立标志s1和s2
	int s1, s2;
	s1 = s2 = NULL;
	// 建立huffman树
	for(i = n + 1; i<=2*n - 1; i++)
	{
		Select(temp_array_w, i-1, s1, s2);
		cout << s1 << "//" << s2 << endl;
		HT[i].weight = temp_array_w[i] = HT[s1].weight + HT[s2].weight;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
		HT[s1].parent = HT[s2].parent = i;
		HT[i].data.ch = '#';
	}// for
	cout << "\tData\tweight\tparent\tlchild\trchild" << endl;
	for(i = 1; i<=2*n - 1; i++)
		cout << "\t" << HT[i].data.ch << "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl;
	// 建立好了树后打印输出到文件humTree中
	ofstream HumTreeOut("humTree.dll");
	// 把个数记录到文件开始
	HumTreeOut << HT[0].weight << endl;
	for(i = 1; i<=2*n -1; i++)
	{
		HumTreeOut << HT[i].data.ch << "\n" << HT[i].weight << "\n" << HT[i].parent << "\n" << HT[i].lchild << "\n" << HT[i].rchild << endl;

	}
	HumTreeOut.close();
}// void

// 通过树给字符编码,并且把编码输入到CodeFile中
void Encoding (HuffmanCode &HC, HuffmanTree &HT, int n, ifstream &tobetranfile)
{
	char *cd = new char[n];
	cd[n-1] = '\0';
	int i = 1;
	for(; i<=n; i++)
	{
		int start = n -1;
		int c, f;
		for(c = i, f = HT[i].parent; f!=0; c = f, f = HT[f].parent)
			if(HT[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		HC[i] = new char[n-start];
		strcpy(HC[i], &cd[start]);
	}
	delete cd;
	char temp_file_ch;
	ofstream CodeOut("CodeFile.txt", ios::ate); // ios::ate表示一个open模式,是在文件后面续写
	while(!tobetranfile.eof()) // 一旦文件到了末尾,eof()函数会返回一个非零值
	{
		tobetranfile.get(temp_file_ch);
		for(i = 1; i<=n; i++)
		{
			if(temp_file_ch == HT[i].data.ch) // 如果相等,便用编码替换
				CodeOut << HC[i];
		}
	}
	CodeOut.close();
}

void Decoding (HuffmanTree &HT, ifstream &CodeFile, int n)
{
	ofstream TextOut("TextFile.txt", ios::ate);
	char temp_code_ch;
	int temp_num = 2*n - 1;
	while(!CodeFile.eof())
	{
		CodeFile.get(temp_code_ch);
		if(temp_code_ch == '1')
			if(!HT[temp_num].rchild)
			{
				TextOut << HT[temp_num].data.ch;
				temp_num = 2*n - 1;
			}
			else
			{
				temp_num = HT[temp_num].rchild;
				if(!HT[temp_num].rchild) //其实随便一个孩子为空就代表是叶子节点
				{
					TextOut << HT[temp_num].data.ch;
					temp_num = 2*n - 1;
				}
			}
		else
			if(!HT[temp_num].lchild)
			{
				TextOut << HT[temp_num].data.ch;
				temp_num = 2*n - 1;
			}
			else
			{
				temp_num = HT[temp_num].lchild;
				if(!HT[temp_num].lchild) //其实随便一个孩子为空就代表是叶子节点
				{
					TextOut << HT[temp_num].data.ch;
					temp_num = 2*n - 1;
				}
			}
	}
	TextOut.close();
	cout << "已经翻译到Text.txt文件中" << endl;
}

// 通过已存在的humtree.dll建立新的树
bool CreatNewHum(HuffmanTree &HT, int &n)
{
		char *ch_name = new char[30];
		// 存放从文件中读取的字符
		int temp_n;
		char temp_ch;
		int i = 1;
		cout << "Please Inputing the File name :";
		cin >> ch_name;
		ifstream HuffmanTreeIn(ch_name);
		if(HuffmanTreeIn.fail())
		{
			HuffmanTreeIn.close();
			cout << "不能打开文件" << endl;
			return false;
		}
		// HuffmanTree HT_TEMP = HT;
		// HuffmanTreeIn.getline(temp_line, 9);
		HuffmanTreeIn >> temp_n; // 一个单词为单位输入
		HuffmanTreeIn.get(temp_ch);
		// HuffmanTreeIn.seekg(1);
		HT = new Huffman[2*temp_n];
		// delete HT_TEMP;
		// 通过读入文件中的数据给HT赋值
		/*
			for(;i<20;i++)
		{
			HuffmanTreeIn.get(temp_ch);
			cout << temp_ch;
		}
		//*/
		//*
		int j = 1;
		while(!HuffmanTreeIn.eof())
		{	
			if(i%5 == 1)
			{
				HuffmanTreeIn >> HT[j].data.ch;
				HuffmanTreeIn.get(temp_ch); // 用于回收回车符号
				i++;
			}
			if(i%5 == 2)
			{
				HuffmanTreeIn >> HT[j].weight;
				HuffmanTreeIn.get(temp_ch);
				i++;
			}
			if(i%5 == 3)
			{
				HuffmanTreeIn >> HT[j].parent;
				HuffmanTreeIn.get(temp_ch);
				i++;
			}
			if(i%5 == 4)
			{
				HuffmanTreeIn >> HT[j].lchild;
				HuffmanTreeIn.get(temp_ch);
				i++;
			}
			if(i%5 == 0)
			{
				HuffmanTreeIn >> HT[j].rchild;
				HuffmanTreeIn.get(temp_ch);
				i++;
			}
		
			// i自加到5的倍数后j++
			if(i%5 == 1)
				j++;
			// 防止输入最后一个定位符号
			if(i > (2*temp_n -1)*5)
				break;
		}// while
		//*/
		// 从指定文件里读入树型
		HuffmanTreeIn.close();
		n = temp_n;
		return true;
}

void PrintCode ()
{
	char *name_ch = new char[51];
	ifstream FileIn("CodeFile.txt");
	ofstream FileOut("CodePrin.txt", ios::ate);
	if(FileIn.fail())
		cout << "文件打开错误!" << endl;
	while(!FileIn.eof())
	{
		FileIn.getline(name_ch, 51);
		cout << name_ch << endl;
		FileOut << name_ch << endl;
	}
	FileIn.close();
	FileOut.close();
}

void TreePrint ()
{
}

void TitalPrinT() {
	cout << "\t=========================================================" << endl;
	cout << endl;
	cout << "\t=\t\t\tHUFFMANTREE\t\t\t=" << endl;
	cout << endl;
	cout << "\t=\t\tI:INITIAL A HUFFMAN TREE\t\t=" << endl;
	cout << endl;
	cout << "\t=\t\tE:ENCODEING THE DATA\t\t\t=" << endl;
	cout << endl;
	cout << "\t=\t\tD:DECODEING THE DATA\t\t\t=" << endl;
	cout << endl;
	cout << "\t=\t\tP:PRINT\t\t\t\t\t=" << endl;
	cout << endl;
	cout << "\t=\t\tQ:QUIT\t\t\t\t\t=" << endl;
	cout << endl;
	cout << "\t=========================================================" << endl;
}
// 把几个运算的函数全都放到一个里面去,主函数main就只调用下运算函数

void ComputeHuffman ()
{
	// 建立个临时输入存放选项的变量
	char temp_input = NULL;
	TitalPrinT();
	// 记录要给几个编码
	int n = 0;
	// 先是主体界面 直到按Q才退出
	while(temp_input != 'Q')
	{
		// 建立操作变量
		char temp_choise = 0;
		HuffmanTree HT;
		HuffmanCode HC;
		// 用switch/case来判断到底按了哪个选项
		cout << "CHOOSE WHICH DO YOU SELECT..." << endl;
		cin >> temp_input;
		switch(temp_input)
		{
		case 'I':
			cout << "How many numbers need to be initialized: ";
			cin >> n;
			// 建立数组存放数据
			HT = new Huffman[2*n];
			Initialization (HT, HC, n);
			break;
		case 'E':
			{
				//*
				cout << "Inputing the HumffmanTree from the (F)ile or (M)emory : ";
				cin >> temp_choise;
				switch(temp_choise)
				{
				case 'F': 
					if(!CreatNewHum(HT, n))
						continue;
					break;
				case 'M':
					// 什么都不做
					break;
				default:
					cout << "Please Pess F or M..." << endl;
					continue;
				}// switch
				//*/
				cout << "Translating in (F)ile or (P)ressing: ";
				cin >> temp_choise;
				switch(temp_choise)
				{
				case 'F':
					break;
				case 'P':
					{
						cout << "由于本人精力限制,现在最多只能输入80个字符" << endl;
						char *temp_press_word = new char[81];
						cin >> temp_press_word;
						// 可以覆盖以前的ToBeTran.txt文件
						ofstream CodeFileOut("ToBeTran.txt");
						CodeFileOut << temp_press_word;
						break;
					}
				}
				HC = new char*[n+1];
				ifstream ToBeTranFile("ToBeTran.txt");
				Encoding(HC, HT, n, ToBeTranFile);
				ToBeTranFile.close();
				for(int i = 1; i<=n; i++)
					cout << HT[i].data.ch << "<-->" << HC[i] << endl;
			}
			// 利用建立好的huffman树(如果不在内存则从文件humTree中读入),对文件
			// ToBeTran中的正文进行编码,然后将结果寸入CodeFile.txt文件中.
			break;
		case 'D':
			{
				// 可以通过不同的树来翻译
				cout << "Inputing the HumffmanTree from the (F)ile or (M)emory : ";
				cin >> temp_choise;
				switch(temp_choise)
				{
				case 'F': 
					{
					if(!CreatNewHum(HT, n))
						continue;
					HC = new char*[n+1];
					/*
					ifstream ToBeTranFile("ToBeTran.txt");
					Encoding(HC, HT, n, ToBeTranFile);
					ToBeTranFile.close();
					*/
					}
					break;
				case 'M':
					// 什么都不做
					break;
				default:
					cout << "Please Pess F or M..." << endl;
					continue;
				}// switch
				ifstream CodeFile("CodeFile.txt");
				Decoding(HT, CodeFile, n);
				CodeFile.close();
			}
			// 利用建立好的haffman树将文件codefile中的代码进行翻译.结果寸入文件TextFile.txt中
			break;
		case 'P':
			PrintCode();
			// 打印代码,50个每行,并且将此字符形式的编码文件写入CodePrin中
			break;
		case 'T':
			// 印huffman树,将已经在内存的huffman树以直观的方式显示,同时将此字符形式的huffman树写
			// 入文件TreePrint中
			break;
		case 'Q':
			return;
		default:
			cout << "Please inputing in \" I E D Q \"..." << endl;
			continue;
		}// switch
		// 回到主菜单
		TitalPrinT();
	}// while
}// ComputerHuffman

void main()
{
	ComputeHuffman();
}