1、*/* 文件名： exp7-6.cpp*#include <stdio.h>#include <string.h>#define N 50 / 葉子結點數#define M 2*N-1/ 樹中結點總數typedef structchar data5;int weight;int parent;int lchild;int rchild;HTNode;typedef struct/ 結點值/ 權重/ 雙親結點/ 左孩子結點/ 右孩子結點char cdN;/ 存放哈夫曼碼int start;HCode;構造哈夫曼樹void CreateHT(HTNode ht,int n)

2、 int i,k,lnode,rnode;int min1,min2;for(i = 0;i < 2*n-1;i+)所有結點的相關域置初值hti.parent = hti.lchild = hti.rchild = -1;/ 為 -1for(i = n;i < 2*n-1;i+)/構造哈夫曼樹min1 = min2 = 32767;/lnode和 rnode 為最小權重的兩個結點位置lnode = rnode = -1;for(k = 0;k <= i-1;k+)if(htk.parent = -1)if(htk.weight < min1)min2 = min1;rn

3、ode = 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) int i,f,c;HCode hc;for(i = 0;i &

4、lt; n;i+)hc.start = n;c = i;f = hti.parent; while(f != -1) if(htf.lchild = c) hc.cdhc.start- = '0'elsehc.cdhc.start- = '1' c = f;f = htf.parent;hc.start+; hcdi = hc;輸出哈夫曼編碼 */void DispHCode(HTNode ht,HCode hcd,int n)int i,k;int sum = 0,m = 0,j;printf(" 輸出哈弗曼編碼 :n");for(i =

5、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 平均長度 =%gn",1.0*sum/m);void main()int n = 15,i;char *str = "The","of","a&q

6、uot;,"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