cpp1.cpp

哈夫曼吗 完整的哈夫曼码的数据结构编程 功能强大

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