霍夫曼碼實(shí)驗(yàn)程序

1、#include <iostream> using namespace std; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼樹 typedef struct int weight; /字符的權(quán)值 int parent,lchild,rchild; HTNode,*HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼編碼 typedef char* *HuffmanCode; /選擇n個(gè)（這里是k=n）節(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn) void Select(HuffmanTree &HT,int k,int &s1,int &s2) int i; i=1; while(i<=k

2、&& HTi.parent!=0)i+; /下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號(hào) s1=i; for(i=1;i<=k;i+) if(HTi.parent=0&&HTi.weight<HTs1.weight)s1=i; /下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號(hào) for(i=1;i<=k;i+) if(HTi.parent=0&&i!=s1)break; s2=i; for(i=1;i<=k;i+) if(HTi.parent=0&&i!=s1&&HTi.weight<HTs2.w

3、eight)s2=i; /構(gòu)造Huffman樹，求出n個(gè)字符的編碼 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,c,f,s1,s2,i,start; char *cd; if(n<=1)return; m=2*n-1; /n個(gè)葉子n-1個(gè)結(jié)點(diǎn) HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0號(hào)單元未用，預(yù)分配m+1個(gè)單元 HuffmanTree p=HT+1; w+; /w的號(hào)單元也沒有值，所以從號(hào)單元開始 for(i=1;i<

4、;=n;i+,p+,w+) p->weight=*w; p->parent=p->rchild=p->lchild=0; for(;i<=m;+i,+p) p->weight=p->parent=p->rchild=p->lchild=0; for(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2); /選出當(dāng)前權(quán)值最小的 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /

5、從葉子到根逆向求每個(gè)字符的霍夫曼編碼 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配n個(gè)字符編碼的頭指針變量 cd=(char*)malloc(n*sizeof(char); /分配求編碼的工作空間 cdn-1='0'/編碼結(jié)束符 for(i=1;i<=n;i+) /逐個(gè)字符求霍夫曼編碼 start=n-1; /編碼結(jié)束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /從葉子到根逆向求編碼 if(HTf.lchild=c) cd-start='0' else cd

6、-start='1' HCi=(char*)malloc(n-start)*sizeof(char); /為第i個(gè)字符編碼分配空間 strcpy(HCi,&cdstart);/從cd復(fù)制編碼到HC free(cd); /釋放工作空間 void main() int n,i; int* w; /記錄權(quán)值 char* ch; /記錄字符 HuffmanTree HT; HuffmanCode HC; cout<<"請(qǐng)輸入待編碼的字符個(gè)數(shù)n=" cin>>n; w=(int*)malloc(n+1)*sizeof(int);/記錄權(quán)

7、值，號(hào)單元未用 ch=(char*)malloc(n+1)*sizeof(char);/記錄字符，號(hào)單元未用 cout<<"依次輸入待編碼的字符data及其權(quán)值weight"<<endl; for(i=1;i<=n;i+) cout<<"data"<<i<<"=" cin>>chi; cout<<"weight"<<i<<"=" cin>>wi; HuffmanCoding(HT,HC,w,n); /輸出字符及