新建文档.txt

经典的霍夫曼算法程序！和西西论课本上的算法是配套的

#include <iostream>
using namespace std;

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

typedef char **HuffmanCode;
typedef char *EachHuffcode;

void Select(HuffmanTree HT,int length,int &s1,int &s2)
{ //s1 lowest,s2 lower
 unsigned int min = 5000;
 HuffmanTree  p = HT;
 int i;
 for(i = 1, ++p; i <= length ; ++i,++p)
 {
  if(p->weight < min && p->parent == 0)
  {
   min = p->weight;
   s1 = i;
  }
 }
 min = 5000;
 p = HT;
 //Get the second less weight 
 for(i = 1, ++p; i <= length ; ++i,++p)
 {
  if(p->weight < min && p->parent == 0)
  {
   if( i == s1)//case s1,ignore
    continue;
   min = p->weight;
   s2 = i;
  }
 }
}//Select

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{
 if(n <= 1) return;
 int m = 2 * n - 1;
 HT = new HTNode[m + 1];//0 is not used
 HuffmanTree p = HT;
 int i;
 for( i = 1, ++p; i <= n; ++i,++p,++w){
  p->weight = *w;//note: never use this *p = {*w,0,0,0,0},because *p has already been declared
  p->parent = p->lchild = p->rchild = 0;
 }//for
 for(; i <= m; ++i,++p) p->weight = p->parent = p->lchild = p->rchild = 0;
 int s1;
 int s2;
 for( i = n + 1; i <= m; ++i){
  Select(HT,i-1,s1,s2);
  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;
 }//for
 HC = new EachHuffcode[n+1];//0 is not used 
 char *cd = new char[n];
 cd[n-1] = '\0';//the end of each char 
 int start;
 for(i = 1; i <= n ; ++i){//get each huff code for h[1] to h[n]
  start = n -1;
  for(int c = i, int f = HT[i].parent; f != 0; c = f ,f = HT[f].parent)
   if(c == HT[f].lchild) cd[--start] = '0';
   else cd[--start] = '1';
   HC[i] = new char[n - start];//allocate memory for each HT
   strcpy(HC[i],&cd[start]);
 }//for
 delete []cd;//don't forget release memory
}//HuffmanCoding

int main(int argc, char* argv[])
{
 HuffmanTree hftree = NULL;
 HuffmanCode hfcode = NULL;
 int x;
 cout<<"Please input the number of the nodes:"<<endl;
 cin>>x;
 int *weight=new int [x];
char *character=new char[x];
 cout<<"Please give the "<<x<< " nodes' character:"<<endl;
 for (int j=0; j<x; ++j) cin>> character [j];
cout<<"Please give the "<<x<< " nodes' weight:"<<endl;
 for (j=0; j<x; ++j) {
    cout<<character[j]<<": ";
    cin>>weight[j];
 }//for
 HuffmanCoding(hftree,hfcode,weight,x);
 EachHuffcode *p = hfcode;
 ++p;
 for (int i = 0; i < x; ++i,++p){
  if(i==0)
	  cout<<"The corresponding HuffmanCode of the "<<x<<" nodes are:"<<endl;
  cout<<character[i]<<":"<<*p<<endl;//show each huffman code by each line
 }//for
 for(i = 1; i <=x; ++i) delete hfcode[i];//release memory
 delete []hfcode;
 delete []hftree;
 return 0;
}//main