c++ 哈夫曼数据结构-哈夫曼编译码，存储结构，编译码方法

问题描述

哈夫曼编译码，存储结构，编译码方法

求大神解答，编码跟译码应该怎样存储，编译码方法

#include
#include
using namespace std;
#define M 127
#define maxvalue 200000
struct CHARACTER//字母结构体
{char data;
int count;
}character1[M],character2[M],*character3;

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

typedef struct CNode{
char co[20];
int start;
}codeNode;

typedef char **HuffmanCode;
HuffmanTree HT; //代表赫夫曼树
HuffmanCode HC; //代表赫夫曼编码

void savecharacter(CHARACTER character[])//保存字母信息
{
ofstream fout("txt1.txt",ios::out|ios::binary);
for(int i=0;i<M;i++)
fout.write((char*)&character[i], sizeof character[i]);
for(i=0;i<M;i++)
cout<<character[i].data<< " "<<character[i].count<<" ";
fout.close();
}

CHARACTER * readcharacter()//读取字母信息
{
ifstream fin("txt1.txt",ios::in|ios::binary);
for(int i=0;i<M;i++)
{fin.read((char*)&character2[i], sizeof character2[i]);
cout<<character2[i].data<<" "<<character2[i].count<<" "; }
return character2;
}

void initcharacter()
{ for(int i=0;i<M;i++)//初始化字母信息
{
character1[i].data=i;
character1[i].count=0;
}
}

CHARACTER * tongji(CHARACTER character[])//统计字符的个数及权值
{cout<<endl;
ifstream fin("txt.txt");
char ch;
int i=0;
while((ch=fin.get())!=EOF){//读到文件结尾为EOF标志
for(i=0;i<M;i++)
{
if(ch==character[i].data){character[i].count++;}
}
cout<<ch;
}
return character;
}

int countcharacter(CHARACTER character[])//统计文件中一共有多少个字符
{ int countchar=0;
int j=0;
int p1,p2;
p1=p2=0;

for(int i=0;i<M;i++)
{if(character[i].count!=0)
    countchar++;
}
    HTNode HH[2*M-1];//建立2*M-1大小的结构体数组
      cout<<endl;
  for( i=1;i<=M;i++)
  {
   if(character[i].count!=0)
   {
   HH[j].c=character[i].data;
   HH[j].weight=character[i].count;

   cout<<"字符"<<HH[j].c<<"权值  "<<HH[j].weight<<endl;
   j++;
   }
  }

return countchar;

}

void select_min(HuffmanTree ht,int k,int * x1,int * x2)
{
*x1=*x2=0;
int i,j=0;
int min=1000;
for(i=0;i<k;i++)//找最小权值

     {if(ht[i].weight<min&&ht[i].parent==0)
              {
                j=i;
                min=ht[i].weight;
              }
     }
      *x1=j;
      min=10000;
      for(i=0;i<k;i++)
      {if(ht[i].weight<min&&i!=*x1&&ht[i].parent==0)
      {j=i;min=ht[i].weight;}
      }
      *x2=j;

       cout<<*x1<<" "<<*x2<<endl;

}

HTNode* Buildtree(CHARACTER character[],int n)
{
    int j=0;
   int i;
   int x1,x2;
   int min1,min2;

  HTNode HH[2*M-1];//建立2*M-1大小的结构体数组
      cout<<endl;
  for( i=1;i<=M;i++)
  {
   if(character[i].count!=0)
   {
   HH[j].c=character[i].data;
   HH[j].weight=character[i].count;

   //cout<<"字符"<<HH[j].c<<"权值  "<<HH[j].weight<<endl;
   j++;
   }
  }
  for(i=0;i<n;i++)
{HH[i].parent=0;
HH[i].lchild=0;
HH[i].rchild=0;
}
for(i=n;i<2*n-1;i++)
{HH[i].parent=0;
HH[i].lchild=0;
HH[i].rchild=0;
HH[i].weight=0;
}

//建树
for(i=n;i<2*n-1;i++)
{
   select_min(HH,i,&x1,&x2);
   HH[x1].parent=i;
   HH[x2].parent=i;
   HH[i].lchild=x1;
   HH[i].rchild=x2;
    HH[i].weight=HH[x1].weight+HH[x2].weight;
 }//for
for(i=0;i<2*n-1;i++)
    cout<<HH[i].c<<" "<<HH[i].weight<<"  ";

return HH;
}

void Encode(HTNode HT[],int n)
{
int i,c,f;
char * cd;
int start;
 HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
 cd=(char* )malloc(n*sizeof(char));
 cd[n-1]='';
 for(i=1;i<=n;++i)
 {
    start=n-1;
 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
     if(HT[i].lchild==c)cd[--start]='0';
     else cd[--start]='1';
  HC[i]=(char*)malloc((n-start)*sizeof(char));
  strcpy(HC[i],&cd[start]);
  cout<<cd;
 }
 free(cd);
}

int main()
{
initcharacter();
character3= tongji(character1);
savecharacter(character3);
character3=readcharacter();
HuffmanTree Ht;
int n= countcharacter(character3);
Ht=Buildtree(character3,n);//将结构体数组地址返回到Ht
codeNode *t;
Encode(Ht,n);
return 0;
}

解决方案

http://www.cnblogs.com/hxf829/archive/2008/12/28/1659837.html

时间： 2024-08-17 18:26:04

c++ 哈夫曼数据结构-哈夫曼编译码，存储结构，编译码方法

问题描述

解决方案