//Tree.h #include<iostream> #include<stdlib.h> using namespace std;
const int MaxValue=10000; const int MaxBit=10; const int MaxN=10;
struct HaffNode{ int weight; int flag; int parent; int leftChild; int rightChild; }; struct Code{ int bit[MaxN]; int start; int weight; }; void Haffman(int weight[],int n,HaffNode haffTree[]){ int j,m1,m2,x1,x2; for(int i=0;i<2*n-1;i++){ if(i<n) haffTree[i].weight=weight[i]; else haffTree[i].weight=0; haffTree[i].flag=0; haffTree[i].parent=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1; } for(i=0;i<n-1;i++){ m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++){ if(haffTree[j].weight<m1&&haffTree[j].flag==0) { m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } else if(haffTree[j].weight<m2&&haffTree[j].flag==0){ m2=haffTree[j].weight; x2=j; } } haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2; } }
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) { Code *cd=new Code; int child,parent; for(int i=0;i<n;i++) { cd->start=n-1; cd->weight=haffTree[i].weight; child=i; parent=haffTree[child].parent; while(parent!=0) { if(haffTree[parent].leftChild==child) cd->bit[cd->start]=0; else cd->bit[cd->start]=1; cd->start--; child=parent; parent=haffTree[child].parent; } for(int j=cd->start+1;j<n;j++) haffCode[i].bit[j]=cd->bit[j]; haffCode[i].start=cd->start; haffCode[i].weight=cd->weight; } } #include "Tree.h"
void main(void) { int i,j,n=4; int weight[]={1,3,5,7}; HaffNode *myHaffTree=new HaffNode[2*n+1]; Code *myHaffCode=new Code[n]; if(n>MaxN) { cerr<<"定义的n越界!"<<endl; exit(1); } Haffman(weight,n,myHaffTree); HaffmanCode(myHaffTree,n,myHaffCode); for(i=0;i<n;i++) { cout<<"Weight="<<myHaffTree[i].weight<<'\t'<<"Code="; for(j=myHaffCode[i].start+1;j<n;j++) cout<<myHaffCode[i].bit[j]; cout<<endl; } }
enjoy youself!!!