啟發(fā)式授課法在數據結構教學中的運用

余艷?劉燕麗

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

關鍵詞：數據結構；課堂教學；啟發(fā)式；存儲結構；算法實現

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

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

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

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

一、課堂教學中存在的問題

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

二、存儲結構的啟發(fā)式教學

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

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

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

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

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

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

十字鏈表存儲結構的分析與設計完成后，有必要用實例來展示有向圖的十字鏈表結構，如圖2所示。其中左圖為有向圖邏輯結構，右圖為其對應的十字鏈表結構。按照如上啟發(fā)式方法進行存儲結構的講解，可以使學生對各種存儲結構產生更深刻的認識，使其成為知識的構建者，而不再是被灌輸的對象。

三、算法實現的啟發(fā)式教學

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

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

四、結束語

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

參考文獻：

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

[2]余艷，劉燕麗.數據結構教學方法探討[J].計算機教育，2013，

（9）：56-58.

[3]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997.

（責任編輯：王意琴）