啟發(fā)式授課法在數(shù)據(jù)結(jié)構(gòu)教學(xué)中的運用

余艷?劉燕麗

摘要：存儲結(jié)構(gòu)和基于各種存儲結(jié)構(gòu)上基本操作的算法實現(xiàn)是數(shù)據(jù)結(jié)構(gòu)課程的重點教學(xué)內(nèi)容。分析了上述內(nèi)容教學(xué)過程中存在的問題，以有向圖十字鏈表存儲結(jié)構(gòu)和Prim算法程序?qū)崿F(xiàn)的教學(xué)過程為例，探討了啟發(fā)式授課方法在數(shù)據(jù)結(jié)構(gòu)課堂教學(xué)中的運用，實踐證明取得了良好的教學(xué)效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；課堂教學(xué)；啟發(fā)式；存儲結(jié)構(gòu)；算法實現(xiàn)

作者簡介：余艷（1980-），女，湖北襄陽人，武漢科技大學(xué)理學(xué)院，講師；劉燕麗（1980-），女，河南西平人，武漢科技大學(xué)理學(xué)院，講師。（湖北 武漢 430065）

基金項目：本文系武漢科技大學(xué)教學(xué)研究項目（項目編號：2012X51）、武漢科技大學(xué)教學(xué)研究項目（項目編號：2013x065）的研究成果。

中圖分類號：G642.0 文獻標(biāo)識碼：A 文章編號：1007-0079（2014）08-0098-02

數(shù)據(jù)結(jié)構(gòu)是信息類相關(guān)專業(yè)本科生必修的專業(yè)基礎(chǔ)課，該課程探討了各種經(jīng)典數(shù)據(jù)結(jié)構(gòu)的邏輯特性、存儲結(jié)構(gòu)以及相關(guān)算法，為后續(xù)課程提供了理論基礎(chǔ)和技術(shù)支持。數(shù)據(jù)結(jié)構(gòu)是課堂教學(xué)與實踐教學(xué)并重的課程，通常開設(shè)在本科二年級上學(xué)期，對于大學(xué)低年級本科生而言，課堂學(xué)習(xí)仍是獲取知識的重要渠道。文獻[1]指出在課堂教學(xué)中教師通過不斷設(shè)疑和釋疑，可以更好地展示自己的思維過程并揭示知識的來龍去脈，并引起教師教與學(xué)生學(xué)的思維共振。本文以武漢科技大學(xué)信息與計算科學(xué)系為例，分析數(shù)據(jù)結(jié)構(gòu)課程存儲結(jié)構(gòu)及算法實現(xiàn)的課堂教學(xué)中遇到的問題，并針對這些問題探討啟發(fā)式授課在數(shù)據(jù)結(jié)構(gòu)課堂教學(xué)中的實際運用方法及效果。

一、課堂教學(xué)中存在的問題

第一，數(shù)據(jù)結(jié)構(gòu)教材對知識的講解嚴謹簡潔，但是對知識的表達過于生硬，缺少對問題背景、存儲結(jié)構(gòu)和算法設(shè)計思想的討論；第二，部分學(xué)生在學(xué)習(xí)過程中習(xí)慣記憶各種存儲結(jié)構(gòu)的表示方法，卻未理解各種存儲結(jié)構(gòu)的設(shè)計原理，這些學(xué)生有可能獲得比較高的卷面分數(shù)，卻難以在未來學(xué)習(xí)和工作中靈活運用數(shù)據(jù)結(jié)構(gòu)知識；[2]第三，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程也是學(xué)生進行復(fù)雜程序設(shè)計的訓(xùn)練過程，部分學(xué)生反映可以輕松理解數(shù)據(jù)結(jié)構(gòu)中的算法策略，但對從算法到代碼的轉(zhuǎn)換工作卻感到困難。

二、存儲結(jié)構(gòu)的啟發(fā)式教學(xué)

數(shù)據(jù)結(jié)構(gòu)課程講授了線性表、棧、隊列、串、數(shù)組、廣義表、二叉樹和圖等經(jīng)典存儲結(jié)構(gòu)，如果直接將各種存儲方法灌輸給學(xué)生，勢必造成學(xué)生知其然而不能知其所以然，且容易導(dǎo)致課堂教學(xué)中問題2的發(fā)生。采用不斷創(chuàng)造問題情境的方法激發(fā)學(xué)生思考，使其主動參與到存儲結(jié)構(gòu)的設(shè)計過程中，則可以加深學(xué)生對存儲方法的理解，同時為將來根據(jù)應(yīng)用需求自行設(shè)計存儲結(jié)構(gòu)積累經(jīng)驗。下面以有向圖的十字鏈表為例討論存儲結(jié)構(gòu)教學(xué)中的啟發(fā)式講授方法。

啟發(fā)問題1：在正式講授十字鏈表結(jié)構(gòu)之前，詢問學(xué)生已學(xué)習(xí)的鄰接表及逆鄰接表在計算出度和入度時各有什么特點。通過回憶學(xué)生會發(fā)現(xiàn)，使用鄰接表時通過遍歷依附于頂點的單鏈表便可以輕松地計算出該頂點的出度，但計算入度則需要遍歷整個鄰接表結(jié)構(gòu)；使用逆鄰接表則恰恰相反，可以輕松計算出各頂點的入度，但計算出度則需遍歷整個逆鄰接表結(jié)構(gòu)。接下來教師引出，為了彌補鄰接表和逆鄰接表各自的不足，人們考慮設(shè)計另外一種存儲結(jié)構(gòu)，通過將鄰接表和逆鄰接表相結(jié)合從而得到十字鏈表結(jié)構(gòu)。這樣講解可以使學(xué)生明白十字鏈表結(jié)構(gòu)的設(shè)計初衷，同時領(lǐng)悟到各種存儲結(jié)構(gòu)的存在都有潛在需求。

啟發(fā)問題2：十字鏈表的結(jié)構(gòu)是怎樣的呢？首先引導(dǎo)學(xué)生分析頂點的特點并設(shè)計其存儲結(jié)構(gòu)。對于任何數(shù)據(jù)結(jié)構(gòu)而言，設(shè)計它的存儲結(jié)構(gòu)無非是考慮如何存儲數(shù)據(jù)元素以及元素間的關(guān)系。元素的存儲往往簡單，而關(guān)系的設(shè)計則需要動些腦筋。有向圖中的頂點即數(shù)據(jù)元素，它們具有相同的特性，結(jié)構(gòu)整齊劃一，因此可以考慮使用順序結(jié)構(gòu)存儲所有頂點。每個頂點元素的結(jié)構(gòu)就非常簡單了，如圖1（a）所示，其中data用于存放頂點信息。

啟發(fā)問題3：弧結(jié)點的結(jié)構(gòu)又應(yīng)該是怎樣的呢？根據(jù)十字鏈表的結(jié)構(gòu)定義，對于有向圖中的每個頂點有一個結(jié)點，每一條弧也有一個結(jié)點。這里有必要引導(dǎo)學(xué)生思考，怎樣用一個結(jié)點表示一條弧。學(xué)生會想到，表示一條弧需要給出弧尾和弧頭。那么進一步引導(dǎo)學(xué)生思考，在弧結(jié)點中如何表示弧尾和弧頭？學(xué)生會給出多種方案，比如直接存儲弧尾和弧頭頂點的信息；或是存儲弧尾和弧頭頂點的位置。這時，需要進一步比較兩種方案的優(yōu)劣。如果在弧結(jié)點中直接存儲弧尾和弧頭頂點的信息，那么在圖結(jié)構(gòu)中勢必存在頂點的多個備份，這樣一方面會導(dǎo)致存儲空間的浪費，另一方面修改某個頂點信息時，它的多個備份需要做相應(yīng)修改，如果沒有全部修改則會帶來數(shù)據(jù)不一致的問題。比較之后，學(xué)生會得出結(jié)論，在弧結(jié)點中存儲弧尾和弧頭的位置信息更合適。此時，繼續(xù)引導(dǎo)學(xué)生思考，如何表示弧尾和弧頭的位置？學(xué)生通常會想到可以用絕對的地址。此時可以提醒學(xué)生頂點存儲在數(shù)組中，在已知數(shù)組基址及元素下標(biāo)時，可以容易地計算出該元素的地址。進一步地，學(xué)生會想到可以用頂點在數(shù)組中的下標(biāo)表示位置信息。接下來再引出程序設(shè)計中的經(jīng)驗，當(dāng)使用順序結(jié)構(gòu)存儲數(shù)據(jù)元素時，為方便起見通常更傾向于使用下標(biāo)訪問元素，而不是使用指針。結(jié)合以上分析，學(xué)生會設(shè)計出如圖1（b）所示的弧結(jié)點。其中，tailvex表示弧尾頂點在頂點向量中的下標(biāo)；headvex表示弧頭頂點在頂點向量中的下標(biāo)。

啟發(fā)問題4：如上設(shè)計的弧結(jié)點結(jié)構(gòu)可以滿足常用操作的需求嗎？按照如上思路設(shè)計的弧結(jié)點可以描述出頂點間的邏輯關(guān)系，但是卻不足以滿足常用的操作需求。比如給定某個頂點尋找它的所有出弧或入弧，則需要遍歷圖中所有的弧結(jié)點，導(dǎo)致算法效率低下。為了能夠方便地找到頂點的所有鄰接點，有必要進一步改進弧結(jié)點的結(jié)構(gòu)設(shè)計。考慮將所有弧尾相同的弧結(jié)點鏈接起來形成一個行鏈表，順著這個鏈表就可以找到弧尾頂點的所有出弧，同理將弧頭相同的弧結(jié)點也鏈接起來形成一個列鏈表，可以方便地找到弧頭頂點的所有入弧。綜上分析，需要在弧結(jié)點中增加兩個指針域，得到如圖1（d）所示的弧結(jié)點結(jié)構(gòu)。其中，hlink表示指向弧頭相同的下一個弧結(jié)點的指針，tlink表示指向弧尾相同的下一個弧結(jié)點的指針。

啟發(fā)問題5：存放弧結(jié)點鏈表的頭指針應(yīng)該保存在哪里呢？為使圖的各種操作最為方便，由于行鏈表保存著所有弧尾頂點相同的弧，可以把它的頭指針和弧尾頂點保存在一起；同理列鏈表的頭指針則和弧頭頂點保存在一起。綜上分析，需要在頂點結(jié)點中增加兩個鏈域，如圖1（c）所示。其中data用于存放頂點本身信息，firstin指向第一條入弧，firstout指向第一條出弧。

十字鏈表存儲結(jié)構(gòu)的分析與設(shè)計完成后，有必要用實例來展示有向圖的十字鏈表結(jié)構(gòu)，如圖2所示。其中左圖為有向圖邏輯結(jié)構(gòu)，右圖為其對應(yīng)的十字鏈表結(jié)構(gòu)。按照如上啟發(fā)式方法進行存儲結(jié)構(gòu)的講解，可以使學(xué)生對各種存儲結(jié)構(gòu)產(chǎn)生更深刻的認識，使其成為知識的構(gòu)建者，而不再是被灌輸?shù)膶ο蟆?/p>

三、算法實現(xiàn)的啟發(fā)式教學(xué)

數(shù)據(jù)結(jié)構(gòu)課程包含一些經(jīng)典算法，如串的模式匹配、二叉樹的遍歷、圖的深度和廣度優(yōu)先遍歷、拓撲排序等。學(xué)生在學(xué)習(xí)這些算法的過程中，普遍反應(yīng)理解算法策略很輕松，但從算法轉(zhuǎn)化到代碼時就覺得困難重重了，在數(shù)據(jù)結(jié)構(gòu)課程的授課過程中加強對此環(huán)節(jié)的教學(xué)極為重要。依據(jù)多年教學(xué)經(jīng)驗來看，采用基于問題的啟發(fā)式教學(xué)方法能夠激發(fā)學(xué)生求解問題的熱情，擺脫枯燥厭煩的情緒，使其樂于思考算法到代碼的轉(zhuǎn)化方法，避免課堂教學(xué)中問題3的發(fā)生，同時為復(fù)雜程序設(shè)計積累經(jīng)驗和技巧。下面以Prim算法的程序?qū)崿F(xiàn)方法為例探討算法實現(xiàn)中的啟發(fā)式講授方法。

啟發(fā)問題2：如何存儲最小生成樹？對于含n個頂點的連通網(wǎng)，最小生成樹的頂點集和連通網(wǎng)的頂點集相同，邊的集合為連通網(wǎng)上邊集合的子集，因此最小生成樹的結(jié)果可使用包含n-1條邊的集合表示。進一步引導(dǎo)學(xué)生思考最小生成樹的每條邊如何表示。每條邊依附于兩個頂點且具備權(quán)值。在最小生成樹構(gòu)造過程中，需要用到最小兩棲邊，最小兩棲邊的兩個頂點分別位于集合U和集合V-U，所以邊的類型定義應(yīng)包含三個成員：beg為位于集合U中的頂點，end為位于集合V-U中的頂點，w為邊的權(quán)值。設(shè)計了最小生成樹的存儲結(jié)構(gòu)以后，就可以開始講解在該存儲結(jié)構(gòu)上跑算法的過程了，如圖3所示。通過圖3分步演示Prim算法程序?qū)崿F(xiàn)的整個過程，使學(xué)生對程序?qū)崿F(xiàn)有更直觀的理解。在講解過程中可以進一步引導(dǎo)學(xué)生思考有關(guān)代碼編寫的細節(jié)問題，例如啟發(fā)問題3。

四、結(jié)束語

在數(shù)據(jù)結(jié)構(gòu)課堂教學(xué)中強調(diào)對問題解決方法的思考，通過啟發(fā)式教學(xué)激發(fā)學(xué)生的研究性思維，讓他們積極參與到知識構(gòu)建與理解的過程中。按照本文方法進行課堂教學(xué)，學(xué)生普遍反應(yīng)對存儲結(jié)構(gòu)的授課內(nèi)容理解起來很輕松，數(shù)據(jù)結(jié)構(gòu)實驗課中編寫程序的思路也很清晰，實踐證明啟發(fā)式授課取得了良好的教學(xué)效果。由于同一個課堂內(nèi)學(xué)生在接受知識的能力上存在較大差異，如何兼顧層次不同的同學(xué)，因材施教達到更好的教學(xué)效果，是需要進一步研究的問題。

參考文獻：

[1]孫式武.課堂教學(xué)中師生思維同步的實現(xiàn)策略[J].教育理論與實踐，2013，33（8）：44-46.

[2]余艷，劉燕麗.數(shù)據(jù)結(jié)構(gòu)教學(xué)方法探討[J].計算機教育，2013，

（9）：56-58.

[3]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997.

（責(zé)任編輯：王意琴）