#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>


//typedef int  TElemType;
const int UINT_MAX=1000;

typedef struct
{
   int weight;
   int parent,lchild,rchild;
}HTNode,* HuffmanTree;

typedef char **HuffmanCode;

//-----------全局變量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int *w,i,j,n;
char *z;
int flag=0;
 int numb=0;
// -----------------求赫夫曼編碼-----------------------

int min(HuffmanTree t,int i)
{ // 函數(shù)void select()調(diào)用
        int j,flag;
        int k=UINT_MAX; // 取k為不小于可能的值
        for(j=1;j<=i;j++)
                if(t[j].weight<k&&t[j].parent==0)
                k=t[j].weight,flag=j;
        t[flag].parent=1;
        return flag;
}

//--------------------slect函數(shù)----------------------
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1為最小的兩個(gè)值中序號(hào)小的那個(gè)
        int j;
        s1=min(t,i);
        s2=min(t,i);
        if(s1>s2)
        {
                j=s1;
                s1=s2;
                s2=j;
        }
}
// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HC
        int m,i,s1,s2,start;
        //unsigned c,f;
  int c,f;
        HuffmanTree p;
        char *cd;
        if(n<=1)
        return;//檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹
        m=2*n-1;
        HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號(hào)單元未用
        for(p=HT+1,i=1;i<=n;++i,++p,++w)
        {
                p->weight=*w;
                p->parent=0;
                p->lchild=0;
                p->rchild=0;
        }
        for(;i<=m;++i,++p)
        p->parent=0;
        for(i=n+1;i<=m;++i) // 建赫夫曼樹
        { // 在HT[1~i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為s1和s2
                select(HT,i-1,s1,s2);
                HT[s1].parent=HT[s2].parent=i;
                HT[i].lchild=s1;
                HT[i].rchild=s2;
                HT[i].weight=HT[s1].weight+HT[s2].weight;
        }
   // 從葉子到根逆向求每個(gè)字符的赫夫曼編碼
        HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
   // 分配n個(gè)字符編碼的頭指針向量([0]不用)
        cd=(char*)malloc(n*sizeof(char)); // 分配求編碼的工作空間
        cd[n-1]='\0'; // 編碼結(jié)束符
        for(i=1;i<=n;i++)
        { // 逐個(gè)字符求赫夫曼編碼
                start=n-1; // 編碼結(jié)束符位置
                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]=(char*)malloc((n-start)*sizeof(char));
     // 為第i個(gè)字符編碼分配空間
                strcpy(HC[i],&cd[start]); // 從cd復(fù)制編碼(串)到HC
        }
        free(cd); // 釋放工作空間
}


//--------------初始化赫夫曼鏈表---------------------------------
void Initialization()
{
        flag=1;
        int num;
        int num2;
        cout<<"下面初始化赫夫曼鏈表"<<endl<<"請輸入結(jié)點(diǎn)的個(gè)數(shù)n：";
        cin>>num;
        n=num;
        w=(int*)malloc(n*sizeof(int));
        z=(char*)malloc(n*sizeof(char));
        cout<<"\n請依次輸入"<<n<<"個(gè)字符(字符型)\n注意:必須以回車結(jié)束："<<endl;
        char base[2];
        for(i=0;i<n;i++)
  {
        cout<<"第"<<i+1<<"個(gè)字符:"<<endl;
        gets(base);
        *(z+i)=*base;
        }
        for(i=0;i<=n-1;i++)
        {
                cout<<setw(6)<<*(z+i);
        }
        cout<<"\n請依次輸入"<<n<<"個(gè)權(quán)值(\n注意:必須以回車結(jié)束)："<<endl;
        for(i=0;i<=n-1;i++)
        {
         cout<<endl<<"第"<<i+1<<"個(gè)字符的權(quán)值:";
         cin>>num2;
         *(w+i)=num2;
  }
        HuffmanCoding(HT,HC,w,n);
//------------------------打印編碼-------------------------------------------
        cout<<"字符對應(yīng)的編碼為:"<<endl;
        for(i=1;i<=n;i++)
        {
                //cout<<"字符"<<*(z+i-1)<<"的編碼";
                puts(HC[i]);
        }
//--------------------------將赫夫曼編碼寫入文件------------------------
        cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"...................."<<endl;

        FILE *htmTree;
        char r[]={' ','\0'};
        if((htmTree=fopen("htmTree.txt","w"))==NULL)
  {
  cout<<"can not open  file"<<endl;
  return;
  }

        fputs(z,htmTree);
        for(i=0;i<n+1;i++)
        {
         fprintf(htmTree,"%6d",*(w+i));
         fputs(r,htmTree);
  }
        for(i=1;i<=n;i++)
        {
         fputs(HC[i],htmTree);
         fputs(r,htmTree);
        }
        fclose(htmTree);
        cout<<"已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;
}

//---------------------獲取報(bào)文并寫入文件---------------------------------

void InputCode()
{
 //cout<<"請輸入你想要編碼的字符"<<endl;
 FILE *tobetran;
 char str[100];
 if((tobetran=fopen("tobetran.txt","w"))==NULL)
 {
  cout<<"不能打開文件"<<endl;
  return;
 }
 cout<<"請輸入你想要編碼的字符"<<endl;
 gets(str);
 fputs(str,tobetran);
 cout<<"獲取報(bào)文成功"<<endl;
 fclose(tobetran);
}

//---------------------編碼函數(shù)---------------------------------
void Encoding()
{
        cout<<"下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl;

        FILE *tobetran,*codefile;

        if((tobetran=fopen("tobetran.txt","rb"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
        }
        if((codefile=fopen("codefile.txt","wb"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
        }

        char *tran;
        i=99;
        tran=(char*)malloc(100*sizeof(char));

        while(i==99)
        {
                if(fgets(tran,100,tobetran)==NULL)
                {
                        cout<<"不能打開文件"<<endl;
                        break;
                }
                for(i=0;*(tran+i)!='\0';i++)
                {
                        for(j=0;j<=n;j++)
                        {
                                if(*(z+j-1)==*(tran+i))
                                {
                                  fputs(HC[j],codefile);
                                  if(j>n)
                                  {
                                   cout<<"字符錯(cuò)誤，無法編碼!"<<endl;
                                   break;
                                  }
                                }
                        }
                }
        }
        cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;
        fclose(tobetran);
        fclose(codefile);
        free(tran);
}


//-----------------譯碼函數(shù)---------------------------------
void Decoding()
{

 cout<<"下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl;
        FILE *codef,*txtfile;
        if((txtfile=fopen("\\Textfile.txt","w"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
        }
  //txtfile=fopen("Textfile.txt","w");
        if ((codef=fopen("codefile.txt","r"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
        }
  //codef=fopen("codefile.txt","r");
   char *work,*work2,i2;
  int i4=0,i,i3;
        unsigned long length=10000;
        work=(char*)malloc(length*sizeof(char));
  fgets(work,length,codef);
  work2=(char*)malloc(length*sizeof(char));
  i3=2*n-1;
  for(i=0;*(work+i)!='\0';i++)
  {
   i2=*(work+i);
   if(HT[i3].lchild==0)
   {
    *(work2+i4)=*(z+i3-1);
    i4++;
    i3=2*n-1;
    i--;
   }
   else if(i2=='0') i3=HT[i3].lchild;
   else if(i2=='1') i3=HT[i3].rchild;
  }
  *(work2+i4)='\0';
  fputs(work2,txtfile);
  cout<<"譯碼完成"<<endl<<"內(nèi)容寫入根目錄下的文件txtfile.txt中"<<endl<<endl;
  free(work);
  free(work2);
        fclose(txtfile);
        fclose(codef);

}


//-----------------------打印編碼的函數(shù)----------------------
void Code_printing()
{
        cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl;
        FILE * CodePrin,* codefile;
        if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
    return;
        }
        if((codefile=fopen("codefile.txt","r"))==NULL)
        {
                cout<<"不能打開文件"<<endl;
    return;
        }


        char *work3;
        work3=(char*)malloc(51*sizeof(char));
        do
        {
                if(fgets(work3,51,codefile)==NULL)
                {
                 cout<<"不能讀取文件"<<endl;
     break;
                }
    fputs(work3,CodePrin);
                puts(work3);
        }while(strlen(work3)==50);
        free(work3);

 /* int iNum=2,num=2;
        while((num=fscanf(codefile,"%d",iNum))!=NULL)
  {
  printf("%d",iNum);
  fprintf(CodePrin,"%d",iNum);
  }
*/
        cout<<"打印工作結(jié)束"<<endl<<endl;
        fclose(CodePrin);
  fclose(codefile);
}


//------------------------打印赫夫曼樹的函數(shù)-----------------------
void coprint(HuffmanTree start,HuffmanTree HT)
{

      if(start!=HT)
        {
   FILE * TreePrint;

   if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
   {cout<<"創(chuàng)建文件失敗"<<endl;
   return;
   }

            numb++;//該變量為已被聲明為全局變量
            coprint(HT+start->rchild,HT);
            cout<<setw(5*numb)<<start->weight<<endl;

      fprintf(TreePrint,"%d\n",start->weight);
            coprint(HT+start->lchild,HT);
            numb--;
   fclose(TreePrint);
        }
}

void Tree_printing(HuffmanTree HT,int w)
{
        HuffmanTree p;
        p=HT+w;
        cout<<"下面打印赫夫曼樹"<<endl;
        coprint(p,HT);
        cout<<"打印工作結(jié)束"<<endl;
}


//------------------------主函數(shù)------------------------------------
void main()
{
        char choice;
        while(choice!='q')
        {       cout<<"\n******************************"<<endl;
                cout<<" 歡迎使用赫夫曼編碼解碼系統(tǒng)"<<endl;
                cout<<"******************************"<<endl;
                cout<<"(1)要初始化赫夫曼鏈表請輸入'i'"<<endl;
    cout<<"(2)輸入要編碼的字符'w'"<<endl;
                cout<<"(3)要編碼請輸入'e'"<<endl;
                cout<<"(4)要譯碼請輸入'd'"<<endl;
                cout<<"(5)要打印編碼請輸入'p'"<<endl;
                cout<<"(6)要打印赫夫曼樹請輸入't'"<<endl;
                cout<<"(7)要離開請輸入'q'"<<endl;
                if(flag==0)cout<<"\n請先初始化赫夫曼鏈表,輸入'i'"<<endl;
                cin>>choice;
    switch(choice)
    {
    case 'i':
                    Initialization();
     break;
    case 'w':
      InputCode();
      break;
    case 'e':
      Encoding();
      break;
    case 'd':
      Decoding();
      break;
    case 'p':
      Code_printing();
      break;
    case 't':
                        Tree_printing(HT,2*n-1);
      break;
    case 'q':
       break;
    default:
      cout<<"input error"<<endl;
    }

        }
       free(z);
       free(w);
       free(HT);
}