余艷?劉燕麗

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

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

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

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

中圖分類號：G642.0 文獻(xiàn)標(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é)與實(shí)踐教學(xué)并重的課程，通常開設(shè)在本科二年級上學(xué)期，對于大學(xué)低年級本科生而言，課堂學(xué)習(xí)仍是獲取知識的重要渠道。文獻(xiàn)[1]指出在課堂教學(xué)中教師通過不斷設(shè)疑和釋疑，可以更好地展示自己的思維過程并揭示知識的來龍去脈，并引起教師教與學(xué)生學(xué)的思維共振。本文以武漢科技大學(xué)信息與計(jì)算科學(xué)系為例，分析數(shù)據(jù)結(jié)構(gòu)課程存儲結(jié)構(gòu)及算法實(shí)現(xiàn)的課堂教學(xué)中遇到的問題，并針對這些問題探討啟發(fā)式授課在數(shù)據(jù)結(jié)構(gòu)課堂教學(xué)中的實(shí)際運(yùn)用方法及效果。

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)束語

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

參考文獻(xiàn)：

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

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

（9）：56-58.

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

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