目錄
前言
實(shí)驗要求
算法描述
個人想法
代碼實(shí)現(xiàn)和思路、知識點(diǎn)講解
知識點(diǎn)講解
文件傳輸
Huffman樹的存儲
Huffman的構(gòu)造
?Huffman編碼
編碼和譯碼
代碼實(shí)現(xiàn)
文件寫入和輸出
Huffman樹初始化
構(gòu)造Huffman樹
求帶權(quán)路徑長度
Huffman編碼
Huffman譯碼
結(jié)束
代碼測試
測試結(jié)果
前言
實(shí)驗要求
利用Huffman編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。試為這樣的信息收發(fā)站編寫一個Huffman的編/譯碼系統(tǒng)。給定一組權(quán)值 {7,9,5,6,10,1,13,15,4,8}，構(gòu)造一棵赫夫曼樹，并計算帶權(quán)路徑長度WPL。
算法描述
1．初始化：從鍵盤讀入n個字符，以及它們的權(quán)值，建立Huffman樹。
2．編碼： ?根據(jù)建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進(jìn)行編碼。
3．譯碼： ?利用已經(jīng)建立好的Huffman樹，對上面的編碼結(jié)果譯碼。
? ? ? ?? ? ?譯碼的過程是分解電文中的字符串，從根結(jié)點(diǎn)出發(fā)，按字符‘0’和‘1’確定找左孩子或右孩子，直至葉結(jié)點(diǎn)，便求得該子串相應(yīng)的字符。具體算法留給讀者完
個人想法
這一期是完成最最最基本要求的Huffman樹的創(chuàng)建和編碼譯碼。越是深入學(xué)習(xí)，越會發(fā)現(xiàn)很多的需求和案例都是在身邊的，脫離應(yīng)用，單純就寫一個算法的實(shí)現(xiàn)感覺還是不那么能感受到學(xué)習(xí)的快樂，所以我后面還會有進(jìn)階版本的。
代碼實(shí)現(xiàn)和思路、知識點(diǎn)講解
知識點(diǎn)講解
文件傳輸
我在寫代碼的時候一個是在進(jìn)行代碼調(diào)試和效果測試的時候覺得頻繁輸入數(shù)據(jù)去調(diào)試很麻煩，另一方面是在問題描述中也說了，利用Huffman編碼進(jìn)行通信，那如果拋開文件的，數(shù)據(jù)的傳輸，那就是空談了，所以我們第一步就是文件的讀取和寫入。
Huffman樹的存儲
有了數(shù)據(jù)來源，下一步就是確定樹在內(nèi)存中的存儲，我們先來用順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)我后面也會出的。結(jié)構(gòu)體定義：
typedef struct {
char data;
unsigned int weight; //不為0
unsigned int parent; //頭結(jié)點(diǎn)沒有雙親用來存葉子結(jié)點(diǎn)數(shù)量
unsigned int lChild, rChild;
} HTNode, *HTree;
這里用的全部都是unsigned int型，就是無符號整型，計算機(jī)存儲是沒有符號的，拿了一半無符號數(shù)的空間補(bǔ)碼存儲負(fù)數(shù)，無符號數(shù)就是把這段空間拿回來，全部存正數(shù)。
Huffman的構(gòu)造
我覺得相對而言這是最難的部分，主要是代碼方面可能會有些繞。知道存儲，要構(gòu)造Huffman數(shù)就要先找到什么是哈夫曼樹又是怎么構(gòu)建的。
可以看到，最開是全是葉子結(jié)點(diǎn)，選擇權(quán)值最小的兩結(jié)點(diǎn)構(gòu)成一個小樹，小樹的根節(jié)點(diǎn)繼續(xù)參與選擇，選兩個最小的結(jié)點(diǎn)構(gòu)成樹，特別注意，不是只能存在一棵樹，可能會同時存在好幾顆樹，而不是盯著一只羊毛薅。最后效果如下：
?Huffman編碼
其實(shí)不過就是大一點(diǎn)的二叉樹，看到圖，那Huffman編碼就很簡單了，因為計算機(jī)是01二進(jìn)制，二叉樹也是只有左右兩個子樹，那就可以得到各個葉子結(jié)點(diǎn)的編碼了
可以發(fā)現(xiàn)，如果在每一個岔路口，也就是每一個層次上標(biāo)注清楚，左拐是0，右拐是1，那對應(yīng)的編碼自然就出來了，例如：15對應(yīng)的是01；4對應(yīng)的是10011；這就是Huffman編碼。?
編碼和譯碼
每個葉子結(jié)點(diǎn)的權(quán)可以看作他們的出現(xiàn)頻率，頻率越高，就要擺在越容易夠到的地方，那我們可以將一篇文章所有出現(xiàn)的字符都看作一個葉子結(jié)點(diǎn)，而它出現(xiàn)的次數(shù)就是它的權(quán)，權(quán)越大離根節(jié)點(diǎn)就越接近。
編碼就是將這些字符作為葉子結(jié)點(diǎn)構(gòu)成Huffman樹，用Huffman的01編碼表示，例如我要表示9和7就是0001011；譯碼就是根據(jù)01從Huffman樹的根節(jié)點(diǎn)開始，直到找到葉子結(jié)點(diǎn)，翻譯為一個字符。
代碼實(shí)現(xiàn)
文件寫入和輸出
文件寫入和輸出就是靠指針實(shí)現(xiàn)，我喜歡讀寫分開來，定義w為只寫，r為只讀，a為追加，簡單展示一下：
//讀取文件并存初始化哈夫曼樹
HTree ReadFile() {
FILE * fp = fopen(Fname, "r"); //只讀方式打開
printf("----------正在讀取文件----------\n\n");
int n;
char cf, cs;
fscanf(fp, "%d %c", &n, &cs); //讀取第一個數(shù)據(jù)為哈夫曼樹葉子結(jié)點(diǎn)數(shù)量
HTree ht = (HTree)malloc((2*n-1)*sizeof(HTNode));
if (!ht) {
printf("！??！malloc Error！??！\n");
exit(1);
}
int i;
for (i = 0; i < 2*n-1; i++) {
ht[i].weight = ht[i].parent = ht[i].lChild = ht[i].rChild = 0;
ht[i].data = '#';
}
ht[0].parent = n;
i = 1;
do {
fscanf(fp, " %c %c", &(ht[i].data), &cf);
fscanf(fp, " %u %c", &(ht[i].weight), &cs);
i++;
} while (cf == ',' && cs == ';'); //'#'結(jié)束
fclose(fp);
if (cf != ',' || cs != '#') {
printf("！??！File Error?。。n");
exit(1);
}
printf("----------文件讀取完成----------\n\n");
return ht;
}?我寫好了一個文件，一個字符是數(shù)量，剩下的就是對應(yīng)結(jié)點(diǎn)元素和權(quán)值：
?從上面的方法可以看到，文件的方法和c語言的一般方法差不多，scanf從鍵盤獲取，fscanf就是從文件獲取，除了多了一個指針fp，其他格式一模一樣。
Huffman樹初始化
上面代碼，我除了讀取文件信息外，我還將Huffman樹初始化。n個葉子結(jié)點(diǎn)，Huffman樹就有2*n-1個節(jié)點(diǎn)所以我們開2*n-1個空間就行。大家的習(xí)慣是喜歡把根節(jié)點(diǎn)放在最后一個，但是我個人更喜歡把根節(jié)點(diǎn)放在第一個，因為需要的時候一下子就可以找到，而且根節(jié)點(diǎn)沒有雙親，那完全可以子啊根節(jié)點(diǎn)的雙親里面存儲葉子節(jié)點(diǎn)個數(shù)。我將根節(jié)點(diǎn)存在第0單元，1-n單元分別存放1-n個元素。
構(gòu)造Huffman樹
因為我將根節(jié)點(diǎn)放在第1單元內(nèi)，所以我和書上的代碼有些不一樣，但是大同小異，我對這個方法做出了優(yōu)化后面會單獨(dú)出一篇博客：
//構(gòu)造哈夫曼樹
HTree CreateHTree() {
HTree ht = ReadFile();
int n = ht[0].parent; //頭結(jié)點(diǎn)沒有雙親用來存葉子結(jié)點(diǎn)數(shù)量
int i;
for (i = n + 1; i < 2 * n; i++) {
int j = 0, lNode, rNode;
unsigned int min1, min2 = -1;
while (ht[++j].parent); //找到第一個未分配的結(jié)點(diǎn)
min1 = ht[j].weight;
lNode = j;
while (++j < i) {
if (!ht[j].parent) {
if (ht[j].weight < min1) {
min2 = min1;
rNode = lNode;
min1 = ht[j].weight;
lNode = j;
}
else if (ht[j].weight < min2) {
min2 = ht[j].weight;
rNode = j;
}
}
}
if (min1 + min2 < min1 || min1 + min2 < min2) {
printf("！??！Error Overflow?。?！\n");
exit(1);
}
j = j % (2 * n - 1);
ht[j].weight = min1 + min2;
ht[j].lChild = lNode;
ht[j].rChild = rNode;
ht[lNode].parent = j;
ht[rNode].parent = j;
}
printf("----------哈夫曼樹構(gòu)建成功----------\n");
return ht;
}其實(shí)本質(zhì)上就是選擇排序，選擇排序是選出一個最小或最大的，這個只要加一個變量記錄次小的就和選擇排序一模一樣了。找到之后將權(quán)值，孩子，雙親等值賦好就ok。
求帶權(quán)路徑長度
我們學(xué)了遞歸，抱著遞歸的思想去做這題就會非常簡單：
//定義遞歸函數(shù)，計算帶權(quán)路徑長度
int getWPL(HTree ht, int index, int depth) {
//如果是葉子結(jié)點(diǎn)，返回WPL
if (!ht[index].lChild && !ht[index].rChild) {
return ht[index].weight * depth;
}
else { //如果不是葉子結(jié)點(diǎn)，遞歸遍歷其左右子樹，深度加1
return getWPL(ht, ht[index].lChild, depth+1) + getWPL(ht, ht[index].rChild, depth+1);
}
}一個if else語句，加上兩個return解決。
Huffman編碼
這里為了讓元素和編碼之間聯(lián)系更加緊密，我單獨(dú)定義一個結(jié)構(gòu)體來存儲，就一個字符加一個數(shù)組。
//哈夫曼樹編碼存儲
typedef struct {
char data;
char *cd;
} HCode;
//創(chuàng)建哈夫曼樹編碼
HCode *CreateHCode(HTree ht) {
int n = ht[0].parent;
HCode *hc = (HCode *)malloc(n * sizeof(HCode));//存放哈夫曼編碼
char *code = (char *)malloc(n * sizeof(char)); //存放臨時編碼
code[n-1] = '\0'; //編碼結(jié)束符
int i;
for (i = 1; i < n + 1; i++) { //遍歷每個葉子結(jié)點(diǎn)
hc[i-1].data = ht[i].data;
int start = n - 1; //編碼起始位置
int c = i; //當(dāng)前結(jié)點(diǎn)下標(biāo)
int p = ht[i].parent; //父節(jié)點(diǎn)下標(biāo)
while (c != 0) { //直到根節(jié)點(diǎn)
if (ht[p].lChild == c) { //左孩子為0
code[--start] = '0';
}
else { //右孩子為1
code[--start] = '1';
}
c = p; //移動到父節(jié)點(diǎn)
p = ht[p].parent; //移動到祖父節(jié)點(diǎn)
}
hc[i-1].cd = (char *)malloc((n - start) * sizeof(char));
strcpy(hc[i-1].cd, &code[start]);
}
free(code);
printf("\n----------哈夫曼樹編碼成功----------\n");
return hc;
}哈夫曼樹編碼需要注意的一個點(diǎn)就是，我們從根節(jié)點(diǎn)很難明確到葉子節(jié)點(diǎn)的路徑，但是我們從葉子節(jié)點(diǎn)可以唯一確定一條路走向根節(jié)點(diǎn)，因為樹的性質(zhì)可以有很多孩子但是只能有一個雙親。所以大家在求編碼的時候要從葉子節(jié)點(diǎn)開始倒著求。我推薦大家使用棧，后進(jìn)先出的性質(zhì)在這里簡直不要太好用，我是偷了個懶直接從字符串末尾往前求，然后用字符串函數(shù)的賦值方法。
Huffman譯碼
知道了什么是編碼，那么譯碼簡直不要太簡單
//哈夫曼樹譯碼
void DeHCode(HTree ht, char *code) {
int k = 0; //當(dāng)前節(jié)點(diǎn)下標(biāo)
int i;
for (i = 0; code[i] != '\0'; i++) { //遍歷序列中的每個字符
if (code[i] == '0') { //向左走
k = ht[k].lChild;
}
else if (code[i] == '1') { //向右走
k = ht[k].rChild;
}
else { //非法字符
printf("?。?！Invalid Code Error?。。n");
exit(1);
}
if (ht[k].lChild == 0 && ht[k].rChild == 0) { // 到達(dá)葉子節(jié)點(diǎn)
printf("%c", ht[k].data); // 輸出對應(yīng)字符
k = 0; // 返回根節(jié)點(diǎn)繼續(xù)遍歷
}
}
printf("\n");
}你只需要跟著01的指引訪問左節(jié)點(diǎn)或者右節(jié)點(diǎn)，直到遇到葉子節(jié)點(diǎn)，輸出元素并回溯到根節(jié)點(diǎn)。周而復(fù)始直到訪問完所有元素。
結(jié)束
代碼測試
我寫個主調(diào)函數(shù)測試代碼
int main() {
printf("%s\n", Fname);
HTree ht = CreateHTree();
printf("哈夫曼樹的帶權(quán)路徑長為：%d\n", getWPL(ht, 0, 0));
HCode *hc = CreateHCode(ht);
printf("字符\t編碼\n");
int i;
for (i = 0; i < ht[0].parent; i++) {
printf("%c\t%s\n", hc[i].data, hc[i].cd);
}
char *c = "001000100101011111010110101110101110";
printf("\n%s\n譯碼后為：", c);
DeHCode(ht, c);
printf("\n----------測試結(jié)束----------\n");
return 0;
}測試結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-775446.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-775446.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) 實(shí)驗17：Huffman樹和Huffman編碼——學(xué)習(xí)理解哈夫曼樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
