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

좋은 웹페이지 즐겨찾기