一、問(wèn)題描述

??對(duì)一篇英文文章，統(tǒng)計(jì)各字符（僅限于26個(gè)小寫字母）出現(xiàn)的次數(shù)，并據(jù)此進(jìn)行 Huffman 編碼。

二、算法思想

??首先，打開文本文件，統(tǒng)計(jì)各個(gè)小寫英文字母出現(xiàn)的次數(shù)；
??然后，統(tǒng)計(jì)出現(xiàn)過(guò)的字母?jìng)€(gè)數(shù) num；
??如果 num<=1，進(jìn)行相關(guān)信息的顯示，不進(jìn)行 Huffman 編碼；
??否則，進(jìn)行 Huffman 編碼：
??準(zhǔn)備工作：存儲(chǔ)出現(xiàn)過(guò)的字母編號(hào)及出現(xiàn)次數(shù)；
??1、根據(jù)出現(xiàn)次數(shù)，創(chuàng)建 Huffman 樹：
??(1)根據(jù)求得的 num 個(gè)出現(xiàn)次數(shù) { w 1 , w 2 , ? , w n u m } \lbrace w_1,w_2,\cdots,w_{num} \rbrace {w1?,w2?,?,wnum?} 構(gòu)成 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$ 中只有一個(gè)帶權(quán)為 $w_i$ 的根節(jié)點(diǎn)，其左右子樹均為空；
??(2)在 F 中選取兩棵根節(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，其根節(jié)點(diǎn)的權(quán)值為兩棵子樹根節(jié)點(diǎn)權(quán)值之和；
??(3)從 F 中刪除這兩棵樹，并將新生成的樹添加到 F 中；
??(4)重復(fù)(2)和(3)，直到 F 中只含一棵樹。所得到的樹就是 Huffman 樹；
??2、根據(jù) Huffman 樹進(jìn)行 Huffman 編碼
??約定 ‘0’ 表示左分支，‘1’ 表示右分支。從某個(gè)葉子節(jié)點(diǎn)開始，如果沒有父節(jié)點(diǎn)，表示編碼結(jié)束；如果其有父節(jié)點(diǎn)，如果為父節(jié)點(diǎn)的左孩子，編碼尾部添加 ‘0’，如果為右孩子，尾部添加 ‘1’，然后向根節(jié)點(diǎn)移動(dòng)：當(dāng)前節(jié)點(diǎn)變?yōu)槠涓腹?jié)點(diǎn)，父節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的父節(jié)點(diǎn)，進(jìn)行相同操作。
??編碼結(jié)束之后，對(duì)編碼進(jìn)行逆置，得到正序編碼；
??3、最后顯示出現(xiàn)的字母及其出現(xiàn)的次數(shù)和 Huffman 編碼；

三、代碼實(shí)現(xiàn)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#pragma warning(disable:4996)typedef struct myhuffman//赫夫曼樹的節(jié)點(diǎn)
{int weight;int parent,lchild,rchild;
}HTnode;typedef struct mylist//存放序號(hào)和權(quán)重
{int index;int weight;
}LI;int *statis();//統(tǒng)計(jì)小寫英文字母出現(xiàn)的頻次，返回存放頻次的數(shù)組char **huffmanCoding(int *w, int n);//創(chuàng)建huffman編碼，w用于存放葉子節(jié)點(diǎn)的權(quán)重，n表示葉子節(jié)點(diǎn)個(gè)數(shù)void select(HTnode *HT,int k,int *s1,int *s2);//在HT[1,,,k]中選取parent==0且weight最小的兩個(gè)節(jié)點(diǎn)，返回其序號(hào)(*s1),(*s2)int main(void)
{int i,j;int *w,num;int **A;//用于存放頻次不為0的字母編號(hào)和頻次char **HC;//獲取小寫字母出現(xiàn)次數(shù)w=statis();	//統(tǒng)計(jì)出現(xiàn)過(guò)的字母?jìng)€(gè)數(shù)num=0;for (i = 1; i <= 26; i++){if (w[i] != 0)num++;}printf("\n字母出現(xiàn)的次數(shù)和Huffman編碼如下:\n");if (num == 0)printf("\n沒有出現(xiàn)小寫英文字母，無(wú)需進(jì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中存放數(shù)據(jù)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("只出現(xiàn)了一個(gè)字母:%c，頻次%d，其Huffman編碼為1\n", A[0][1] + 'a' - 1, A[1][1]);else // num>=2{//創(chuàng)建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()//統(tǒng)計(jì)小寫英文字母出現(xiàn)的頻次，返回存放頻次的數(shù)組
{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("請(qǐng)輸入文件名:");scanf("%s",filename);fp=fopen(filename,"r");if (!fp){printf("文件不存在!\n");exit(-1);}//統(tǒng)計(jì)小寫字母出現(xiàn)次數(shù)printf("\n文本信息為:\n");while (!feof(fp)){ch=fgetc(fp);printf("%c",ch);if ('a' <= ch && ch <= 'z')w[ch - 'a' + 1]++;}printf("\n");//關(guān)閉文件fclose(fp);return w;
}char **huffmanCoding(int *w, int n)//創(chuàng)建huffman編碼，w用于存放葉子節(jié)點(diǎn)的權(quán)重，n表示葉子節(jié)點(diǎn)個(gè)數(shù)
{int i,j,k,l;HTnode *HT,p;int m;int s1,s2;char **HC;char *cd;//一、創(chuàng)建huffman樹m=2*n-1;//總的節(jié)點(diǎn)個(gè)數(shù)HT=(HTnode *)malloc((m+1)*sizeof(HTnode));//HT為結(jié)構(gòu)體數(shù)組，用于存放huffman樹的節(jié)點(diǎn)//初始化for (i = 1; i <= n; i++)//葉子節(jié)點(diǎn){p.weight=w[i];p.parent=0;p.lchild=p.rchild=0;HT[i]=p;}for (; i <= m; i++)//非葉子節(jié)點(diǎn){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最小的兩個(gè)節(jié)點(diǎn)，并返回其序號(hào)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';//字符串結(jié)束標(biāo)志for (i = 1; i <= n; i++)//對(duì)各個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼{j=n-1;k=i;l=HT[i].parent;while (l != 0){j--;if(HT[l].lchild == k)cd[j]='0';elsecd[j]='1';//更新循環(huán)變量k=l;l=HT[l].parent;}//為第i個(gè)編碼分配空間并賦值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最小的兩個(gè)節(jié)點(diǎn)，返回其序號(hào)(*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的點(diǎn){if (HT[i].parent == 0){j++;T[j].index=i;T[j].weight=HT[i].weight;}}//對(duì)T冒泡排序，尋找weight最小的兩個(gè)節(jié)點(diǎn)n=j;//parent==0的節(jié)點(diǎn)個(gè)數(shù)lastindex=n;while (lastindex > n - 2)//至多進(jìn)行兩趟冒泡排序{i=lastindex;lastindex=0;for (j = 1; j < i; j++){if (T[j].weight < T[j + 1].weight)//交換兩個(gè)數(shù)據(jù)，小的放在后面{temp=T[j];T[j]=T[j+1];T[j+1]=temp;lastindex=j;}}}//返回節(jié)點(diǎn)序號(hào)(*s1)=T[n].index;(*s2)=T[n-1].index;free(T);
}

四、小結(jié)

1、 由于 Huffman 樹中沒有出度為1的點(diǎn)，所以可以根據(jù)葉子節(jié)點(diǎn)的個(gè)數(shù) $n_0$ 事先確定總的節(jié)點(diǎn)個(gè)數(shù)為 $2n_0?1$。
2、 結(jié)構(gòu)體變量之間可以直接賦值；
3、 在尋找 parent==0 且 weight 最小的兩個(gè)節(jié)點(diǎn)時(shí)，只需進(jìn)行至多兩次的冒泡排序，大大提高了查找效率和算法性能；
4、 進(jìn)行 Huffman 編碼時(shí)，由于是從葉子節(jié)點(diǎn)開始向前回溯到根節(jié)點(diǎn)，所以編碼時(shí)從后向前進(jìn)行，這樣就避免了逆置編碼；
5、 對(duì)于特殊情況：出現(xiàn)的英文字母?jìng)€(gè)數(shù)小于等于1，則不進(jìn)行 Huffman 編碼；