《數據結構》課程中哈夫曼編碼教學案例研究

王彩霞

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

關鍵詞：教學案例;數據結構;哈夫曼編碼

中圖分類號：G642 ? ? ? 文獻標志碼：A ? ? ? ? 文章編號：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

引言

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

一、數據結構設計

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

typedef struct Node{//哈夫曼樹結點結構

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

struct Node *lchild，*rchild;

} HuffmanTreeNode;

typedef struct{

int ?weight;

struct Node ?*Leaf;

} TreeLeaf;

TreeLeaf ?LeafNode[n];//葉子結點數組

二、哈夫曼樹的構造設計

構造哈夫曼樹前，先對n個葉子結點權值按升序排序，構造二叉樹時避免多次循環查找最小和次小權值，只需從前往后依次取權值即可。

（一）算法思想

定義TreeLeaf結構的輔助數組NLNode[n-1]，構造哈夫曼樹時生成的中間結點，按照生成的先后順序依次加入到數組NLNode[n-1]中，則數組中的中間結點權值肯定是從小到大有序的。數組中Leaf域存放新生成的二叉樹的根結點地址。用K統計數組NLNode[n-1]中插入結點的個數。算法描述如下：

1. 初始化數組NLNode，weight域置為MAX（MAX大于n個葉子結點權值之和），Leaf置為NULL。

2. 根據數組LeafNode中的n個權值，生成n棵只有葉子結點的二叉樹，每個結點的bit域置“0”，二叉樹根結點地址存放在與其權值相對應的Leaf域。

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

（1）LeafNode[i].weight與NLNode[j].weight中取較小者賦給s1，Leaf域值賦給p1，并將其對應的數組下標增1。

（2）LeafNode[i].weight與NLNode[j]. weight中取較小者賦給s2，Leaf域值賦給p2，并將其對應的數組下標增1，p2所指結點的bit域置“1”。

（3）以p1，p2所指結點為左右子樹構造一棵新的二叉樹，根結點的權值為s1+s2，bit域置“0”。將新生成的二叉樹根結點加入到數組NLNode中，K增1。

（4）當K

4. 當數組NLNode滿時，哈夫曼樹構造結束。

例如排好序的權值集W={2，3，4，4，6}，構造哈夫曼樹過程如圖1所示，根結點bit域值為“#”，不參與編碼。

（a）

（b）

（c）

（d）

（e）

圖1 哈夫曼樹構造過程

（二）算法C語言[3]實現

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存放最小和次小權值

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，"#"）;//樹的根結點不參與編碼

return;

}

三、哈夫曼編碼設計

（一）算法思想

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

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

2. 將p所指結點的bit域值加到p所指結點的左孩子及右孩子bit域值的前面，j減1。

3. 重復2.直到數組NLNode中所有中間結點執行完為止。

4. 各葉子結點的bit域符號串值就是其哈夫曼編碼。

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

（二）算法C語言實現

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各權值的哈夫曼編碼：＼n"）;

for（i=0;i

p=LeafNode[i].Leaf;

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

}

free（cd）;

return;

}

四、結束語

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

參考文獻：

[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].清華大學出版社，2011.

[2]鮑愛華，陳衛衛，等.基于“一題多解”的數據結構實踐教學模式[J].計算機教育，2018（2）：119-123.

[3]黃容，趙毅.C語言程序設計[M].清華大學出版社，2012.