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


#define NUM 256 //字母數(shù) 
#define TNUM 511 // 總結(jié)點(diǎn)數(shù)為num+（num-1）
#define CLONG 24 //編碼最大長度 


class Node 
{ 
public: 
   int data;     // byte will be converted to int
   long weight; 
   int parent; 
   int lchild; 
   int rchild; 
}; 

void main() 
{ 
long weight[NUM];//256個(gè)字符出現(xiàn)頻率 
int nzc=0;   //the count of symbol with no zero weight
long maxweight;  // 最大字節(jié)數(shù)，根的權(quán)
int maxclength=0,minclength=100;   //碼表中最長的碼
int i,j,smallest,small;
long smallestw,smallw; 
int hcode[NUM][CLONG]; //用于存儲(chǔ)編碼 
int son,father; 
char codetable[256][5];  //碼表 0 長度 1 2 3 為碼 4 為代表的symbol
FILE *source,*destination;
Node nodes[TNUM]; //用對(duì)象數(shù)組存儲(chǔ)哈夫曼樹 

for(i=0;i<NUM;i++){
 nodes[i].data=257;
 nodes[i].weight=0;
 nodes[i].lchild=-1;
 nodes[i].rchild=-1;
 nodes[i].parent=-1;
}

// read the source file and count the weight
for(i=0;i<NUM;i++){
  weight[i]=0;
}
/////////////////////////////////////////////////////////////////////////////

if((source=fopen("compress.txt","w"))==NULL)
{
	printf("source file can not be opened!\n");
    return;
}
for(i=0;i<256;i++){fputc((char)i,source);}



maxweight=ftell(source);
fclose(source);
////////////////////////////////////////////////////////////////////////////////
if((source=fopen("compress.txt","r"))==NULL)
{
	printf("source file can not be opened!\n");
    return;
}
while(!feof(source)){
	weight[(int)(fgetc(source))]++;
}
maxweight=ftell(source);
fclose(source);
//  
nzc=0;
for(i=0;i<NUM;i++) 
{ 
  if(weight[i]!=0)
  {
  nodes[nzc].data=i; 
  nodes[nzc].weight=weight[i]; 
  nzc++;
  }
}            
///now nodes[i] contain only valid value;

for(i=nzc;i<2*nzc-1;i++) 
{ 
nodes[i].data=257;   //其實(shí)不是什么真正的字符
nodes[i].weight=-1; 
nodes[i].parent=-1; 
nodes[i].lchild=-1; 
nodes[i].rchild=-1; 
} 

//建立哈夫曼樹 
for(i=nzc;i<2*nzc-1;i++) 
{ 
smallest=small=-1;    //權(quán)數(shù)最小的兩個(gè)節(jié)點(diǎn)
smallestw=smallw=maxweight; //代表有最小的權(quán)數(shù)的節(jié)點(diǎn)的權(quán)  
for(j=0;j<i;j++) 
{ 
 if(nodes[j].parent==-1) 
 { 
  if(nodes[j].weight<smallestw) 
  {  
   smallw=smallestw; 
   smallestw=nodes[j].weight; 
   small=smallest; 
   smallest=j; 
  } 
  else if(nodes[j].weight>smallestw&&nodes[j].weight<smallw) 
  { 
   smallw=nodes[j].weight; 
   small=j; 
  } 
 } 
}//for語句得到 parent=-1(即尚沒有父結(jié)點(diǎn))且weight最小的兩個(gè)結(jié)點(diǎn) 
nodes[small].parent=i; 
nodes[smallest].parent=i; 
nodes[i].lchild=small; 
nodes[i].rchild=smallest; 
nodes[i].weight=nodes[smallest].weight+nodes[small].weight; 
} 
//到此就完成了樹
//初始化huffman code 
for(i=0;i<nzc;i++) 
{ 
for(j=0;j<CLONG;j++) 
{ 
hcode[i][j]=3;   // any digital will be ok except of '1'and'0' 
} 
} 

//編碼 開始
for(i=0;i<nzc;i++) 
{ 
  j=CLONG-1;   ///從高位向下存
  for(son=i,father=nodes[i].parent;father!=-1;)   // 一定要注意判斷條件。
  { 
   if(nodes[father].lchild==son) 
   { 
    hcode[i][j]=1; 
   } 
   else 
   { 
    hcode[i][j]=0; 
   } 
   j--; 
   son=father,father=nodes[son].parent;
  } 

} 
// 編碼成功 下面創(chuàng)建碼表
int length;
int m,n;
for(i=0;i<nzc;i++){
	length=0;
	for(j=0;j<CLONG;j++)
	{
		if (hcode[i][j]!=3) length++;
	}
    m=7;n=1;
    codetable[i][1]=(char)0;
    codetable[i][2]=(char)0;
    codetable[i][3]=(char)0;
	for(j=CLONG-length;j<CLONG;j++){
		if(hcode[i][j]==1){
        codetable[i][n]=(char)( codetable[i][n]|(char)(1<<m));
		}
		m--;
		if(m==-1){
		n++;
		m=7;
		}
	}
   
	if (length>maxclength) 
	{maxclength=length;}
	if(length<minclength)
	{minclength=length;}
    codetable[i][0]=(char)length;    // 碼表每個(gè)下標(biāo)代表symbol，每個(gè)item第一個(gè)字節(jié)為長度
    codetable[i][4]=(char)nodes[i].data;
}
if((destination=fopen("codetable.txt","w"))==NULL)
{
	printf("source file can not be opened!\n");
    return;
}

for(i=0;i<nzc;i++){
fputc(codetable[i][0],destination);
fputc(codetable[i][1],destination);
fputc(codetable[i][2],destination);
fputc(codetable[i][3],destination);
fputc(codetable[i][4],destination);
}


fclose(destination);
// 特別說明：nodes里面從0到nzc-1都是有效的。
//輸出 nodes 
/*
cout<<"HuffmanTree:"<<endl; 
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) 
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; 
for(i=0;i<TNUM;i++) 
{ 
cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) 
<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; 
} 
*/
//輸出編碼 
cout<<"maxlength"<<maxclength<<"minlength"<<minclength<<endl;
cout<<"from table \n";
i=1;
cout<<"NO."<<i<<":L"<<(int)codetable[i][0]<<":char"<<(int)codetable[i][1]<<(int)codetable[i][2]<<(int)codetable[i][3]<<" "<<(int)codetable[i][4];

/*

  
if((destination=fopen("char.txt","w"))==NULL)
{
	printf("source file can not be opened!\n");
    return;
}

fputc(codetable[0][1],destination);
fputc(codetable[0][2],destination);
fputc(codetable[0][3],destination);

fclose(destination);
	
*/


cout<<"共有"<<nzc<<"個(gè)不是0的";
cout<<endl<<"Result:"<<endl; 
cout<<setw(6)<<"symbol"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; 
for(i=0;i<nzc;i++) 
{ 
cout<<setw(6)<<nodes[i].data<<setw(10)<<nodes[i].weight; cout<<"    "; 
for(j=0;j<CLONG;j++) 
{ 
  if(hcode[i][j]!=3) 
  { 
   cout<<hcode[i][j]; 
  } 
} 
cout<<endl; 
} 
cout<<"\nDone"<<endl; 

cout<<"共有"<<nzc<<"個(gè)不是0的";


for(i=0;i<nzc;i++) 
{
cout<<nodes[i].data<<"   ";

}
cout<<maxweight;


cout<<"done!";
getchar();
}