杜敏　郭珊珊　潘鵬　陶駿

摘要：探討了哈夫曼樹的教學(xué)要點(diǎn)及教學(xué)方法，以哈夫曼樹的定義和意義為教學(xué)內(nèi)容的開端，分步介紹了哈夫曼樹的構(gòu)造和運(yùn)用方法，以典型的電文傳輸為例，剖析了哈夫曼樹的要點(diǎn)以及編碼過程的注意點(diǎn)。

關(guān)鍵詞：教學(xué)設(shè)計;哈夫曼樹;教學(xué)模式;問題驅(qū)動

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）02-0106-03

Abstract： This paper probes into the teaching points and teaching methods of Huffman tree. Taking the definition and significance of Huffman tree as the beginning of teaching content， it introduces the construction and application methods of Huffman tree step by step. Taking typical message transmission as an example， it analyses the main points of Huffman tree and the points for attention in coding process.

Key words： curriculum design; huffman tree; teaching model; problem driven

《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計算機(jī)學(xué)院學(xué)生所需要學(xué)習(xí)的一門重要必修課程。課程要求學(xué)生會把生活中大量的復(fù)雜問題簡單化，對問題進(jìn)行抽象建模，繼而以特定的數(shù)據(jù)類型和存儲結(jié)構(gòu)把他們存儲到計算機(jī)中去，從而可以實(shí)現(xiàn)某種操作。數(shù)據(jù)結(jié)構(gòu)的研究范圍主要涉及各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，運(yùn)用算法對數(shù)據(jù)進(jìn)行有規(guī)則的操作。比如排序和查找，實(shí)現(xiàn)這些操作的具體步驟就稱之為算法，算法就是對特定的數(shù)據(jù)類型進(jìn)行某些操作，從而達(dá)到某種目的的過程。

《數(shù)據(jù)結(jié)構(gòu)與算法》中以樹形結(jié)構(gòu)為非線性結(jié)構(gòu)代表展開教學(xué)。樹形結(jié)構(gòu)是有層次的嵌套結(jié)構(gòu)，它在計算機(jī)科學(xué)中具有廣泛的應(yīng)用，反映了數(shù)據(jù)元素之間的層次結(jié)構(gòu)。本文選擇了樹形結(jié)構(gòu)中的哈夫曼樹，以課件的形式進(jìn)行教學(xué)，能有效開展案例教學(xué)，實(shí)現(xiàn)學(xué)習(xí)過程控制的教學(xué)策略，強(qiáng)化學(xué)習(xí)效果。

1 教學(xué)目標(biāo)

教學(xué)目標(biāo)是指在教學(xué)活動中教學(xué)者所期待的所有學(xué)生反饋的學(xué)習(xí)結(jié)果，是課堂教學(xué)的出發(fā)點(diǎn)，教學(xué)目標(biāo)始終是教學(xué)活動的過程主線。教師以教學(xué)目標(biāo)為中心，制定能夠引導(dǎo)學(xué)生學(xué)習(xí)的教學(xué)策略，學(xué)生以教師的教學(xué)目標(biāo)為目標(biāo)，積極展開學(xué)習(xí)。根據(jù)學(xué)生學(xué)習(xí)結(jié)果的反饋，心理學(xué)家概括出不同的學(xué)習(xí)結(jié)果，代表之一就是智力技能目標(biāo)。從以上幾種分類的結(jié)果可以看到一點(diǎn)，哈夫曼樹一課中的教學(xué)目標(biāo)主要為智力技能目標(biāo)。那么哈夫曼樹的教學(xué)目標(biāo)即是學(xué)生學(xué)完本課件的內(nèi)容之后，能夠根據(jù)給定的條件構(gòu)造哈夫曼樹，并且能夠?qū)懗銎渥疃痰膸?quán)路徑長度。

2 學(xué)習(xí)者特征

傳播學(xué)原理闡釋了有效的訊息傳遞的條件，傳播者必須了解接受者對訊息的態(tài)度、有關(guān)的知識基礎(chǔ)和傳播技能。教學(xué)活動也是一樣，教學(xué)者設(shè)計的一切教學(xué)活動都是圍繞學(xué)生的學(xué)習(xí)?？梢姡瑢W(xué)習(xí)者學(xué)習(xí)特征的分析是很有必要的，有效針對學(xué)習(xí)者的學(xué)習(xí)風(fēng)格和學(xué)習(xí)能力，制定切合該類學(xué)習(xí)者學(xué)習(xí)特點(diǎn)的教學(xué)策略，從而有效闡明學(xué)習(xí)目標(biāo)，達(dá)到教學(xué)效果。因此有效的教學(xué)設(shè)計必定要考慮到學(xué)習(xí)者的學(xué)習(xí)特征。學(xué)習(xí)者學(xué)習(xí)的一個重要特征就是學(xué)習(xí)的初始能力，學(xué)生學(xué)習(xí)結(jié)果的性質(zhì)極大部分是由于學(xué)生對學(xué)習(xí)認(rèn)知的準(zhǔn)備狀態(tài)所影響的。學(xué)習(xí)者原本儲備的知識基礎(chǔ)是自身學(xué)習(xí)新知識的重要內(nèi)部條件，哈夫曼樹面向的學(xué)習(xí)者在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法這一課程的內(nèi)容以前已經(jīng)學(xué)習(xí)了C++程序設(shè)計語言及計算機(jī)導(dǎo)論等前導(dǎo)課程的內(nèi)容，并且在之前就已經(jīng)學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)中的樹的知識。因此學(xué)生通過學(xué)習(xí)此前的教學(xué)內(nèi)容以及前導(dǎo)課程的學(xué)習(xí)已經(jīng)具備了一定的解決問題的能力和計算機(jī)程序的編寫能力。

3 教學(xué)內(nèi)容

觀察一個例子—判定樹：

判定樹指的是在處理事件的詳細(xì)分析中，用樹形邏輯圖對單個功能與活動的一種詳細(xì)分析方法。大多數(shù)問題的解決都會用到判定樹，這些判斷結(jié)構(gòu)的設(shè)計直接影響著程序的執(zhí)行效率。例如，編制一個將百分制轉(zhuǎn)換成60分以下，70分以下，80分以下，90分以下，90分以上這五個等級輸出的程序，用下列簡單形式可以快速編寫：

if（score < 60）

System.out.print（“bad”）;

else if（score <70）

System.out.print（“pass”）;

else if（score <80）

System.out.print（“general”）;

else if（score <90）

System.out.print（“good”）;

else

System.out.print（“pretty good”）;

若考慮上述程序所耗費(fèi)的時間，就會發(fā)現(xiàn)該程序的缺陷。60分以下的情況程序只需要判斷一次，而60～70分的情況程序需要判斷兩次，以此類推，若是分?jǐn)?shù)情況較多那判斷的次數(shù)豈不是更多，況且實(shí)際應(yīng)用中在五個等級上所分布的學(xué)生成績是不均勻的。當(dāng)學(xué)生百分制成績的錄入量很大時，上述判定過程需要反復(fù)調(diào)用，此時程序的執(zhí)行效率將成為一個嚴(yán)重問題。

如表1的表格就是在一次考試中數(shù)學(xué)課程的各分?jǐn)?shù)段的分布情況：

現(xiàn)按照表格條件利用哈夫曼樹來尋找一顆最佳判定樹，即總的比較次數(shù)最少的判定樹。

第一種構(gòu)造方式：

第二種構(gòu)造方式：

顯然后者的判定效率要比前者高。

所以稱判定過程最優(yōu)的二叉樹為最優(yōu)二叉樹，即哈夫曼樹。

3.1 概念

路徑：樹中一個結(jié)點(diǎn)到達(dá)其子孫所經(jīng)過的結(jié)點(diǎn)集合。

路徑長度：在樹的一條路徑中，每走過一個結(jié)點(diǎn)路徑長度都要加一。

權(quán)值：每個樹結(jié)點(diǎn)所在的數(shù)值，通常指字符對應(yīng)的二進(jìn)制編碼出現(xiàn)的概率。

結(jié)點(diǎn)的帶權(quán)路徑長度：指的是在一棵樹中，結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。

3.2 哈夫曼樹的構(gòu)造

哈夫曼樹被定義為一種帶權(quán)路徑長度最短的樹。要使得二叉樹的WPL值最小，那么該二叉樹的根結(jié)點(diǎn)以下的葉子結(jié)點(diǎn)為所有權(quán)值中較大的值，而所有權(quán)值中較小的值都會遠(yuǎn)離該二叉樹的根結(jié)點(diǎn)。哈夫曼善于總結(jié)，他根據(jù)這一特點(diǎn)，提出了一種構(gòu)造最優(yōu)二叉樹的方法——哈夫曼算法：

給定n個數(shù)值為權(quán)值，要求構(gòu)造一棵最優(yōu)二叉樹即哈夫曼樹。給出哈夫曼樹的構(gòu)造規(guī)則：

（1） 在給定的n個權(quán)值中選出兩個最小的值，讓它們構(gòu)成一棵新的二叉樹，新二叉樹的左右葉子結(jié)點(diǎn)的值就是它們的值，新樹的根結(jié)點(diǎn)的權(quán)值就是這兩個葉子結(jié)點(diǎn)權(quán)值的和;

（2） 在原來給定的所有n個權(quán)值中刪除上一步已用的兩個最小權(quán)值，并將新二叉樹的權(quán)值加入n-2個權(quán)值中去;

（3） 重復(fù)上面兩個步驟，當(dāng)所有權(quán)值都出現(xiàn)在這一棵二叉樹上時，這棵樹就是所需要構(gòu)造的哈夫曼樹。

這里要注意幾點(diǎn)：

（1） 哈夫曼樹不唯一;

（2） 哈夫曼樹的子樹也是哈夫曼樹;

（3） 哈夫曼樹中無度為1的結(jié)點(diǎn);

（4） 有n個葉子結(jié)點(diǎn)的哈夫曼樹，其總結(jié)點(diǎn)數(shù)為2n-1。

在處理問題時，我們設(shè)立的目標(biāo)不同，解決問題的過程中使用的方法也就有所不同。但是解決方法一定是要符合處理條件的。比如上述的二叉樹，要使得構(gòu)造的樹帶權(quán)路徑長度最小，那么它所涉及的處理方法可能要求達(dá)到某種空間資源的最小化，或者時間的最小化，于是哈夫曼樹在理論上便有了應(yīng)用價值。

3.3 哈夫曼樹在編碼中的應(yīng)用

用于通信編碼：

在電報通訊中，電文是需要在字符和二進(jìn)制編碼之間相互轉(zhuǎn)換從而進(jìn)行傳送的，電文以二進(jìn)制的0，1序列傳送。在發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進(jìn)制的0，1序列，而在接收端又需要把接收的0，1序列轉(zhuǎn)換成對應(yīng)的字符序列。

例如給出的這段電文：WRGPWPRGGRPPGPWRGP

電文中使用了W，P，G，R這四種字符，每個字符出現(xiàn)的頻率分別對應(yīng)3，6，5，4，將它們進(jìn)行二進(jìn)制等長編碼，則編碼依次為W：00? P：01R：10? G：11

所發(fā)電文為：

00101101 00011011 111001 0111 01? ?00101101

采用不等長編碼容易產(chǎn)生二義性或者多義性。這里有一個例子，A：010，B：0101，C：001，D：1010字符A的編碼010與字符B的編碼0101的前一部分重合。在這種情況下，0101010，同樣表示了BBA的代碼和AD的代碼，這種情況的編碼就產(chǎn)生了譯碼的二義性。

所以，采用不等長編碼容易出現(xiàn)二義性。為了解決這個問題，可以將字符集里的每個字符賦予葉子結(jié)點(diǎn)的含義，這樣就能生成一顆編碼二叉樹，使該字符結(jié)點(diǎn)的權(quán)值表示的是字符出現(xiàn)頻率的含義，有了這些條件之后便能求出樹的最小帶權(quán)路勁長度，其表示的含義就是傳送電文的最短長度。這里就存在以頻率賦予權(quán)值所出現(xiàn)的哈夫曼樹的問題。

比如此處存在7個字符{H，I，J，K，L，M，N}，這7個字符的出現(xiàn)頻率為{5，24，7，17，34，5，13}，若將它們存入至文件中去，可使用哈夫曼樹構(gòu)造不等長編碼進(jìn)行存儲，并且符合前綴編碼的要求。

H：111? I：01 J：111K：00 L：0M：11 N：11構(gòu)造樹形如圖3所示：

哈夫曼樹構(gòu)造完成以后，須從葉子結(jié)點(diǎn)出發(fā)走到根部從而求出編碼。

構(gòu)造過程總結(jié)：

（1） 對兩個最小者的選擇為雙親下標(biāo)為0的結(jié)點(diǎn);

（2） 對選出的兩個最小者，修改雙親下標(biāo)為新結(jié)點(diǎn)的下標(biāo);

（3） 新結(jié)點(diǎn)的左右孩子修改為所選的兩個新結(jié)點(diǎn)的下標(biāo);

（4） 新結(jié)點(diǎn)的權(quán)值為兩個結(jié)點(diǎn)權(quán)值之和。

最后給出哈夫曼編碼的簡要算法：

//結(jié)點(diǎn)的結(jié)構(gòu)體類型

public class HTNode

{public int weight;? //結(jié)點(diǎn)的權(quán)值

public int parent;? //結(jié)點(diǎn)的雙親

public intlchild;? ?//結(jié)點(diǎn)左孩子的下標(biāo)

public intrchild;? //結(jié)點(diǎn)右孩子的下標(biāo)

};

voidCreateHuffmanTree（ListHT，int n）

{

if（n<=1）return;

m=2*n-1;

HT=new HTNode[m+1];

//0單元未使用，此處需要動態(tài)分配m+1個單元，HT[m]為根結(jié)點(diǎn)

for（i=1;i<=m;i++）

//將1～m的結(jié)點(diǎn)雙親，左右孩子的下標(biāo)都初始化為0

{

HT[i].parent=0;

HT[I].lchild=0;

HT[i].rchild=0;

//輸入n個葉結(jié)點(diǎn)的權(quán)值

for（i=1;i<=n;i++）

{

System.out.print（HT[i].weight）;

}}}

4 教學(xué)策略

教學(xué)設(shè)計是一個系統(tǒng)過程。 在哈夫曼樹教學(xué)設(shè)計中有如下的教學(xué)策略。

概念的教學(xué)策略。該教學(xué)設(shè)計中必須講解的概念有：路徑、路徑長度、樹的路徑長度、帶權(quán)的路徑長度、樹的帶權(quán)的路徑長度、空心二叉樹和哈夫曼樹等。該教學(xué)設(shè)計中的概念的講解使用如下的組織方式。講解概念所用方法：使用文本直接呈現(xiàn)哈夫曼樹所涉及的知識概念。使用動畫圖表演示概念的簡單實(shí)例。介紹完概念后，普及哈夫曼樹在編碼中的實(shí)際應(yīng)用，用以鍛煉學(xué)習(xí)者的思考能力，進(jìn)而保持對哈夫曼樹知識的注意。給出相關(guān)概念的練習(xí)題，類型為填空題以及選擇題。給出進(jìn)階應(yīng)用編程題，用以鍛煉學(xué)習(xí)者的思維能力以及編程能力。

規(guī)則的教學(xué)策略。該教學(xué)設(shè)計的規(guī)則為哈夫曼樹的構(gòu)造算法。采用的教學(xué)方法是規(guī)則—實(shí)例的方法。為了使學(xué)生能有效地學(xué)習(xí)哈夫曼樹知識，采用圖形與文本相結(jié)合的方式，交錯傳遞哈夫曼樹的知識概念及應(yīng)用。即先以文本的形式呈現(xiàn)哈夫曼樹的構(gòu)造算法，接著再以圖形動畫演示用構(gòu)造算法構(gòu)造哈夫曼樹及求哈夫曼樹的帶權(quán)路徑長度的過程。講解完后提供習(xí)題小測驗，類型為填空題以及選擇題。學(xué)生回答問題之后，教學(xué)者對學(xué)生的答案進(jìn)行檢查，如果學(xué)生的答題情況很差即沒有答對所列題目中的百分之八十，下次課程則應(yīng)繼續(xù)鞏固基礎(chǔ)概念，調(diào)整學(xué)習(xí)進(jìn)度從而達(dá)到教學(xué)效果。

5 總結(jié)

完整的教學(xué)設(shè)計應(yīng)包含教學(xué)目標(biāo)、學(xué)習(xí)者特征的分析以及教學(xué)內(nèi)容形式的確定。學(xué)生是教學(xué)活動的關(guān)鍵，教學(xué)設(shè)計應(yīng)圍繞學(xué)生的理解能力來開展。對于哈夫曼樹教學(xué)設(shè)計來說，它所涉及的思維傳達(dá)方式尤其重要。因哈夫曼樹一課中的學(xué)習(xí)內(nèi)容多且知識點(diǎn)間的關(guān)系復(fù)雜，所以要將這種抽象的邏輯理念表示成超文本的形式是非常困難的，但是在教學(xué)設(shè)計中編排圖片、動畫極大優(yōu)化了學(xué)習(xí)效果。

參考文獻(xiàn)：

[1] 火旺.數(shù)據(jù)結(jié)構(gòu)與算法[M].西安：西安電子科技大學(xué)出版社，2005：125-127.

[2] 克抗.計算機(jī)輔助教育[M].北京：高等教育出版社，1997.

[3] 齊超.哈夫曼編碼及其應(yīng)用[J].鄭州市電子信息工程學(xué)校學(xué)報，2014，12（1）：256.

[4] 太山，郭觀七，李文彬.課堂設(shè)問的技巧及其在《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)中的應(yīng)用[J].湖南理工學(xué)院學(xué)報：自然科學(xué)版，2015（1）：81-83.

[5] 哈夫曼算法在分類優(yōu)化應(yīng)用中方的缺陷及修正[J]東華大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院學(xué)報，2010，9（7）：60-62.

[6] 孟凡榮，賈杰，王興偉.網(wǎng)絡(luò)工程專業(yè)創(chuàng)新性實(shí)踐課程體系構(gòu)建與實(shí)施[J].計算機(jī)教育，2013（14）：104-108.

[7] 逯鵬，張贊.數(shù)據(jù)結(jié)構(gòu)課程教學(xué)方法的研究和實(shí)踐[J].教育教學(xué)論壇，2015（18）：121-123.

[8] 瑩.哈夫曼樹遍歷算法的優(yōu)化[J].安徽電子信息技術(shù)學(xué)院學(xué)報，2009，25（5）：7235.

【通聯(lián)編輯：王力】