哈夫曼树 | 顾建伟个人博客
现在的位置: 首页 > Code > 正文
哈夫曼树
2014年04月20日 Code, 电脑相关 ⁄ 共 1741字 评论数 3

分享到:


以验证可直接运行 [code lang="c"] #include <stdio.h> #include <string.h> #define N 50 //叶子结点数 #define M 2*N-1 //树中结点总数 typedef struct { char data[5]; //结点值 int weight; //权重 int parent; //双亲结点 int lchild; //左孩子结点 int rchild; //右孩子结点 }HTNode; typedef struct { char cd[N]; //存放哈夫曼码 int start; }HCode; /********构造哈夫曼树**********/ void CreateHT(HTNode ht[],int n) { int i,k,lnode,rnode; int min1,min2; for(i = 0;i < 2*n-1;i++) ht[i].parent = ht[i].lchild = ht[i].rchild = -1;//所有结点的相关域置初值为-1 for(i = n;i < 2*n-1;i++)//构造哈夫曼树 { min1 = min2 = 32767;//lnode和rnode为最小权重的两个结点位置 lnode = rnode = -1; for(k = 0;k <= i-1;k++) if(ht[k].parent == -1) { if(ht[k].weight < min1) { min2 = min1; rnode = lnode; min1 = ht[k].weight; lnode = k; } else if(ht[k].weight < min2) { min2 = ht[k].weight; rnode = k; } } ht[lnode].parent = i; ht[rnode].parent = i; ht[i].weight = ht[lnode].weight+ht[rnode].weight; ht[i].lchild = lnode; ht[i].rchild = rnode; } } /***************构造哈夫曼编码****************/ void CreateHCode(HTNode ht[],HCode hcd[],int n) { int i,f,c; HCode hc; for(i = 0;i < n;i++) { hc.start = n; c = i; f = ht[i].parent; while(f != -1) { if(ht[f].lchild == c) hc.cd[hc.start--] = '0'; else hc.cd[hc.start--] = '1'; c = f; f = ht[f].parent; } hc.start++; hcd[i] = hc; } } /***************输出哈夫曼编码**************/ void DispHCode(HTNode ht[],HCode hcd[],int n) { int i,k; int sum = 0,m = 0,j; printf(" 输出哈弗曼编码:\n"); for(i = 0;i < n;i++) { j = 0; printf(" %s:\t",ht[i].data); for(k = hcd[i].start;k <= n;k++) { printf("%c",hcd[i].cd[k]); j++; } m += ht[i].weight; sum += ht[i].weight*j; printf("\n"); } printf("\n 平均长度=%g\n",1.0*sum/m); } void main() { int n = 15,i; char *str[] = {"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 ht[M]; HCode hcd[N]; for(i = 0;i < n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight = fnum[i]; } printf("\n"); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("\n"); } [/code]

说出你的想法!
有事加我的QQ:932404999(微博ID:顾建伟个人博客网)
×