圖示教學法在數據結構與算法教學中的應用

沙宗堯 邊馥苓

摘要:數據結構和算法的教學是計算機科學與技術、軟件工程等相關專業最重要的教學內容之一,特別是在復雜的算法分析時,由于具有抽象性和較強的邏輯性,不采用好的教學方法,往往是事倍功半。本文提出用圖示教學法教授數據結構中的算法,并以圖狀結構中的最小生成樹算法為例,詳細介紹了該圖示方法描述數據結構算法過程,可以為數據結構的教學提供參考。

關鍵詞:數據結構;算法;圖示教學法;最小生成樹

中圖分類號:G642 文獻標識碼:B

1背景

數據結構和算法是計算機科學與技術、軟件工程等相關專業的專業基礎課,其重要性不言而喻,在教學過程中需要運用多種教學方法,讓學生領會算法實現的過程和本質,加深對所學知識的理解、記憶和應用。在數據結構和算法課程教學中,圖狀結構的教學是一個難點,特別是涉及到圖的具體應用時,更讓學生難以掌握,本文將圖示教學法應用到數據結構中關于圖狀結構的一個典型應用——最小生成樹問題,給出該教學方法的基本方法和過程,取得了良好的教學效果。

最小生成樹是圖狀(網絡)結構中一個典型的實踐應用,可以解決實際中諸如公路網的規劃,即在n個城市中,如何規劃n-1條公路,使得n個城市都可以連接起來,而所有城市間的連接線長度的總和最短(所要修建的公路長度最短,因而費用最少)。

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

2教學方法

圖示教學法就是用各種圖形表示的方法描述問題、引導學生的思考,增強對新知識的記憶,并在教學中被廣泛使用。最小生成樹屬于網絡的實踐應用,下面以圖1為例,用圖示教學法來對最小生成樹算法進行圖示過程分析。

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

如圖1,每個帶圈的數字表示一個城市,城市間的邊表示城市間的距離,如果兩城市間沒有邊存在,則表示這兩個城市間不適宜修道路(如有山脈或河流隔斷,造價太高),假設種子城市為數字1(選定的網絡的起始頂點),通過圖示教學法求最優路段網的過程如圖2:

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

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

注意到為了使規劃的路段網是最優的(路段長度總和最小),只要保證每次加入到最優路段網中的城市都具有最短路段長度,則最后的路段總長度也必然最小。在圖2(a)中,城市2與種子城市具有最小的距離(16),因而不可能找到其它任何一個路段,實現“種子城市與其它外圍城市實現互連時,種子城市到其它任意一個城市的路段距離小于該值”,因而路段②-①必然是滿足種子城市連通其它城市的最優路段,將城市2加入到最優路段網后,得到圖2(b)。注意到當城市2加入到最優路段網后,城市3、4、6如果是通過城市2為“橋梁”(圖中的虛線所示),加入到該最優路段網中,可以使各自的路段長度由原先的∞、∞和21分別縮短到5、6、11(其它城市通過城市2無法實現路段長度縮短,因為保持不變),此時路段總長度也由原先的∞縮小到57(即16+5+6+19+11),較圖2(a),該方案有了很大的進步。然而該網絡仍不是最優路段網,因為其僅保證了路段②-①的最優性(注意圓圈內的網絡是最優的),而其它城市到該網絡中的路段并非最優,這樣不能保證路段總長度最小。

進一步注意到,在所有的當前外圍城市中,城市3距離最優路段網的距離最短(5),也就是為了使當前最優路段網(圓圈內的城市及連線)與其它外圍城市能夠實現連通,且連通后的路段總長度最小,所以當前應加入城市3(圖2(c))。城市3的加入或許可以使得其它的外圍城市通過該城市為“橋梁”,而縮短外圍城市到最優路段網的距離(當然這里城市3的加入實際并沒有使其它城市到最優路段網的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優路段網中(因為在余下的外圍城市中,城市4到最優路段網的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優路段網的距離由原來的19縮短到18(其它路段不變)。第5步將城市6加入到最優路段網中(圖2(e)),該城市的加入沒有影響余下的城市(當前僅剩一個城市,即城市5),最后將城市5加入到最優路段網中(圖2(f))。得到的最終的最優路段網如圖2(h),其路段長度的總和為56(16+5+11+6+18)。

3算法求解

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

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

基于上述分析,不難給出以上算法的實現描述:

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

(2) 反復執行如下操作:將B[i]中值最小的元素對應的編號i(即節點i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對應的B[j]和C[j]的值,修改的依據是:如果B[j]>Li-j,則用B[j]的值更改為Li-j。直至所有的A[i](1<=i<=n)都是1為止。

(3) 輸出結果,將B、C的最后值輸出即可以得到最后結果,B所有的元素最后都為0,表示所有的元素都進入了最短路段網(最小生成數網),而C中的元素值表示的是當前節點元素(即節點1、2、3、4、5或6)是通過C中表示的節點編號而進入最短路段網的,即:節點1是通過其自身進入路段網,節點2通過節點1進入路段網,節點3、4和6均通過節點2進入路段網,節點5通過節點4進入路段網。

4結論

本文提出將圖示教學法可應用于數據結構和算法課程教學的多個環節中,有些算法在大多數教科書中有了一定的圖示過程表示,而有些算法卻沒有給出形象的圖示表示,因而需要在教學中應補充。本文以圖狀結構中的最小生成樹算法為例,通過圖示分析,詳細地講解這個算法的核心思想和實現過程,通過視覺刺激,使學生能夠加深對這個算法過程的把握,取得了良好的教學效果。

參考文獻:

[1] 戴敏,于長云,董玉濤. 高效學習數據結構[J]. 計算機教育,2006(2):59-60.

[2] 余臘生,石獻. 基于創新理念的數據結構教學方法探討[J]. 計算機與信息技術,2006(11):110-114.

[3] 黃毅蓉. 關于多元復合函數偏導數鏈導法則的圖示教學探討[J]. 成都航空職業技術學院學報,2001(1):31-33.

[4] 薛超英. 數據結構[M]. 2版. 武漢:華中科技大學出版社,2002.