圖示教學(xué)法在數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)中的應(yīng)用

沙宗堯 邊馥苓

摘要:數(shù)據(jù)結(jié)構(gòu)和算法的教學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)最重要的教學(xué)內(nèi)容之一,特別是在復(fù)雜的算法分析時(shí),由于具有抽象性和較強(qiáng)的邏輯性,不采用好的教學(xué)方法,往往是事倍功半。本文提出用圖示教學(xué)法教授數(shù)據(jù)結(jié)構(gòu)中的算法,并以圖狀結(jié)構(gòu)中的最小生成樹(shù)算法為例,詳細(xì)介紹了該圖示方法描述數(shù)據(jù)結(jié)構(gòu)算法過(guò)程,可以為數(shù)據(jù)結(jié)構(gòu)的教學(xué)提供參考。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);算法;圖示教學(xué)法;最小生成樹(shù)

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

1背景

數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)的專業(yè)基礎(chǔ)課,其重要性不言而喻,在教學(xué)過(guò)程中需要運(yùn)用多種教學(xué)方法,讓學(xué)生領(lǐng)會(huì)算法實(shí)現(xiàn)的過(guò)程和本質(zhì),加深對(duì)所學(xué)知識(shí)的理解、記憶和應(yīng)用。在數(shù)據(jù)結(jié)構(gòu)和算法課程教學(xué)中,圖狀結(jié)構(gòu)的教學(xué)是一個(gè)難點(diǎn),特別是涉及到圖的具體應(yīng)用時(shí),更讓學(xué)生難以掌握,本文將圖示教學(xué)法應(yīng)用到數(shù)據(jù)結(jié)構(gòu)中關(guān)于圖狀結(jié)構(gòu)的一個(gè)典型應(yīng)用——最小生成樹(shù)問(wèn)題,給出該教學(xué)方法的基本方法和過(guò)程,取得了良好的教學(xué)效果。

最小生成樹(shù)是圖狀(網(wǎng)絡(luò))結(jié)構(gòu)中一個(gè)典型的實(shí)踐應(yīng)用,可以解決實(shí)際中諸如公路網(wǎng)的規(guī)劃,即在n個(gè)城市中,如何規(guī)劃n-1條公路,使得n個(gè)城市都可以連接起來(lái),而所有城市間的連接線長(zhǎng)度的總和最短(所要修建的公路長(zhǎng)度最短,因而費(fèi)用最少)。

對(duì)于這個(gè)典型的應(yīng)用,絕大多數(shù)教科書均介紹了普里姆(Prim)算法,用于求最小生成樹(shù)問(wèn)題,然而教科書對(duì)這個(gè)算法實(shí)現(xiàn)的論述,一般是先介紹應(yīng)用背景,然后就給出算法實(shí)現(xiàn)的過(guò)程,缺少形象的算法分析過(guò)程,課堂教學(xué)講解如果按照這種方式去傳授,學(xué)生在理解上十分吃力,而且不能有效地長(zhǎng)期記憶。筆者結(jié)合自己在教學(xué)中的經(jīng)驗(yàn),將以上算法采用了圖示教學(xué)法來(lái)分析其基本原理和實(shí)現(xiàn)過(guò)程,并給出算法實(shí)現(xiàn)過(guò)程,取得了良好的效果。

2教學(xué)方法

圖示教學(xué)法就是用各種圖形表示的方法描述問(wèn)題、引導(dǎo)學(xué)生的思考,增強(qiáng)對(duì)新知識(shí)的記憶,并在教學(xué)中被廣泛使用。最小生成樹(shù)屬于網(wǎng)絡(luò)的實(shí)踐應(yīng)用,下面以圖1為例,用圖示教學(xué)法來(lái)對(duì)最小生成樹(shù)算法進(jìn)行圖示過(guò)程分析。

假設(shè)某一區(qū)域內(nèi)有n個(gè)城市,現(xiàn)要為這些城市修建城間公路,使得任意兩城市間都能夠相互通達(dá)(連通),由于要求所有的城市都在該公路網(wǎng)上,某兩個(gè)城市間的道路稱為一個(gè)路段,則修建的道路路段總數(shù)應(yīng)等于n-1個(gè)(容易理解:如果路段總數(shù)小于n-1,則會(huì)有存在城市不能處在該道路網(wǎng)的節(jié)點(diǎn)上;如果路段總數(shù)大于n-1則會(huì)存在某兩個(gè)城市間有至少兩個(gè)路段,則路段距離的總和將不是最小),先從這些城市中任選一個(gè)作為種子,把剩下的城市用路段連接到由該種子城市為起始點(diǎn)的城市網(wǎng)絡(luò)中,保證路段長(zhǎng)度總和最小(最優(yōu)路段網(wǎng)),則最后連接好的路段即為最小生成樹(shù)。

如圖1,每個(gè)帶圈的數(shù)字表示一個(gè)城市,城市間的邊表示城市間的距離,如果兩城市間沒(méi)有邊存在,則表示這兩個(gè)城市間不適宜修道路(如有山脈或河流隔斷,造價(jià)太高),假設(shè)種子城市為數(shù)字1(選定的網(wǎng)絡(luò)的起始頂點(diǎn)),通過(guò)圖示教學(xué)法求最優(yōu)路段網(wǎng)的過(guò)程如圖2:

圖中,Li-j表示城市i與城市j間的距離,例如在(b)中,當(dāng)把城市2加入到最優(yōu)路段網(wǎng)后,城市3、4、6與該最優(yōu)路段網(wǎng)的距離發(fā)生了變化,例如城市3,由于由L1-3(=∞)> L2-3(=5),故其與最優(yōu)路段網(wǎng)的距離由原先的∞也轉(zhuǎn)變?yōu)?

首先構(gòu)造一個(gè)初始最優(yōu)路段網(wǎng),但該網(wǎng)絡(luò)只有一個(gè)節(jié)點(diǎn),即“種子城市”,其位于圖2(a)中的中心圓圈內(nèi),圈外的節(jié)點(diǎn)稱為外圍節(jié)點(diǎn)或外圍城市。然后根據(jù)圖1城市間的距離(網(wǎng)絡(luò)節(jié)點(diǎn)間的邊的權(quán)值),求其它所有城市(網(wǎng)絡(luò)節(jié)點(diǎn))與種子城市間的距離(通過(guò)訪問(wèn)網(wǎng)絡(luò)的物理存儲(chǔ)結(jié)構(gòu)如鄰接表獲取),該圖表示僅通過(guò)了種子城市來(lái)連接所有的外圍其它城市,圖中中心圓圈外的城市當(dāng)前還沒(méi)有加入到最優(yōu)路段網(wǎng)規(guī)劃中,圈外連接每個(gè)外圍城市與中心圓圈的實(shí)線表示該城市如果按當(dāng)前規(guī)劃方案加入到該路段網(wǎng)時(shí)所需要建造的路段長(zhǎng)度(即網(wǎng)絡(luò)邊的權(quán)),圈內(nèi)的虛線表示當(dāng)前外圍城市通過(guò)某一個(gè)最優(yōu)路段網(wǎng)中的某城市為“橋梁”,而進(jìn)入到該網(wǎng)絡(luò)中。例如,城市2如果通過(guò)城市1進(jìn)入規(guī)劃網(wǎng),則需要修建長(zhǎng)度為16(僅表示相對(duì)數(shù)值)的道路,城市5要修建長(zhǎng)度19的道路,城市6要修建長(zhǎng)度21的道路,而城市3和城市4無(wú)法通過(guò)城市1來(lái)連接到最優(yōu)路段網(wǎng)中(距離為無(wú)窮大,∞),而必須通過(guò)其它城市作為“橋梁”,來(lái)進(jìn)入該規(guī)劃網(wǎng)絡(luò)中。很明顯,如果按照該方案來(lái)把所有的外圍城市都加入到初始最優(yōu)路段網(wǎng),得到的路段網(wǎng)如圖2(g),需要修建的路段網(wǎng)總長(zhǎng)度為∞,顯然不是最優(yōu)路段網(wǎng)。

注意到為了使規(guī)劃的路段網(wǎng)是最優(yōu)的(路段長(zhǎng)度總和最小),只要保證每次加入到最優(yōu)路段網(wǎng)中的城市都具有最短路段長(zhǎng)度,則最后的路段總長(zhǎng)度也必然最小。在圖2(a)中,城市2與種子城市具有最小的距離(16),因而不可能找到其它任何一個(gè)路段,實(shí)現(xiàn)“種子城市與其它外圍城市實(shí)現(xiàn)互連時(shí),種子城市到其它任意一個(gè)城市的路段距離小于該值”,因而路段②-①必然是滿足種子城市連通其它城市的最優(yōu)路段,將城市2加入到最優(yōu)路段網(wǎng)后,得到圖2(b)。注意到當(dāng)城市2加入到最優(yōu)路段網(wǎng)后,城市3、4、6如果是通過(guò)城市2為“橋梁”(圖中的虛線所示),加入到該最優(yōu)路段網(wǎng)中,可以使各自的路段長(zhǎng)度由原先的∞、∞和21分別縮短到5、6、11(其它城市通過(guò)城市2無(wú)法實(shí)現(xiàn)路段長(zhǎng)度縮短,因?yàn)楸３植蛔?,此時(shí)路段總長(zhǎng)度也由原先的∞縮小到57(即16+5+6+19+11),較圖2(a),該方案有了很大的進(jìn)步。然而該網(wǎng)絡(luò)仍不是最優(yōu)路段網(wǎng),因?yàn)槠鋬H保證了路段②-①的最優(yōu)性(注意圓圈內(nèi)的網(wǎng)絡(luò)是最優(yōu)的),而其它城市到該網(wǎng)絡(luò)中的路段并非最優(yōu),這樣不能保證路段總長(zhǎng)度最小。

進(jìn)一步注意到,在所有的當(dāng)前外圍城市中,城市3距離最優(yōu)路段網(wǎng)的距離最短(5),也就是為了使當(dāng)前最優(yōu)路段網(wǎng)(圓圈內(nèi)的城市及連線)與其它外圍城市能夠?qū)崿F(xiàn)連通,且連通后的路段總長(zhǎng)度最小,所以當(dāng)前應(yīng)加入城市3(圖2(c))。城市3的加入或許可以使得其它的外圍城市通過(guò)該城市為“橋梁”,而縮短外圍城市到最優(yōu)路段網(wǎng)的距離(當(dāng)然這里城市3的加入實(shí)際并沒(méi)有使其它城市到最優(yōu)路段網(wǎng)的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優(yōu)路段網(wǎng)中(因?yàn)樵谟嘞碌耐鈬鞘兄?城市4到最優(yōu)路段網(wǎng)的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優(yōu)路段網(wǎng)的距離由原來(lái)的19縮短到18(其它路段不變)。第5步將城市6加入到最優(yōu)路段網(wǎng)中(圖2(e)),該城市的加入沒(méi)有影響余下的城市(當(dāng)前僅剩一個(gè)城市,即城市5),最后將城市5加入到最優(yōu)路段網(wǎng)中(圖2(f))。得到的最終的最優(yōu)路段網(wǎng)如圖2(h),其路段長(zhǎng)度的總和為56(16+5+11+6+18)。

3算法求解

有了如上的圖示教學(xué)法描述的計(jì)算最小生成樹(shù)實(shí)現(xiàn)基本過(guò)程,在講解算法時(shí)就比較容易了。算法在實(shí)現(xiàn)時(shí)需要構(gòu)造三個(gè)輔助數(shù)組:第1個(gè)數(shù)組A[n](n為節(jié)點(diǎn)數(shù))記錄當(dāng)前節(jié)點(diǎn)是外圍節(jié)點(diǎn)還是已加入最短路段(路徑)網(wǎng)的節(jié)點(diǎn),數(shù)組元素A[i]=0或1,0表示節(jié)點(diǎn)i是一個(gè)外圍節(jié)點(diǎn),當(dāng)加入到最短路段(路徑)網(wǎng)后,A[i]=1;第2個(gè)數(shù)組B[n]記錄各節(jié)點(diǎn)到最短路段(路徑)網(wǎng)的距離,用B[n]表示;第3個(gè)數(shù)組C[n]記錄外圍節(jié)點(diǎn)通過(guò)最短路段(路徑)網(wǎng)內(nèi)的哪一個(gè)節(jié)點(diǎn)為“橋梁”而進(jìn)入該路段(路徑)網(wǎng)的。注意這里的路徑R和路段L是兩個(gè)不同的概念,路段是節(jié)點(diǎn)的邊,而路徑是具有共同節(jié)點(diǎn)的有序邊起節(jié)點(diǎn)與尾節(jié)點(diǎn)首尾相連在一起的序列,如在圖1中,其中的一個(gè)路徑R1-3=L1-2+L2-3。下面結(jié)合圖2和圖3,給出這些數(shù)組的值在計(jì)算過(guò)程中的變化情況。

輔助數(shù)組的變化情況如下圖3所示,其中圖3(a)即對(duì)應(yīng)于圖2(a),圖3(b)對(duì)應(yīng)于圖2(b),依此類推。在圖3(a)中,首先只有第一個(gè)節(jié)點(diǎn)進(jìn)入最短路段網(wǎng),因此A[1]=1,其它的A元素均為0,外圍節(jié)點(diǎn)與最短路段網(wǎng)的距離B[i]與圖2(a)中的距離對(duì)應(yīng),這里節(jié)點(diǎn)1由于已在最短路段網(wǎng),所以B[1]=0,由于所有的節(jié)點(diǎn)目前都是通過(guò)節(jié)點(diǎn)1與最短路段網(wǎng)連接,因而所有的C[i]的值都是1。在圖3(b)中,由于節(jié)點(diǎn)2距最短路段網(wǎng)的距離最小(16),節(jié)點(diǎn)2進(jìn)入最短路段網(wǎng),因而A[2]=1,此時(shí)由于節(jié)點(diǎn)2已進(jìn)入最短路段網(wǎng),因而B(niǎo)[2]=0,而節(jié)點(diǎn)3和節(jié)點(diǎn)4通過(guò)節(jié)點(diǎn)2,使它們距最短路段網(wǎng)的距離由原先的∞縮短到5和6,節(jié)點(diǎn)6也通過(guò)節(jié)點(diǎn)2使B[6]由21縮小到11。圖3(c)、3(d)、3(e)、3(f)的過(guò)程不再贅述。最后的結(jié)果(圖3(f))表明,節(jié)點(diǎn)1通過(guò)其本身進(jìn)入最短路段網(wǎng),節(jié)點(diǎn)2通過(guò)節(jié)點(diǎn)1進(jìn)入最短路段網(wǎng),節(jié)點(diǎn)3、4、6均通過(guò)節(jié)點(diǎn)2為“橋梁”進(jìn)入最短路段網(wǎng),而節(jié)點(diǎn)5通過(guò)節(jié)點(diǎn)4進(jìn)入最短路段網(wǎng)。

基于上述分析,不難給出以上算法的實(shí)現(xiàn)描述:

(1) 初始化數(shù)組A、B、C,結(jié)果如圖2(a)、圖3(a),這里假設(shè)以節(jié)點(diǎn)1為起始(源)節(jié)點(diǎn),共有n個(gè)節(jié)點(diǎn)。

(2) 反復(fù)執(zhí)行如下操作:將B[i]中值最小的元素對(duì)應(yīng)的編號(hào)i(即節(jié)點(diǎn)i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對(duì)應(yīng)的B[j]和C[j]的值,修改的依據(jù)是:如果B[j]>Li-j,則用B[j]的值更改為L(zhǎng)i-j。直至所有的A[i](1<=i<=n)都是1為止。

(3) 輸出結(jié)果,將B、C的最后值輸出即可以得到最后結(jié)果,B所有的元素最后都為0,表示所有的元素都進(jìn)入了最短路段網(wǎng)(最小生成數(shù)網(wǎng)),而C中的元素值表示的是當(dāng)前節(jié)點(diǎn)元素(即節(jié)點(diǎn)1、2、3、4、5或6)是通過(guò)C中表示的節(jié)點(diǎn)編號(hào)而進(jìn)入最短路段網(wǎng)的,即:節(jié)點(diǎn)1是通過(guò)其自身進(jìn)入路段網(wǎng),節(jié)點(diǎn)2通過(guò)節(jié)點(diǎn)1進(jìn)入路段網(wǎng),節(jié)點(diǎn)3、4和6均通過(guò)節(jié)點(diǎn)2進(jìn)入路段網(wǎng),節(jié)點(diǎn)5通過(guò)節(jié)點(diǎn)4進(jìn)入路段網(wǎng)。

4結(jié)論

本文提出將圖示教學(xué)法可應(yīng)用于數(shù)據(jù)結(jié)構(gòu)和算法課程教學(xué)的多個(gè)環(huán)節(jié)中,有些算法在大多數(shù)教科書中有了一定的圖示過(guò)程表示,而有些算法卻沒(méi)有給出形象的圖示表示,因而需要在教學(xué)中應(yīng)補(bǔ)充。本文以圖狀結(jié)構(gòu)中的最小生成樹(shù)算法為例,通過(guò)圖示分析,詳細(xì)地講解這個(gè)算法的核心思想和實(shí)現(xiàn)過(guò)程,通過(guò)視覺(jué)刺激,使學(xué)生能夠加深對(duì)這個(gè)算法過(guò)程的把握,取得了良好的教學(xué)效果。

參考文獻(xiàn):

[1] 戴敏,于長(zhǎng)云,董玉濤. 高效學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)[J]. 計(jì)算機(jī)教育,2006(2):59-60.

[2] 余臘生,石獻(xiàn). 基于創(chuàng)新理念的數(shù)據(jù)結(jié)構(gòu)教學(xué)方法探討[J]. 計(jì)算機(jī)與信息技術(shù),2006(11):110-114.

[3] 黃毅蓉. 關(guān)于多元復(fù)合函數(shù)偏導(dǎo)數(shù)鏈導(dǎo)法則的圖示教學(xué)探討[J]. 成都航空職業(yè)技術(shù)學(xué)院學(xué)報(bào),2001(1):31-33.

[4] 薛超英. 數(shù)據(jù)結(jié)構(gòu)[M]. 2版. 武漢:華中科技大學(xué)出版社,2002.