数据结构应用实例(三)——赫夫曼编码

一、问题描述

  对一篇英文文章，统计各字符（仅限于26个小写字母）出现的次数，并据此进行 Huffman 编码。

二、算法思想

  首先，打开文本文件，统计各个小写英文字母出现的次数；
  然后，统计出现过的字母个数 num；
  如果 num<=1，进行相关信息的显示，不进行 Huffman 编码；
  否则，进行 Huffman 编码：
  准备工作：存储出现过的字母编号及出现次数；
  1、根据出现次数，创建 Huffman 树：
  (1)根据求得的 num 个出现次数 { w 1 , w 2 , ⋯ , w n u m } \lbrace w_1,w_2,\cdots,w_{num} \rbrace {w1​,w2​,⋯,wnum​} 构成 num 棵二叉树的集合 F = { T 1 , T 2 , ⋯ , T n u m } F=\lbrace T_1,T_2,\cdots,T_{num} \rbrace F={T1​,T2​,⋯,Tnum​}，其中每棵二叉树 $T_i$ 中只有一个带权为 $w_i$ 的根节点，其左右子树均为空；
  (2)在 F 中选取两棵根节点权值最小的树作为左右子树构造一棵新二叉树，其根节点的权值为两棵子树根节点权值之和；
  (3)从 F 中删除这两棵树，并将新生成的树添加到 F 中；
  (4)重复(2)和(3)，直到 F 中只含一棵树。所得到的树就是 Huffman 树；
  2、根据 Huffman 树进行 Huffman 编码
  约定 ‘0’ 表示左分支，‘1’ 表示右分支。从某个叶子节点开始，如果没有父节点，表示编码结束；如果其有父节点，如果为父节点的左孩子，编码尾部添加 ‘0’，如果为右孩子，尾部添加 ‘1’，然后向根节点移动：当前节点变为其父节点，父节点变为父节点的父节点，进行相同操作。
  编码结束之后，对编码进行逆置，得到正序编码；
  3、最后显示出现的字母及其出现的次数和 Huffman 编码；

三、代码实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#pragma warning(disable:4996)typedef struct myhuffman//赫夫曼树的节点
{int weight;int parent,lchild,rchild;
}HTnode;typedef struct mylist//存放序号和权重
{int index;int weight;
}LI;int *statis();//统计小写英文字母出现的频次，返回存放频次的数组char **huffmanCoding(int *w, int n);//创建huffman编码，w用于存放叶子节点的权重，n表示叶子节点个数void select(HTnode *HT,int k,int *s1,int *s2);//在HT[1,,,k]中选取parent==0且weight最小的两个节点，返回其序号(*s1),(*s2)int main(void)
{int i,j;int *w,num;int **A;//用于存放频次不为0的字母编号和频次char **HC;//获取小写字母出现次数w=statis();	//统计出现过的字母个数num=0;for (i = 1; i <= 26; i++){if (w[i] != 0)num++;}printf("\n字母出现的次数和Huffman编码如下:\n");if (num == 0)printf("\n没有出现小写英文字母，无需进行Huffman编码\n");else // num>=1{A=(int **)malloc(2*sizeof(int *));A[0]=(int *)malloc((num+1)*sizeof(int));A[1]=(int *)malloc((num+1)*sizeof(int));//向A中存放数据j=1;for (i = 1; i <= 26 && j <= num; i++){if (w[i] != 0){A[0][j]=i;A[1][j]=w[i];j++;}}if (num == 1)printf("只出现了一个字母:%c，频次%d，其Huffman编码为1\n", A[0][1] + 'a' - 1, A[1][1]);else // num>=2{//创建huffman编码HC = huffmanCoding(A[1], num);//显示huffman编码			for (i = 1; i <= num; i++)printf("%c，频次：%2d，编码：%s\n", A[0][i] + 'a' - 1, A[1][i], HC[i]);free(HC);}free(A);}free(w);	return 0;
}int *statis()//统计小写英文字母出现的频次，返回存放频次的数组
{int i;int *w;FILE *fp;char ch,filename[50];//初始化w=(int *)malloc(27*sizeof(int));for (i = 1; i <= 26; i++)w[i]=0;//打开文件printf("请输入文件名:");scanf("%s",filename);fp=fopen(filename,"r");if (!fp){printf("文件不存在!\n");exit(-1);}//统计小写字母出现次数printf("\n文本信息为:\n");while (!feof(fp)){ch=fgetc(fp);printf("%c",ch);if ('a' <= ch && ch <= 'z')w[ch - 'a' + 1]++;}printf("\n");//关闭文件fclose(fp);return w;
}char **huffmanCoding(int *w, int n)//创建huffman编码，w用于存放叶子节点的权重，n表示叶子节点个数
{int i,j,k,l;HTnode *HT,p;int m;int s1,s2;char **HC;char *cd;//一、创建huffman树m=2*n-1;//总的节点个数HT=(HTnode *)malloc((m+1)*sizeof(HTnode));//HT为结构体数组，用于存放huffman树的节点//初始化for (i = 1; i <= n; i++)//叶子节点{p.weight=w[i];p.parent=0;p.lchild=p.rchild=0;HT[i]=p;}for (; i <= m; i++)//非叶子节点{p.weight=0;p.parent=0;p.lchild=p.rchild=0;HT[i]=p;}//合并子树for (i = n + 1; i <= m; i++){select(HT,i-1,&s1,&s2);//在HT[1,,,i-1]中选取parent==0且weight最小的两个节点，并返回其序号HT[s1].parent=i;HT[s2].parent=i;HT[i].weight=HT[s1].weight+HT[s2].weight;HT[i].lchild=s1;HT[i].rchild=s2;}//二、生成huffman编码HC=(char **)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';//字符串结束标志for (i = 1; i <= n; i++)//对各个叶子节点进行编码{j=n-1;k=i;l=HT[i].parent;while (l != 0){j--;if(HT[l].lchild == k)cd[j]='0';elsecd[j]='1';//更新循环变量k=l;l=HT[l].parent;}//为第i个编码分配空间并赋值HC[i]=(char *)malloc((n-j)*sizeof(char));strcpy(HC[i],&cd[j]);}free(HT);free(cd);return HC;
}void select(HTnode *HT, int k, int *s1, int *s2)//在HT[1,,,k]中选取parent==0且weight最小的两个节点，返回其序号(*s1),(*s2)
{int i,j;int n,lastindex;LI *T,temp;if(k <= 1)return;T=(LI *)malloc((k+1)*sizeof(LI));j=0;for (i = 1; i <= k; i++)//挑选parent==0的点{if (HT[i].parent == 0){j++;T[j].index=i;T[j].weight=HT[i].weight;}}//对T冒泡排序，寻找weight最小的两个节点n=j;//parent==0的节点个数lastindex=n;while (lastindex > n - 2)//至多进行两趟冒泡排序{i=lastindex;lastindex=0;for (j = 1; j < i; j++){if (T[j].weight < T[j + 1].weight)//交换两个数据，小的放在后面{temp=T[j];T[j]=T[j+1];T[j+1]=temp;lastindex=j;}}}//返回节点序号(*s1)=T[n].index;(*s2)=T[n-1].index;free(T);
}

四、小结

1、 由于 Huffman 树中没有出度为1的点，所以可以根据叶子节点的个数 $n_0$ 事先确定总的节点个数为 $2n_0-1$。
2、 结构体变量之间可以直接赋值；
3、 在寻找 parent==0 且 weight 最小的两个节点时，只需进行至多两次的冒泡排序，大大提高了查找效率和算法性能；
4、 进行 Huffman 编码时，由于是从叶子节点开始向前回溯到根节点，所以编码时从后向前进行，这样就避免了逆置编码；
5、 对于特殊情况：出现的英文字母个数小于等于1，则不进行 Huffman 编码；