| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2958 人关注过本帖
标题:哈夫曼编码问题
取消只看楼主 加入收藏
JJST
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2016-10-13
结帖率:0
收藏
 问题点数:0 回复次数:0 
哈夫曼编码问题
代码由bug求改进

#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
#define Max 200 //最大结点数目
#define INT 10000
char ch[Max]; //叶子结点信息(字符)
int i,w[Max]; //w为输入的权值数组
typedef struct{
 unsigned int weight; //权值
 unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。
     int s1,s2,j,min1,min2;
     if(n<=1)  return;
     int m=2*n-1;
     HT=new HTNode[m+1];//0号单元未用
     for(i=1;i<=n;++i) //哈夫曼树叶子结点的初始化
    {
          HT[i].weight=w[i];  HT[i].parent=0;
          HT[i].lchild=0;     HT[i].rchild=0;
      }
     for(i=n+1;i<=m;++i) //非叶子结点的初始化
     {
           HT[i].weight=0;   HT[i].parent=0;
        HT[i].lchild=0;   HT[i].rchild=0;
     }
     for(i=n+1;i<=m;++i) //建哈夫曼树
     { //在HT[1..i-1]选择parent为0且weight最小的两个结点S1和S2
          min1=min2=INT;
          for(j=1;j<i;j++)
           if(HT[j].parent==0&&(HT[j].weight<min1))
           {   
           min1=HT[j].weight;  
           s1=j;
        }
          for(j=1;j<i;j++)
          if(HT[j].parent==0&&(HT[j].weight<min2)&&j!=s1)
          {   min2=HT[j].weight;  
            s2=j;   
        }
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
           HT[i].weight=HT[s1].weight+HT[s2].weight;
           ch[i]='?';//非叶子结点的结点字符
        }
 //从叶子到根逆向求每个字符的哈夫曼编码
         HC=new char*[n+1]; //分配n个字符编码的头指针向量
        char *cd=new char[n]; //分配求编码的工作空间
         HT[i].lchild=s1; HT[i].rchild=s2;
         cd[n-1]='\0';  //编码结束符
         for(i=1;i<=n;i++)  //逐个字符求哈夫曼编码
         {
          int c,f,start=n-1;//编码结束符位置
          for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
                  /*cd[--start]=(HT[f].lchild==c?'0':'1';*/ //从叶子到根逆向求编码
               if(HT[f].lchild==c)
            cd[--start]='0';
           else
            cd[--start]='1';
           HC[i]=new char[n-start];//为第i个字符编码分配空间
           strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC
         }
         delete cd;
}
void Initialization(HuffmanTree &HT,HuffmanCode &HC,int &n)//初始化,注意加引用符号
{
  char c;
     ifstream fin("hfmTree.txt",ios::in);//读出
     if(fin.fail()) //若不存在此文件,则从终端读入
  {
         cout<<"请输入字符个数n:";
   cin>>n;
   cout<<"请输入字符及相应权值:"<<endl;
   for(i=1;i<=n;i++)
   {
    //getchar()是在输入缓冲区顺序读入一个字符(包括空格、回车和tab)。
        getchar(); //取消换行符
    //getchar每次只能读取一个字符.如果需要取消'\n'的影响,可以用getchar();来清除,
    //这里getchar();只是取得了'\n'但是并没有赋给任何字符变量,所以不会有影响,相当于清除了这个字符.
        ch[i]=getchar(); //保证空格读进
        cin>>w[i];
   }
   HuffmanCoding(HT,HC,w,n);
   ofstream fout("hfmTree.txt",ios::out);//写入
   cout<<n<<endl;
   for(i=1;i<=2*n-1;i++)//写入字符,权值,父结点,左右孩子
      fout<<ch[i]<<" "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
   for(i=1;i<=n;i++)//写入字符及相应的编码
      fout<<ch[i]<<"  "<<HC[i]<<endl;
         fout.close();
  }
   else{   //如果文件存在,即读到内存中
      fin>>n;
      for(i=1;i<=2*n-1;i++)
     {
        fin.get(ch[i]);
        fin>>HT[i].weight>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
        fin.get(c);
     }
       for(i=1;i<=n;i++)
          {  
            fin.get(ch[i]);
               fin>>HC[i];
               fin.get(c);
           }
      }
     fin.close();
}
void Encoding(HuffmanCode & HC,int n) //编码
{
     int i,j;
     string str,str1;
     ifstream fin("ToBeTran.txt",ios::in);//打开文件
     ofstream fout("CodeFile.txt",ios::out);
     if(fin.fail())
      cout<<"文件ToBeTran.txt打开失败!"<<endl;
    getline(fin,str);//读入一行,可以读入空格
     while(!fin.eof())//文件不结束
     {
          getline(fin,str1);
          str=str+str1;
     }
       fin.close();
     for(i=0;str[i]!='\0';i++)//编码过程,一个字符一个字符来
     {   
          j=1;
          while(ch[j]!=str[i]&&j<=n) j++;
          if(j<=n)  fout<<HC[j];
     }
    fout<<endl;
     fout.close();
}
void Decoding(HuffmanTree HT,int n)//译码
{
  int j,len,m;
  string str;
  m=2*n-1;
  ifstream fin("CodeFile.txt",ios::in);
  ofstream fout("TextFile.txt",ios::out);
  if(fin.fail())
  {
   cout<<"文件CodeFile.txt打开失败!"<<endl;
   return ;
  }
   fin>>str;
   fin.close();
   len=str.size();
   i=0;j=m;
  while(i<len)
  { //从根出发,按字符'0'或'1'确定找左孩子或右孩子,直至叶子结点
   if(str[i]=='0')
         j=HT[j].lchild;
   else j=HT[j].rchild;
   if(HT[j].lchild==0)
   {  fout<<ch[j];  j=m; }
   i++;
  }
  fout<<endl;
}
void Print(HuffmanTree HT,int n)//打印代码文件
{
     int i;
     char str[Max];
     ifstream fin("CodeFile.txt",ios::in);
     ofstream fout("CodePrin.txt",ios::out);
     if(fin.fail())
      cout<<"文件CodeFile.txt打开失败!"<<endl;
     fin>>str;
     cout<<"毎行50个代码形式的编码如下:"<<endl;
     for(i=0;i<strlen(str);i++)
     {
          if(i%50==0&&i!=0) //毎50以换行
          {
               cout<<endl; fout<<endl;
         }
      cout<<str[i];fout<<str[i];
     }
    cout<<endl;fout<<endl;
      fin.close(); fout.close();
}
//非叶子结点用权值表示,叶子结点用字符表示
void PrintTree(HuffmanTree &HT,int &n)
{
 ofstream fout("TreePrint.txt",ios::out);//写入文件
 int l,j,m=0,k=1,q=0,p=0,r=1;//k 表示层数,r表示每层的结点数
 for(i=1;i<=2*n-1;i++)
    if(HT[i].parent==0)//找根结点的权值
     m=HT[i].weight;
 for(l=m;l>0;l--)  
   for(i=1;i<=2*n-1;i++)
   if(HT[i].weight==l)
   {   
    for(j=0;j<k;j++)
    { cout<<"   "; fout<<"   "; }//控制每层前面的空格
    if(ch[i]!='?') //如果是叶子结点就直接输出,否则输出权重
    {
     if(ch[i]==' ')  ch[i]='#';//标记为空的字符
     {  cout<<ch[i]<<endl; fout<<ch[i]<<endl; }
    }
    else
    {   cout<<HT[i].weight<<endl; fout<<HT[i].weight<<endl;  p++; }//p 表示每层的非叶子结点数
       q++;//q 记录每层的结点数目
       if(q==r) { k++; r=2*p; p=0; q=0; } //如果该层的结点满了,就到下一层,即k+1
   }   
}
int main()
{
 HuffmanTree HT;
 HuffmanCode HC;
 char c;
 int n;
 HT=new HTNode[Max];
 HC=new char*[Max];
 for(int i=1;i<=Max;i++)//初始化
 HC[i]=new char[20];
 cout<<"-----------------------欢迎进入哈夫曼的编/译码系统---------------------------"<<endl;
 cout<<"|                 菜单如下:"<<endl;                                      
 cout<<"|                 1、初始化"<<endl;
 cout<<"|                 2、编码"<<endl;
 cout<<"|                 3、译码"<<endl;
 cout<<"|                 4、打印代码文件"<<endl;
 cout<<"|                 5、打印哈夫曼树"<<endl;
 cout<<"|                 6、退出"<<endl;
 cout<<"-----------------------------------------------------------------------------"<<endl;
  while(c!='Q')
 {
     cout<<"请选择操作:";
  cin>>c;
  switch(c)
  {
  case '1': Initialization(HT,HC,n);
               cout<<"哈夫曼树成功存入文件hfmTree中!"<<endl;
      break;
  case '2': Encoding(HC,n);
         cout<<"对文件ToBeTran的编码结果成功存入文件CodeFile中!"<<endl;
      break;
  case '3': Decoding(HT,n);
         cout<<"对文件CodeFile的译码结果成功存入文件TextFile中!"<<endl;
      break;
  case '4': Print(HT,n);
         cout<<"毎行50个代码形式的编码结果成功写入文件CodePrin中!"<<endl;
      break;
  case '5': cout<<"哈夫曼树的凹入表示法如下:"<<endl;
         PrintTree(HT,n);
         cout<<"哈夫曼树以凹入表形式成功写入文件TreePrint中!"<<endl;
  default: break;
  }
  }
 return 0;
}
搜索更多相关主题的帖子: 编码 INT 字符 for cout 
2017-06-28 14:04
快速回复:哈夫曼编码问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.047057 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved