《數(shù)據(jù)結(jié)構(gòu)》課程中哈夫曼編碼教學(xué)案例研究

王彩霞

摘 ?要：哈夫曼編碼是《數(shù)據(jù)結(jié)構(gòu)》課程中二叉樹的一個(gè)重要應(yīng)用，也是該課程的重點(diǎn)和難點(diǎn)。文章對哈夫曼編碼的課堂教學(xué)進(jìn)行了介紹，在課程中，利用樹的二叉鏈表結(jié)構(gòu)及哈夫曼樹的特點(diǎn)設(shè)計(jì)出了另一種哈夫曼編碼方法，并給出算法設(shè)計(jì)方法及描述，同時(shí)與傳統(tǒng)編碼方法做比較分析。教學(xué)實(shí)踐表明，學(xué)生對哈夫曼編碼原理的理解及編碼程序設(shè)計(jì)方法的掌握得到了顯著提高。

關(guān)鍵詞：教學(xué)案例;數(shù)據(jù)結(jié)構(gòu);哈夫曼編碼

中圖分類號(hào)：G642 ? ? ? 文獻(xiàn)標(biāo)志碼：A ? ? ? ? 文章編號(hào)：2096-000X（2020）31-0104-03

Abstract： Huffman coding is an important application of binary trees in the "Data Structure" course， and it is also the focus and difficulty of the course. This article introduces the classroom teaching of Huffman coding. In the course， another Huffman coding method is designed using the binary linked list structure of the tree and the characteristics of the Huffman tree， the algorithm design method and description are given， and at the same time， it is compared and analyzed with traditional coding methods. Teaching practice shows that students' understanding of Huffman coding principles and mastery of coding programming methods have been significantly improved.

Keywords： teaching case; data structure; Huffman coding

引言

《數(shù)據(jù)結(jié)構(gòu)》[1]是一門典型的將理論轉(zhuǎn)換為實(shí)踐的計(jì)算機(jī)課程，在應(yīng)用數(shù)學(xué)專業(yè)的課程體系中起著非常重要作用。如果學(xué)生在學(xué)習(xí)理論知識(shí)的過程中，能夠持續(xù)運(yùn)用不同的已學(xué)知識(shí)解決相同的問題[2]，舉一反三，改造創(chuàng)新，那么理論和實(shí)踐能力都能得到發(fā)展提高。在文中，筆者利用已學(xué)的一維數(shù)組及樹的二叉鏈表結(jié)構(gòu)，在傳統(tǒng)哈夫曼編碼方法基礎(chǔ)上，給出了另一種哈夫曼樹編碼方法。教學(xué)結(jié)果顯示，學(xué)生學(xué)習(xí)效率得到了大大提高，同時(shí)還激發(fā)了學(xué)生的上機(jī)編程熱情。

一、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

哈夫曼樹采用二叉鏈表結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)包含指向左右孩子結(jié)點(diǎn)的指針，還包括用于存放該結(jié)點(diǎn)所在分支編碼的域。n個(gè)葉子結(jié)點(diǎn)存放在一維數(shù)組中，每個(gè)數(shù)組元素包括兩個(gè)域，一個(gè)存放葉子結(jié)點(diǎn)權(quán)值，一個(gè)是指向哈夫曼樹葉子結(jié)點(diǎn)的指針。定義如下：

typedef struct Node{//哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)

char bit[MB];// MB為哈夫曼編碼串最大長度

struct Node *lchild，*rchild;

} HuffmanTreeNode;

typedef struct{

int ?weight;

struct Node ?*Leaf;

} TreeLeaf;

TreeLeaf ?LeafNode[n];//葉子結(jié)點(diǎn)數(shù)組

二、哈夫曼樹的構(gòu)造設(shè)計(jì)

構(gòu)造哈夫曼樹前，先對n個(gè)葉子結(jié)點(diǎn)權(quán)值按升序排序，構(gòu)造二叉樹時(shí)避免多次循環(huán)查找最小和次小權(quán)值，只需從前往后依次取權(quán)值即可。

（一）算法思想

定義TreeLeaf結(jié)構(gòu)的輔助數(shù)組NLNode[n-1]，構(gòu)造哈夫曼樹時(shí)生成的中間結(jié)點(diǎn)，按照生成的先后順序依次加入到數(shù)組NLNode[n-1]中，則數(shù)組中的中間結(jié)點(diǎn)權(quán)值肯定是從小到大有序的。數(shù)組中Leaf域存放新生成的二叉樹的根結(jié)點(diǎn)地址。用K統(tǒng)計(jì)數(shù)組NLNode[n-1]中插入結(jié)點(diǎn)的個(gè)數(shù)。算法描述如下：

1. 初始化數(shù)組NLNode，weight域置為MAX（MAX大于n個(gè)葉子結(jié)點(diǎn)權(quán)值之和），Leaf置為NULL。

2. 根據(jù)數(shù)組LeafNode中的n個(gè)權(quán)值，生成n棵只有葉子結(jié)點(diǎn)的二叉樹，每個(gè)結(jié)點(diǎn)的bit域置“0”，二叉樹根結(jié)點(diǎn)地址存放在與其權(quán)值相對應(yīng)的Leaf域。

3. 置i=0，j=0，K=0，做以下操作：

（1）LeafNode[i].weight與NLNode[j].weight中取較小者賦給s1，Leaf域值賦給p1，并將其對應(yīng)的數(shù)組下標(biāo)增1。

（2）LeafNode[i].weight與NLNode[j]. weight中取較小者賦給s2，Leaf域值賦給p2，并將其對應(yīng)的數(shù)組下標(biāo)增1，p2所指結(jié)點(diǎn)的bit域置“1”。

（3）以p1，p2所指結(jié)點(diǎn)為左右子樹構(gòu)造一棵新的二叉樹，根結(jié)點(diǎn)的權(quán)值為s1+s2，bit域置“0”。將新生成的二叉樹根結(jié)點(diǎn)加入到數(shù)組NLNode中，K增1。

（4）當(dāng)K

4. 當(dāng)數(shù)組NLNode滿時(shí)，哈夫曼樹構(gòu)造結(jié)束。

例如排好序的權(quán)值集W={2，3，4，4，6}，構(gòu)造哈夫曼樹過程如圖1所示，根結(jié)點(diǎn)bit域值為“#”，不參與編碼。

（a）

（b）

（c）

（d）

（e）

圖1 哈夫曼樹構(gòu)造過程

（二）算法C語言[3]實(shí)現(xiàn)

void huffmantree（TreeLeaf *LeafNode，TreeLeaf *NLNode） {

HuffmanTreeNode *p;

int i;

for（i=0;i

NLNode[i].weight=MAX;

NLNode[i].Leaf=NULL;

}

for（i=0;i

p=（HuffmanTreeNode*）malloc（sizeof（Huffm

anTreeNode））;

if（！p） return;

p->weight=LeafNode[i].weight;

strcpy（p->bit，"0"）;

p->lchild=p->rchild=NULL;

LeafNode[i].Leaf=p;

}

int j=0，K=0，s1，s2;//s1，s2存放最小和次小權(quán)值

HuffmanTreeNode *p1，*p2;

i=0;

while（K

if（i

s1=LeafNode[i].weight;

p1=LeafNode[i].Leaf;

i++;

}

else{

s1=NLNode[j].weight;

p1=NLNode[j].Leaf;

j++;

}

if（i

s2=LeafNode[i].weight;

p2=LeafNode[i].Leaf;

i++;

}

else{

s2=NLNode[j].weight;

p2=NLNode[j].Leaf;

j++;

}

strcpy（p2->bit，"1"）;

p=（HuffmanTreeNode *）malloc（sizeof（Huf

fmanTreeNode））;

p->weight=NLNode[k].weight=s1+s2;

strcpy（p->bit，"0"）;

p->lchild=p1;

p->rchild=p2;

NLNode[k].Leaf=p;K++;

}

K--; strcpy（NLNode[K].Leaf->bit，"#"）;//樹的根結(jié)點(diǎn)不參與編碼

return;

}

三、哈夫曼編碼設(shè)計(jì)

（一）算法思想

在數(shù)組NLNode中從后往前依次取除根結(jié)點(diǎn)外的所有中間結(jié)點(diǎn)的地址，對哈夫曼樹從第二層起向下掃描各中間結(jié)點(diǎn)，求出葉子結(jié)點(diǎn)的哈夫曼編碼。算法敘述如下：

1. 置j=n-3，取p= NLNode[j].Leaf。

2. 將p所指結(jié)點(diǎn)的bit域值加到p所指結(jié)點(diǎn)的左孩子及右孩子bit域值的前面，j減1。

3. 重復(fù)2.直到數(shù)組NLNode中所有中間結(jié)點(diǎn)執(zhí)行完為止。

4. 各葉子結(jié)點(diǎn)的bit域符號(hào)串值就是其哈夫曼編碼。

編碼過程如圖2所示。（a）中p首先指向權(quán)值為11的結(jié)點(diǎn)，將其bit域值“1”加到權(quán)值為5、6的結(jié)點(diǎn)bit域值的前面，則權(quán)值為5的結(jié)點(diǎn)的bit域值就是“10”，權(quán)值為6的結(jié)點(diǎn)的bit域值就是“11”;（b）（c）依次類推。最后得到各個(gè)葉子結(jié)點(diǎn)的權(quán)值。

（二）算法C語言實(shí)現(xiàn)

void huffmancode（TreeLeaf *LeafNode，TreeLeaf *NLNode） {

int i，j;

char *cd=（char*）malloc（MB *sizeof（char））;

HuffmanTreeNode *p;

for（j=n-3;j>-1;j--）

{ ?p=NLNode[j].Leaf;

strcpy（cd，p->bit）;

strcat（cd，p->lchild->bit）;

strcpy（p->lchild->bit，cd）;

strcpy（cd，p->bit）;

strcat（cd，p->rchild->bit）;

strcpy（p->rchild->bit，cd）;

}

printf（"＼n各權(quán)值的哈夫曼編碼：＼n"）;

for（i=0;i

p=LeafNode[i].Leaf;

printf（"%d： ?%s＼n"，p->weight，p->bit）;

}

free（cd）;

return;

}

四、結(jié)束語

《數(shù)據(jù)結(jié)構(gòu)》課程中，傳統(tǒng)的哈夫曼編碼方法是在結(jié)構(gòu)體數(shù)組上構(gòu)造哈夫曼樹，編碼時(shí)從葉子結(jié)點(diǎn)向上到根結(jié)點(diǎn)逆向掃描2n-1個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度為O（n2）。在本教學(xué)過程中，在傳統(tǒng)編碼方法基礎(chǔ)上提出了另一種實(shí)現(xiàn)哈夫曼編碼的方法，哈夫曼樹采用二叉鏈表結(jié)構(gòu)，求編碼時(shí)從哈夫曼樹第二層向下到葉子結(jié)點(diǎn)掃描，時(shí)間復(fù)雜度為O（n）。編碼算法設(shè)計(jì)巧妙新穎，結(jié)構(gòu)清晰簡潔，這不但能拓展學(xué)生的算法設(shè)計(jì)思維，而且能提高學(xué)生的程序開發(fā)能力，在《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)中有一定的參考價(jià)值。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社，2011.

[2]鮑愛華，陳衛(wèi)衛(wèi)，等.基于“一題多解”的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)模式[J].計(jì)算機(jī)教育，2018（2）：119-123.

[3]黃容，趙毅.C語言程序設(shè)計(jì)[M].清華大學(xué)出版社，2012.