Huffman编码及数据结构介绍

Huffman编码及数据结构介绍

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