数据结构实战（三）——三、 Huffman编码

数据结构实战（三）——三、 Huffman编码

任务简述

对一篇英文文章，统计其中26个小写字母出现的频次，对这些小写字母进行Huffman编码。

算法描述

用hf【51】来存放51个结点。先输出文本并用count数组记录每个字母出现次数。对hf初始化，然后每次将weight最小的两个结点组成一个新的结点，直到生成了51个结点。对每个字母对应的bianma赋值，先求出bianma长度然后倒序赋值，左孩子赋0，右孩子赋1。输出每个字母输出的次数及对应的编码。最后用“”输入编码，一一判断是否是某个字母对应的编码，分别操作，输出文本。时间复杂度为O(n)（n为文本长度）

源代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node{int weight,pa,left,right;//weight为出现次数 char ch,bianma[25];//ch为每个结点对应的字母，bianma记录每个字母对应的bianma 
}HF;int zhuanhua(char ch){//将字符转化为数字 int a=ch-'a';return a;
}int main(){FILE *f=fopen(&#","r");//A.txt为原文 char ch,bianma[25];//ch是每次输入的 HF hf[51];//共26个字母，霍夫曼树共51个结点 int count[26]={0},i,visit[51]={0},n=26,mmin,mmmin,j,k,length;//count记录每个字母出现次数，visit在生成树时记录每个字母是否已有pa，n为当前结点数量，mmin是每次循环最小数 mmmin是第二小数，length是每个字母的bianma长度 if(!f){//打开失败 printf("打开失败n");exit(0);}printf("原文本：n");while((ch=getc(f))!=EOF){//先输出原文并统计每个字母出现次数 if('a'<=ch&&ch<='z'){putchar(ch);count[zhuanhua(ch)]++;}}fclose(f);for(i=0;i<2*n-1;i++){//这两个循环对霍夫曼树先初始化（前26个结点为字母结点） hf[i].left=0;hf[i].pa=0;hf[i].right=0;}for(i=0;i<n;i++){hf[i].weight=count[i];hf[i].ch='a'+i;}while(n<51){//用出现次数最小的两个点生成新结点，直到共51个结点 visit数组判断每个结点是否已有pa for(i=0;i<n;i++){//先找到一个最小的和第二小的 if(!visit[i]){mmin=i;break;}}for(i++;i<n;i++){if(!visit[i]){if(hf[i].weight<hf[mmin].weight){mmmin=mmin;mmin=i;}else{mmmin=i;}break;}}for(i++;i<n;i++){if(!visit[i]){if(hf[i].weight<hf[mmmin].weight){if(hf[i].weight<hf[mmin].weight){mmin=i;}else{mmmin=i;}}}}visit[mmin]=1;visit[mmmin]=1;hf[n].weight=hf[mmin].weight+hf[mmmin].weight;hf[n].left=mmmin;hf[n].right=mmin;hf[mmin].pa=n;hf[mmmin].pa=n;n++;}for(i=0;i<26;i++){//对每个字母的bianma赋值 k=i;length=0;while(hf[k].pa){//先求bianma长度 k=hf[k].pa;length++;}k=i;j=1;while(hf[k].pa){//倒序对bianma赋值，左孩子赋0，右孩子赋1 if(k==hf[hf[k].pa].left){bianma[length-j]='0';}else{bianma[length-j]='1';}k=hf[k].pa;j++;}bianma[length]='';strcpy(hf[i].bianma,bianma);}for(i=0;i<26;i++){//输出每个字母的出现次数及对应的编码 printf("%c:出现%d次 编码：",hf[i].ch,hf[i].weight);puts(hf[i].bianma);printf("n");}f=fopen(&#","r");//输入编码，输出字符 if(!f){//打开失败 printf("打开失败n");exit(0);}i=0;while((ch=getc(f))!=EOF){//bianma记录当前输入的编码，与每个字母对应的编码比较，如有字母与其对应则输出并对bianma重新赋值，没有则继续赋值 bianma[i]=ch;bianma[i+1]='';for(j=0;j<26;j++){if(strcmp(bianma,hf[j].bianma)==0){//当前bianma为某个字母对应的编码的情况 printf("%c",hf[j].ch);i=0;break;}}if(j==26){//当前bianma不是任何字母对应的编码的情况 i++;}}fclose(f);return 0;
} //共128行

运行结果

总结
写好了才发现没用什么全在主函数里写的没用什么别的函数。。。初始化这些操作可以写个函数来完成。对大写字母以及数字、标点、空格等都直接忽略了，导致输出的文章很傻。同时，对于没有输出的字母不应该赋编码，有空会把这些都加进去再写一个更完善的。