#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; //指向哈夫曼编码cd[]的最开始字符(从下标start开始到n为有效的哈夫曼编码) } HCode; void CreateHT(HTNode ht[],int n);//构造 void CreateHCode(HTNode ht[],HCode hcd[],int n);//编码 void DispHCode(HTNode ht[],HCode hcd[],int n);//输出编码 void main() { int n=15;//15个单词（叶节点） ////初始化 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 (int i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } CreateHT(ht,n);//构造哈夫曼树 CreateHCode(ht,hcd,n);//根据哈夫曼树建立哈夫曼编码 DispHCode(ht,hcd,n);//输出哈夫曼编码 printf("\n"); } void CreateHT(HTNode ht[],int n) { int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++)//ht[]初始化---所有结点的相关域置初值-1 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //构造哈夫曼树/////////////////////////////// for (i=n;i<2*n-1;i++) { min1=min2=32767;//最小权重和次小权重 lnode=rnode=-1;//最小两个权重位置(节点下标) //从已有的节点且未构造二叉树的节点中选取权重最小的两个节点 for (k=0;k<=i-1;k++)//树中现有i个节点 if (ht[k].parent==-1)//尚未构造二叉树的结点 { if (ht[k].weight<min1)//k号节点权重比最小权重min1还小 { min2=min1;rnode=lnode;//次小权重min2取最小权重min1 min1=ht[k].weight;lnode=k;//最小权重min1取k号节点对应的权重 } else if (ht[k].weight<min2)//k号节点权重大于最小权重，小于次小权重min2 { min2=ht[k].weight;rnode=k;//次小权重min2取k号节点权重 } } ht[lnode].parent=i;ht[rnode].parent=i;//权重最小的两个节点构造以i号节点为父节点的二叉树 //新增i号节点(新增节点没有data域) 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,temp; HCode hc; for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/ { //////对叶节点i对应单词---进行编码//// hc.start=n;//hc.cd[]中编码存放的起始位置(从start开始到n为编码存储区)(编码下标范围是0~N-1) temp=i;//当前节点c取叶节点i f=ht[temp].parent; while (f!=-1)//当前节点c存在父节点 { if (ht[f].lchild==temp)//当前c节点是其父节点的左孩子节点 hc.cd[hc.start--]='0';//编码 else hc.cd[hc.start--]='1';//当前c节点是其父节点的右孩子节点 temp=f;//取c的父节点为新的当前节点c f=ht[temp].parent;//取当新的当前节点c的父节点f } hc.start++;//(从下标hc.start开始存储到hc.start=n结束)---start指向哈夫曼编码最开始字符 //////////////////////////////////////// hcd[i]=hc;//叶节点i对应单词的哈夫曼编码hc存入编码表hcd[i] } } void DispHCode(HTNode ht[],HCode hcd[],int n)//输出哈夫曼编码 { int i,k; int CodeSum=0,WeightAdd=0; printf("输出哈夫曼编码:\n"); for (i=0;i<n;i++)//对于每个单词(叶节点) { int CountLen=0; printf("%s:\t",ht[i].data);//输出单词 for (k=hcd[i].start;k<=n;k++)//输出单词(叶节点)编码 { printf("%c",hcd[i].cd[k]); CountLen++;//统计i号单词编码长度 } WeightAdd+=ht[i].weight;//统计叶节点权重和(即所有单词总数) CodeSum+=ht[i].weight*CountLen;//得到总的编码量(即所有单词的编码总量) printf("\n"); } printf("平均每个单词的编码长度=%g\n",1.0*CodeSum/WeightAdd);//输出每个单词的编码平均长度 } /* 输出哈夫曼编码: The: 01 of: 101 a: 001 to: 000 and: 1110 in: 1101 that: 11110 he: 11001 is: 11000 at: 10011 on: 10010 for: 10001 His: 10000 are: 111111 be: 111110 平均每个单词的编码长度=3.56208 Press any key to continue */