cseg.txt

哈夫曼编码构造 c++程序

#include <iostream> 
#include <fstream> 
#include <deque> 
using namespace std; 
//file declaration 
ifstream fin("Huffman.in"); 
//fuction declaration 
void huffman(); 
int getmin(int n); 
void in(); 
//variable declaration 
#define NN 1000 
typedef struct Cseg{               // 哈夫曼树的构造及其编码，t为树的存储结构 

，n为字符数， 
int l,r,w,p;               // f为对应字符的频率，c为字符。bi存储编码后的状态 

。 
}Cseg;                             // Cseg中，l,r为左右孩子，p is 
parent,w i 
s weight. 
Cseg t[NN];                        // 
int n,f[NN]; 
char c[NN]; 
deque<int> bi[NN]; 
//programe 
int main() 
{ 
in(); 
huffman(); 
return 0; 
} 
void in() 
{ 
int i; 
fin>>n; 
fin>>c; 
for (i=0;i<n;i++) 
  fin>>f; 
return; 
} 
void huffman() 
{ 
int i,j,k; 
for (i=0;i<n;i++){ 
  t.l=t.r=t.p=-1; 
  t.w=f; 
} 
for (i=1;i<n;i++){ 
  int i1; 
  i1=i+n-1; 
  j=getmin(i+n-1); 
  t[i1].l=j; 
  t[j].p=i1; 
  k=getmin(i+n-1); 
  t[i1].w=t[j].w+t[k].w; 
  t[i1].l=j; 
  t[i1].r=k; 
  t[i1].p=-1; 
  t[k].p=i1; 
} 
for (i=0 ; i<n; i++){ 
  bi.clear(); 
  k=i; 
  while (t[k].p!=-1){ 
   j=t[k].p; 
   if (t[j].l==k) bi.push_front(0); 
   else bi.push_front(1); 
   k=j; 
  } 
} 
//  out 
for (i=0;i<n;i++){ 
  cout<<c<<" ->"; 
  for (j=0;j<bi.size();j++) 
   cout<<bi[j]; 
  cout<<endl; 
} 
return; 
} 
int getmin(int n) 
{ 
int i,rec=-1; 
for (i=0;i<n;i++) 
  if (t.p==-1) 
   if (rec==-1) rec=i; 
   else if (t[rec].w>t.w) rec=i; 
return rec; 
}