1、#include #include stdlib.h #define MAXBIT 10#define MAXVALUE 10000#define MAXLEAF 100#define MAXNODE MAXLEAF*2-1 /定義哈夫曼樹編碼類型typedef struct char bitMAXBIT; /存放葉子結(jié)點(diǎn)字符編碼過后的二進(jìn)制編碼 int start; /存放葉子結(jié)點(diǎn)二進(jìn)制編碼在bit數(shù)組里的起始數(shù)組位置int length; /存放二進(jìn)制編碼的位數(shù)HFMCode; /定義哈夫曼樹結(jié)點(diǎn)類型typedef struct char data; /編碼字符int weight; /哈

2、夫曼樹結(jié)點(diǎn)的權(quán)值int parent; /哈夫曼樹結(jié)點(diǎn)的父結(jié)點(diǎn)int lchild; /哈夫曼樹結(jié)點(diǎn)的左孩子int rchild; /哈夫曼樹結(jié)點(diǎn)的右孩子HFMNode; /構(gòu)造哈夫曼樹void createHFMTree(HFMNode hfmnodeMAXNODE,int n) int i,j,m1,m2,x1,x2; for(i=0;i2*n-1;i+) hfmnodei.weight=0; hfmnodei.parent=-1; hfmnodei.lchild=-1; hfmnodei.rchild=-1; for(i=0;in;i+) getchar();printf(請(qǐng)輸入第%d片

3、葉子的字符：,i+1); scanf(%c,&hfmnodei.data);printf(請(qǐng)輸入第%d片葉子的權(quán)重：,i+1); scanf(%d,&hfmnodei.weight); for(i=0;in-1;i+) m1=m2=MAXVALUE; /m1和m2分別用來存儲(chǔ)葉子結(jié)點(diǎn)權(quán)值的最小值和次小值x1=x2=0; /x1和x2分別用來存儲(chǔ)m1和m2的位置for(j=0;jn+i;j+) if(hfmnodej.weightm1&hfmnodej.parent=-1) m2=m1;x2=x1;m1=hfmnodej.weight;x1=j; else if(hfmnodej.weightm

4、2&hfmnodej.parent=-1) m2=hfmnodej.weight;x2=j; hfmnodex1.parent=n+i; hfmnodex2.parent=n+i; hfmnoden+i.weight=hfmnodex1.weight+hfmnodex2.weight;/父結(jié)點(diǎn)的權(quán)重是左孩子和右孩子的權(quán)重之和 hfmnoden+i.lchild=x1; hfmnoden+i.rchild=x2; /顯示葉子的編碼字符和編碼字符對(duì)應(yīng)的二進(jìn)制編碼void showCode(HFMCode hfmcodeMAXNODE,HFMNode hfmnodeMAXNODE,int n)int

5、 i,j,k,c,p; HFMCode cd;for(i=0;in;i+) hfmcodei.length=0;hfmcodei.start=0;k=hfmcodei.start;cd.start=n-1;c=i; p=hfmnodec.parent; while(p!=-1) if(hfmnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=hfmnodec.parent; for(j=cd.start+1;jn;j+) hfmcodei.bitk=cd.bitj; k+;hfmcodei.len

6、gth+; /length計(jì)算存放的二進(jìn)制編碼的位數(shù) for(i=0;in;i+) /輸出每個(gè)葉子節(jié)點(diǎn)的哈夫曼編碼 printf(第%d片葉子的編碼是:,i+1); printf(%ct,hfmnodei.data);for(j=hfmcodei.start;jhfmcodei.length;j+)printf(%d,hfmcodei.bitj); printf(n); /輸入字符串，得到二進(jìn)制編碼void compileCode(char str,int n,HFMCode hfmcodeMAXLEAF,HFMNode hfmnodeMAXNODE)int i,j,k;for(i=0;str

7、i!=0;i+)for(j=0;jn;j+)if(stri=hfmnodej.data)for(k=hfmcodej.start;khfmcodej.length;k+)printf(%d,hfmcodej.bitk);printf(nn);/輸入二進(jìn)制編碼得到字符串void decompileCode(char num,int n,HFMCode hfmcodeMAXLEAF,HFMNode hfmnodeMAXNODE)int i,j;j=2*n-2; /哈夫曼樹根結(jié)點(diǎn)的位置for(i=0;numi!=0;i+)if(numi=0)j=hfmnodej.lchild;else if(num

8、i=1)j=hfmnodej.rchild;if(jn) /j大于等于n表示的都是除葉子結(jié)點(diǎn)以外的哈夫曼樹結(jié)點(diǎn) printf(%c,hfmnodej.data);j=2*n-2;printf(n);/主函數(shù)void main() HFMNode hfmnodeMAXNODE; HFMCode hfmcodeMAXLEAF; char str100; /存放輸入的需要編譯的的字符串char num100; /存放輸入的需要編譯的二進(jìn)制字符串int n; /輸入的葉子結(jié)點(diǎn)數(shù)/哈夫曼編碼器printf(-哈弗曼編碼器-n);printf(請(qǐng)輸入葉子結(jié)點(diǎn)數(shù):); scanf(%d,&n);createHFMTree(hfmnode,n);showCode(hfmcode,hfmnode,n);/哈夫曼譯碼器printf(-哈夫曼譯碼器-n);printf(