#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
using namespace std;
typedef struct{// 哈夫曼樹和哈夫曼編碼的存儲表示
unsigned int weight;
unsigned int parent,lChild,rChild;
}HTNode, *HuffmanTree;// 用動態數組存儲哈夫曼樹
typedef struct{
     char ch;
     char* hufCh;
}HuffmanCode;//用動態數組存儲哈夫曼編碼表
typedef struct{// 權值字符結點
char ch;
int wt;
}wElem;// 動態分配數組存儲讀入字符與權值
void HuffmanCoding(HuffmanTree &,HuffmanCode *,wElem *,int);//構造哈夫曼樹HT,并求哈夫曼編碼，將結果存入hufTree.txt
void DeCoding(HuffmanTree,HuffmanCode *,const char*,const int);//對文件里的代碼進行譯碼,將結果存入textfile.txt                                                                
void SelectTwoNode(HuffmanTree,int,int&,int&);//選擇兩個最小的結點
void HuffmanCoding(HuffmanTree &HT,HuffmanCode* HC,wElem* w,int n)//構造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HC
{
if(n<=1)
   return;
int m=2*n-1;                       // m為結點數目
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));            //未用0號單元
HuffmanTree p=HT;
p++;                      //p指向HT的第1號單元
int i=0,ww=0;           //ww為wElem* w的下標 
for(i=1;i<=n;i++,p++,ww++) 
{
   p->weight=w[ww].wt;
   p->parent=p->lChild=p->rChild=0;
}                                                //初始化
for(;i<=m;++i,++p)
{
   p->weight=p->parent=p->lChild=p->rChild=0;
}                                
int s1=0,s2=0;                           //s1,s2為HT[1 .. i-1]中parent為0且weight最小的兩個結點
for(i=n+1;i<=m;++i)
{
   SelectTwoNode(HT,i-1,s1,s2); 
   HT[s1].parent=i;              // 標記 parent               
   HT[s2].parent=i;                // 標記 parent             
   HT[i].lChild=s1;               // 標記左孩子
   HT[i].rChild=s2;                // 標記右孩子
   HT[i].weight=HT[s1].weight+HT[s2].weight;
}
char* cd=new char[n];              //分配編碼的空間
cd[n-1]='\0';                       //結束符
int c=0;
int f=0;
for(i=1;i<=n;++i)                //開始編碼
{
   int start=n-1;                     //編碼結束符位置
   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].ch=w[i-1].ch;     //復制字符
   HC[i].hufCh=(char*)malloc((n-start)*sizeof(char));    //為第i個字符編碼分配空間
   strcpy(HC[i].hufCh,&cd[start]);               //從cd復制編碼到HC
}
delete []cd;                     //釋放空間
}

// -----------------------選擇兩個最小的結點,序號分別放在s1和s2中--------------------
void SelectTwoNode(HuffmanTree HT,int i,int &s1,int &s2)
{
unsigned int sm1,sm2;
s1=1;                //從序號為1的權值開始 
s2=1;
int m=0;                //最小權值的序號臨時變量
for(m=1;m<=i;m++)           //第一遍中第一個parent為0的結點
{
   if(HT[m].parent!=0) 
    continue;
   else
   {
    sm1=HT[m].weight;
    s1=m;
    break;
   }
}
for(int j=m+1;j<=i;j++)                     // 第一遍選第一個最小的
{
   if(HT[j].parent!=0) 
    continue;
   else
   {
    if(sm1>HT[j].weight) 
    {
     sm1=HT[j].weight;
     s1=j;
    }
   }
}
for(m=1;m<=i;m++) //第二遍中第一個parent為0的結點
{
   if(HT[m].parent!=0) 
    continue;
   else 
   {
    sm2=HT[m].weight;
    s2=m;
    if(s2==s1) 
     continue;
    else 
     break;
   }
}
for(int k=m+1;k<=i;k++) //第二遍選第二個最小的
{
   if(HT[k].parent!=0) 
    continue;
   else
   {
    if((HT[k].weight<sm2)&&(k!=s1)) //保證sm1!=sm2
    {
     sm2=HT[k].weight;
     s2=k;
    }
   }
}
}
//-------------------譯碼實現，在 HC 里進行逐字掃描比較求子串相應的字符--------------------------------------
void DeCoding(HuffmanTree HT,HuffmanCode *HC,const char* iFile,const int n)
{// 參數n為字符個數p=2*n-1就為HT的結點數目.HT[p]就為HT的根.
ifstream fIn(iFile,ios::in);
char inBuf='1';
ofstream fout("textfile.txt",ios::out);
char* cd=new char[n];   // 儲存字串的空間
int start=0;              //譯碼開始標記
int p=2*n-1;          //根下標
int iHC=1;                // 用于掃描 HC 的循環變
while(fIn.get(inBuf))   // 循環讀入 \'0\' 或 \'1\' 或 \'\\n\'
{
   if(inBuf=='0')
   {
    if(HT[p].lChild!=0)
    {
     cd[start++]=inBuf;   //使inBuf進cd*
     p=HT[p].lChild;      //進入左子樹
     continue;
    }
    else
    {
     cd[start++] = '\0';
     for(iHC=1;iHC<=n;iHC++) //尋找與子串匹配的字符
     {
      if(strcmp(HC[iHC].hufCh,cd)==0)
      {
       fout<<HC[iHC].ch;
       break;     //找到則跳出for循環
      }
      else 
       continue;
     }
     start=0;
     cd[start++]=inBuf;     //為讀下一子串做準備
     p=HT[2*n-1].lChild; //此時p指向root的leftchild
    }
   }
   else 
    if(inBuf=='1')
    {
     if(HT[p].rChild!=0)
     {
      cd[start++]=inBuf;   //讓inBuf進入cd*
      p=HT[p].rChild;      //進入左子樹
      continue;
     }
     else
     {
      cd[start++]='\0';      //子串結束符
      for(iHC=1;iHC<=n;iHC++) //尋找與子串匹配的字符
      {
       if(strcmp(HC[iHC].hufCh,cd)==0)
       {
        fout<<HC[iHC].ch;
        break; // 找到則跳出for循環
       }
       else
       {  
        continue;
       }
      }
      start=0;
      cd[start++]='1';       //準備讀下一個子串
      p=HT[2*n-1].rChild; //p指向root的rightchild
     }
    }
     else 
      if(inBuf=='\n')
     {
      continue;
            }
}
cd[start]='\0';
for(iHC=1;iHC<=n;iHC++) //尋找與子串匹配的字符
{
   if(strcmp(HC[iHC].hufCh,cd)==0)
   {
    fout<<HC[iHC].ch;
    break; //找到則跳出for循環
   }
   else 
   {   
    continue;
   }  
}
     delete [] cd; //釋放空間
fIn.close();   //關閉文件
fout.close(); //關閉文件
}              
int main( )
{
     char* wFileName=new char[128];
cout<<endl<<"請輸入字符存放位置及文件名: ";
cin >> wFileName;
ifstream hufInPut(wFileName,ios::in );//用hufInPut打開外部文件 
if(!hufInPut)
   cerr << "文件不存在" << endl;
int hufNum=0;
hufInPut>>hufNum; //讀入字符集大小n到hufNum
//-------------------輸出基本信息--------------------------------
cout<<"字符總數: " << hufNum << endl;
cout<<" 字符    權值" << endl;
wElem* hufW=new wElem[hufNum]; //分配n個字符和n個權值的儲存空間
for(int ii=0;ii<hufNum;ii++)
{
// ------------------循環讀入字符及其對應的權值--------------------------
   hufInPut >> hufW[ii].ch >> hufW[ii].wt;
   cout << setw(4) << hufW[ii].ch << setw(8) << hufW[ii].wt << endl;
}
cout<<endl;
hufInPut.close();     //關閉存放字符和權值的文件
delete [] wFileName; //釋放空間
HuffmanTree hufT;
HuffmanCode* hufC=(HuffmanCode* )malloc((hufNum+1)*sizeof(HuffmanCode)); //分配n個字符編碼的頭指針向量
HuffmanCoding(hufT,hufC,hufW,hufNum );//編碼
// ------------------用hufTreeOutPut把哈夫曼樹HT,HC輸出到文件hufTree.txt中------------------------------------------
ofstream hufTreeOutPut( "hufTree.txt" , ios::out );
hufTreeOutPut << "++ 哈夫曼樹 ++++++++++++++++++++++++++++" << endl << setw(9) << "            權值 " <<"     雙親 " << "   左孩子 " << " 右孩子 "<< endl;
for(int tOut=1;tOut<=2*hufNum-1;tOut++)
{
   hufTreeOutPut<<setw(6)<<tOut<<setw(8)<<hufT[tOut].weight<<setw(8)<<hufT[tOut].parent<<setw(8)<<hufT[tOut].lChild << setw( 8 ) << hufT[ tOut ].rChild << endl;
}
hufTreeOutPut << "------------------------------------------ " << endl << endl << "++ 哈夫曼編碼 +++++++++++++++++++++++++++ " << endl;
//-----------向屏幕輸出編碼過的編碼基本信息----------------------------------------------------------------------
     cout << "將字符編碼后, 代碼為: " <<endl;
     cout << " 字符    代碼" << endl;
for( int cOut=1;cOut<=hufNum;cOut++)
{
   hufTreeOutPut << "    " << hufC[cOut].ch<< " +++++>> "<<hufC[cOut].hufCh<<endl;
//-----------------向屏幕輸出編碼過的編碼內容----------------------------------------------------------
   cout<<setw(4)<<hufC[cOut].ch<<setw(8)<<hufC[cOut].hufCh<<endl;
}
cout<<"+++++++轉換后的代碼存儲在文件<hufTree.txt>中+++++++ "<<endl;
cout<<endl<<endl;
hufTreeOutPut <<"++ 轉換成功!++++++++++++++++++++" << endl;
hufTreeOutPut.close(); //輸出完畢，關閉文件
delete [] hufW; //釋放內存
//-------------------向屏幕輸出編碼過的代碼內容------------------------------------- 
     char* cFileName=new char[128]; // 存放文件名的空間
cout << endl<< "請輸入存儲有代碼的文件位置及名稱: ";
cin >> cFileName;
ifstream codeIn(cFileName,ios::in );
if(!codeIn) 
   cerr << "file can not be opened" << endl;
char codeInBuf='0';
cout<<"\n待編譯的代碼為:\n---------------------------------------------"<<endl;
while( codeIn.get( codeInBuf ) ) 
cout << codeInBuf;
cout<<"\n---------------------------------------------";
     cout << endl << endl; 
     DeCoding(hufT,hufC,cFileName,hufNum);           //譯碼
//--------------- 向屏幕輸出譯碼后的內容----------------------------------------------------
cout << "譯碼為: " << endl;
cout<<"---------------------------------------------\n";
ifstream dcodeIn("textfile.txt",ios::in);
if( !dcodeIn ) 
   cerr <<"file can not be opened"<<endl;
char dcodeInBuf='0';
while( dcodeIn.get(dcodeInBuf)) 
   cout <<dcodeInBuf;
     cout<<endl;
cout<<"---------------------------------------------";
     cout<<"\n********譯碼存儲在文件textfile.txt中*******"<<endl;
cout << endl<<endl;
return 0;
}