哈夫曼編碼,構(gòu)造樹

1、單詞theofatoandinthatheisatonforhisarebe頻度1192677541518462450242195190181174157138124123# include <stdio.h># include<string.h># define N 50 /葉子結(jié)點(diǎn)數(shù)# define M 2*N-1 /數(shù)中結(jié)點(diǎn)數(shù)typedef structchar data5; /結(jié)點(diǎn)值int weight; /權(quán)重int parent;/雙親結(jié)點(diǎn)int lchild;/左孩子結(jié)點(diǎn)int rchild;/右孩子結(jié)點(diǎn)HTNode;typedef structchar

2、cdN; /存放哈夫曼碼int start;HCode;void CreateHT(HTNode ht ,int n)/構(gòu)造哈夫曼樹int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/所有結(jié)點(diǎn)的相關(guān)初值是-1for (i=n;i<2*n-1;i+)/構(gòu)造哈夫曼樹min1=min2=32767;/lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置 lnode=rnode=-1;for(k=0;k<=i-1;k+)if (htk.parent=-1)/只在

3、尚未構(gòu)造二叉樹的結(jié)點(diǎn)中找if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;void CreateHCode(HTNode ht,HCode hcd ,int n)/構(gòu)造哈夫曼編碼int

4、 i,f,c;HCode hc;for (i=0;i<n;i+)/根據(jù)哈夫曼樹求哈夫曼編碼hc.start=n;c=i;f=hti.parent;while (f!=-1)/循序直到樹根結(jié)點(diǎn)if (htf.lchild=c)/處理左孩子結(jié)點(diǎn)hc.cdhc.start-='0'else /處理右孩子結(jié)點(diǎn)hc.cdhc.start-='1'c=f;f=htf.parent;hc.start+;/start指向哈夫曼編碼最開始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼int i,k;i

5、nt sum=0,m=0,j;printf("輸出哈夫曼編碼：n"); /輸出哈夫曼編碼for(i=0;i<n;i+)j=0; printf("%s:t",hti.data);for (k=hcdi.start;k<=n;k+)printf("%c",hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf("n");printf("n平均長(zhǎng)度=%gn",1.0*sum/m);void main()int n=15,i;char *str

6、="The","of","a","to","and","in","that","he" ,"is","at","on","for","His","are","be"int fnum=1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123;HTNode htM; HCode hcdN; for (i=0;i<n;i+) strcpy(hti.data,stri); hti.weight=fnumi; printf