#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\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();
}
