构造哈夫曼树源程序

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