發(fā)布時(shí)間：2023-03-07 15:05:58
序言：寫作是分享個(gè)人見(jiàn)解和探索未知領(lǐng)域的橋梁，我們?yōu)槟x了8篇的數(shù)據(jù)結(jié)構(gòu)與算法樣本，期待這些樣本能夠?yàn)槟峁┴S富的參考和啟發(fā)，請(qǐng)盡情閱讀。
>> 數(shù)據(jù)結(jié)構(gòu)排序算法可視化的設(shè)計(jì) 選擇排序算法的分析與改進(jìn) 《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)改進(jìn)與探索 論數(shù)據(jù)結(jié)構(gòu)中的外排序與內(nèi)排序 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)中排序算法的動(dòng)態(tài)演示 基于VC++的數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng) 基于數(shù)據(jù)結(jié)構(gòu)的最小生成樹(shù)算法 基于項(xiàng)目導(dǎo)向的數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)研究與實(shí)踐 基于C語(yǔ)言排序的算法改進(jìn)與應(yīng)用 基于C程序冒泡排序算法的研究與改進(jìn) 試論算法與數(shù)據(jù)結(jié)構(gòu)的相關(guān)性 《數(shù)據(jù)結(jié)構(gòu)與算法》的教改問(wèn)題研究 “算法與數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)體系的建設(shè) 數(shù)據(jù)結(jié)構(gòu)中排序方法的研究 數(shù)據(jù)結(jié)構(gòu)算法應(yīng)用 基于Visual C++的數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法的演示系統(tǒng) 基于K―D樹(shù)數(shù)據(jù)結(jié)構(gòu)的平面插值算法的優(yōu)化 “算法與數(shù)據(jù)結(jié)構(gòu)”教學(xué)探索與實(shí)踐 通用題庫(kù)數(shù)據(jù)結(jié)構(gòu)與組卷算法設(shè)計(jì) 算法與數(shù)據(jù)結(jié)構(gòu)理論教學(xué)技巧探討 常見(jiàn)問(wèn)題解答 當(dāng)前所在位置：l.
[4]黃福員.冒泡排序算法的改進(jìn)[J].微機(jī)發(fā)展,2003,13(11):65-66.
[5] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述[M].張懷勇,譯.北京:人民郵電出版社,2007.
[6]Thomas H Cormen.算法導(dǎo)論[M].2版.北京:機(jī)械工業(yè)出版社,2006.
[7]Sartaj Sahni.計(jì)算機(jī)算法[M].北京:機(jī)械工業(yè)出版社,2006.
[8]徐士良.實(shí)用數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2006.
關(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[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
(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.
全書共20章。1.Python編程101：對(duì)使用Python語(yǔ)言編程進(jìn)行總體介紹，包括創(chuàng)建對(duì)象、對(duì)象調(diào)用方法、運(yùn)算符重載、讀取文件方法、XML文件等內(nèi)容；2.計(jì)算復(fù)雜度：包括計(jì)算機(jī)體系結(jié)構(gòu)介紹、常見(jiàn)的計(jì)算復(fù)雜性、攤銷復(fù)雜度的方法等；3.遞歸：包括時(shí)棧和堆的概念、簡(jiǎn)單遞歸函數(shù)的編寫、運(yùn)行，遞歸計(jì)算機(jī)圖形學(xué)、列表與字符串等；4.排序：包括選擇排序、歸并排序、快速排序、鏈表、棧和隊(duì)列等內(nèi)容；5.集合與映射：數(shù)獨(dú)游戲介紹、集、散列等相關(guān)概念，最后分析規(guī)劃問(wèn)題；6.樹(shù)：抽象語(yǔ)法樹(shù)和表達(dá)、前綴和后綴表達(dá)式、解析前綴表達(dá)式、二叉搜索樹(shù)等內(nèi)容；7.圖：包括圖的定義及理論、存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)、Kruskal算法、Dijkstra算法、圖的表示方法等；8.Bloom過(guò)濾器、Trie數(shù)據(jù)類型等相關(guān)內(nèi)容；9.堆：包括堆的主要思想及其建立、排序算法、與其他算法的比較等；10.平衡二叉搜索樹(shù)：二叉搜索樹(shù)的概念、存儲(chǔ)結(jié)構(gòu)與性質(zhì)、AVL樹(shù)與 Splay樹(shù)等具體實(shí)例；11.B樹(shù)：包括關(guān)系型數(shù)據(jù)庫(kù)的概念、B樹(shù)的組織結(jié)構(gòu)、優(yōu)勢(shì)、實(shí)現(xiàn)、B樹(shù)的插入與刪除等內(nèi)容；12.啟發(fā)式搜索：包括深度優(yōu)先搜索與廣度優(yōu)先搜索、A*搜索、最佳搜索等相關(guān)內(nèi)容；13.附錄A：整數(shù)操作符；14.附錄B：浮算子；15.附錄C：字符串運(yùn)算符和方法；16.附錄D：列表操作符和方法；17.附錄E：字典操作和方法；18.附錄F：Turtle方法；19附錄G：TurtleScreen方法；20.附錄H：完整的程序。
作者Kent D.Lee博士是美國(guó)艾奧瓦洲路德學(xué)院計(jì)算機(jī)科學(xué)教授，已成功出版兩本著作：Python編程基礎(chǔ)和編程語(yǔ)言基礎(chǔ)。另一作者Steve Hubbard博士是路德學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系教授。
本書介紹了初級(jí)與高級(jí)的數(shù)據(jù)結(jié)構(gòu)和算法問(wèn)題，每一章開(kāi)始提供了學(xué)習(xí)目標(biāo)，復(fù)習(xí)題和編程練習(xí)，以及眾多的例證；同時(shí)在相關(guān)的網(wǎng)站提供可下載的程序和補(bǔ)充文件。本書可以作為計(jì)算機(jī)學(xué)科相關(guān)專業(yè)的教材或參考書，同時(shí)對(duì)計(jì)算機(jī)科技工作者也有參考價(jià)值。
關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；多線程；VC++；動(dòng)態(tài)演示
中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)31-7685-03
Demonstrate System Based on VC++ for Data Structure Algorithm
SHEN Li-min
(Computing Center of the PLA University of Foreign Languages, Luoyang 471003, China)
Abstract: In view of the characteristic of data structure, on the analysis of insufficiency and limitation for traditional teaching method. How to illustrate algorithm performing process to the studuentsin a simple way becomes vital to the teaching of this course. Based on the reansons above, a teaching platform demonstrating the processing of algorithm has been designed and presented in this paper. This algorithm demo system to display a variety of programming languages to achieve a variety of algorithms and dynamic process, has the image of the interface, clear display of the various algorithms realize the process. The system is friendly, easy to use, it serves to the study of the student as well as the teacher's teaching.
Key words: data structure; multhread; VC++; dynamic demonstrate
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程，對(duì)各類算法的理解是課程教學(xué)的重點(diǎn)和難點(diǎn)，算法動(dòng)態(tài)演示系統(tǒng)作為輔助教學(xué)過(guò)程的手段可以有效幫助學(xué)生更快的理解、掌握算法。在教學(xué)過(guò)程中能加以計(jì)算機(jī)輔助教學(xué)，不僅可以提高教學(xué)效果，而且能夠激發(fā)學(xué)生濃厚的學(xué)習(xí)興趣并加強(qiáng)其編程能力，本系統(tǒng)采用多線程技術(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)算法的算法動(dòng)態(tài)演示設(shè)計(jì)，實(shí)現(xiàn)了源代碼跟蹤、變量跟蹤、模擬動(dòng)態(tài)效果的算法演示系統(tǒng)。
1 數(shù)據(jù)結(jié)構(gòu)定義
1.1 抽象數(shù)據(jù)類型迷宮
為了便于介紹，本文以迷宮求解為例。
ADT Seek{
數(shù)據(jù)對(duì)象：
D={ai,j|0
數(shù)據(jù)關(guān)系：R={ROW,COL}
基本操作：
InitSeek(&M,a,row,col)
初始條件：二維數(shù)組a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。
操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，以字符‘磚墻’表示障礙，并在迷宮四周加上一圈障礙。
Seek(int k，int x，int y，BOOL &succ)
初始條件：布爾型變量succ為fause。
操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài)：根據(jù)布爾變量succ的值來(lái)判斷有無(wú)路徑可走。
PrintSeek（M）
初始條件：迷宮M已存在。
操作結(jié)果：以字符形式輸出迷宮。
} ADT Seek[1]；
1.2 整體框架
本程序包含三個(gè)模塊
1）棧模塊――實(shí)現(xiàn)棧抽象數(shù)據(jù)類型
2）迷宮模塊――實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型
3）主程序模塊：
void mian()
{ 初始化；
Do{
接受命令；
處理命令；
}while(命令!=“退出”)；
}
2 動(dòng)態(tài)系統(tǒng)的設(shè)計(jì)
2.1 多線程技術(shù)
系統(tǒng)的核心部分是動(dòng)畫演示、變量跟蹤和源代碼同步的實(shí)現(xiàn)，對(duì)于每一個(gè)算法的演示都要求實(shí)現(xiàn)這部分，數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示的關(guān)鍵技術(shù)多線程技術(shù)
多線程(Muhithread)是指程序含有多個(gè)執(zhí)行流。多線程機(jī)制允許單個(gè)程序通過(guò)建立多個(gè)并行執(zhí)行的線程來(lái)完成各自的任務(wù)。這些并行執(zhí)行的線程可以執(zhí)行相同的代碼，也可以執(zhí)行不同的代碼[2]。
在dotNET類庫(kù)中，System.Threading命名空間下包含了各種線程組件、接口來(lái)幫助程序員使用C#編寫多線程程序。在這個(gè)命名空間中最重要的就是Thread類，它是C#多線程程序設(shè)計(jì)的基礎(chǔ)。Thread類提供了創(chuàng)建線程、控制線程的方法，它主要有以下幾種重要的成員[3,6]：
啟動(dòng)線程：Start()
終止線程：Abort()
線程休眠：Sleep()
掛起線程：Suspend()
恢復(fù)線程：Resume()
2.2 具體的線程設(shè)計(jì)
AlgorithmThread．//用戶自定義線程
{//類成員變量聲明處
public AlgorithmThread()
{//構(gòu)造函數(shù)體
} //類AlgorithmThread的構(gòu)造函數(shù)
public void Run(){//定義線程體，以實(shí)現(xiàn)自定義線程類AlgorithmThread的功能
int i;String str;
for(i=0;i
{
str="Stepumber"+i.ToString()+"executed";
Thread.Sleep(500);
}
}
}
主程序中建立和啟動(dòng)線程：
public class mainForm
{ public delegate
void DelegateStep(int s);
public void startAlgorithmThread()
{ m_algotithmThread=new
Thread(newThreadStart(this.ThreadFunction));
//創(chuàng)建線程實(shí)例
m_algotithmThread.Start();//啟動(dòng)線程，即調(diào)用ThreadFunction線程函數(shù)
}
private void ThreadFunction()
{ /線程函數(shù)
AlgorithmThread algorithmThread;
algorithmThread=new AlgorithmThread();
algorithmThread.run();//調(diào)用AlgorithmThread的run函數(shù)，執(zhí)行線程體
}}
2.3 實(shí)現(xiàn)思路
數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)采用Windows應(yīng)用程序項(xiàng)目來(lái)創(chuàng)建，在算法演示系統(tǒng)的主頁(yè)上有啟動(dòng)各個(gè)算法的按鈕，通過(guò)這些按鈕啟動(dòng)每個(gè)算法演示界面，該界面有幾個(gè)主要區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)組件[4-5]。
主窗口：包括標(biāo)題欄和工具欄，用來(lái)實(shí)現(xiàn)系統(tǒng)控制。
動(dòng)畫演示區(qū)：以圖形和動(dòng)畫的方式模擬和顯示算法執(zhí)行的過(guò)程和結(jié)果。
源代碼區(qū)：用來(lái)顯示類C語(yǔ)言編寫的算法描述，為了更清楚地描繪算法的執(zhí)行過(guò)程，當(dāng)程序運(yùn)行到當(dāng)前行時(shí)，用一條高亮度光帶罩住此語(yǔ)句，表示該語(yǔ)句被執(zhí)行。
變量當(dāng)前值顯示區(qū)：由控件ListView實(shí)現(xiàn)，負(fù)責(zé)當(dāng)前演示算法的重要參數(shù)及變化值的顯示。
3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析
實(shí)驗(yàn)分別從算法進(jìn)行動(dòng)態(tài)模擬、代碼同步跟蹤來(lái)形象直觀地反映算法的設(shè)計(jì)思想與動(dòng)態(tài)過(guò)程，圖1是迷宮求解算法求解過(guò)程。
3.1 算法動(dòng)態(tài)模擬
本文利用多線程技術(shù)實(shí)現(xiàn)算法動(dòng)態(tài)模擬演示，對(duì)一個(gè)具體的算法演示子模塊，須滿足執(zhí)行、暫停、速度可調(diào)、任意時(shí)刻復(fù)位并能重新執(zhí)行等復(fù)雜切換控制功能，從圖1可以看到，菜單區(qū)有自動(dòng)執(zhí)行、單步執(zhí)行、擇暫停所得到的效果，從圖1的動(dòng)畫顯示區(qū)和變量區(qū)看到算法執(zhí)行的過(guò)程。如圖2中（a）是迷宮這種數(shù)據(jù)結(jié)構(gòu)的初始化，（b）是隨機(jī)生成的迷宮。
3.2 代碼同步跟蹤
本文AlgorithmThread線程負(fù)責(zé)執(zhí)行迷宮求解算法，而在主窗口中需要同步顯示被執(zhí)行到的源代碼行和該行代碼中涉及到變量的當(dāng)前值的獲取和顯示，這涉及到多線程間的同步和交互的問(wèn)題。如圖3所示藍(lán)色的橫條表示算法執(zhí)行到到位置，結(jié)合圖1和圖3可以清楚看到代碼的同步跟蹤情況。
4 結(jié)論
本文是基于VC實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)，采用了多線程技術(shù)，對(duì)算法進(jìn)行動(dòng)態(tài)模擬、代碼同步跟蹤，可以形象直觀地反映算法的設(shè)計(jì)思想與動(dòng)態(tài)過(guò)程，便于加深學(xué)習(xí)者對(duì)算法的理解和掌握。
參考文獻(xiàn)：
[1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2008.
[2] Nagel C,Evjen B,Glynn J,et al.C#高級(jí)編程[M].李敏波,譯.4版.北京:清華大學(xué)出版社,2006.
[3] Schneider G,Winters J P.用例分析技術(shù)[M].姚淑珍,李巍,譯.北京:機(jī)械工業(yè)出版社,2002.
[4] 劉懷亮,陳榮國(guó),呂國(guó)華.軟件組建技術(shù)[M].北京:冶金工業(yè)出版社,2007.
關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 教學(xué)模式 層次化教學(xué)
中圖分類號(hào)：G424 文獻(xiàn)標(biāo)識(shí)碼：A
1 數(shù)據(jù)結(jié)構(gòu)在本科生教學(xué)中的地位
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科本科教學(xué)中的核心課程，課程知識(shí)豐富，內(nèi)容抽象，實(shí)踐性強(qiáng)，主要研究各種基本的數(shù)據(jù)結(jié)構(gòu)在存儲(chǔ)器中的映像和各種基本操作在相應(yīng)的存儲(chǔ)映像上的實(shí)現(xiàn)。學(xué)習(xí)本課程旨在使學(xué)生增強(qiáng)分析計(jì)算機(jī)所加工數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)特性，選擇合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法的能力，并初步掌握算法的時(shí)間效率分析和空間效率分析的技術(shù)，編寫出高效的程序。①
數(shù)據(jù)結(jié)構(gòu)作為實(shí)踐性很強(qiáng)的計(jì)算機(jī)專業(yè)基礎(chǔ)課，在計(jì)算機(jī)科學(xué)教育中有著重要的地位和作用。美國(guó)IEEE和ACM的教學(xué)計(jì)劃均把算法與數(shù)據(jù)結(jié)構(gòu)類課程列為計(jì)算機(jī)以及信息技術(shù)相關(guān)學(xué)科專業(yè)的本科必修基礎(chǔ)課程。②
2 數(shù)據(jù)結(jié)構(gòu)教學(xué)體系的實(shí)施和效果
數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容比較抽象，教學(xué)中長(zhǎng)期存在一部分老師重理論輕實(shí)踐的現(xiàn)象，即使老師花費(fèi)很多時(shí)間備課和授課，卻經(jīng)常出現(xiàn)學(xué)生只能大致明白算法思想，而無(wú)法真正實(shí)現(xiàn)算法的情況，學(xué)生逐漸對(duì)這門課程的學(xué)習(xí)失去了興趣和信心。
由于我院的授課對(duì)象是三本學(xué)生，如果只是枯燥地介紹各種數(shù)據(jù)結(jié)構(gòu)以及算法實(shí)現(xiàn)，學(xué)生很難理解并掌握相應(yīng)知識(shí)點(diǎn)，最終只能勉強(qiáng)應(yīng)付考試，而失去了學(xué)習(xí)該門課程的真正意義。為了實(shí)現(xiàn)課程的教學(xué)目標(biāo)，使學(xué)生不但掌握數(shù)據(jù)結(jié)構(gòu)的基本理論知識(shí)點(diǎn)，更要掌握各種經(jīng)典算法，學(xué)會(huì)分析實(shí)際執(zhí)行的算法，培養(yǎng)學(xué)生創(chuàng)造性地應(yīng)用各種數(shù)據(jù)結(jié)構(gòu)和算法，解決實(shí)際的應(yīng)用問(wèn)題的能力，以及探索和創(chuàng)新能力。針對(duì)我院學(xué)生的特點(diǎn)，在教學(xué)中采取層次化教學(xué)，既要培養(yǎng)多數(shù)應(yīng)用型人才的實(shí)踐能力，又要培養(yǎng)少數(shù)研究型人才的科研能力。
2.1 強(qiáng)化實(shí)踐，注重培養(yǎng)能力
數(shù)據(jù)結(jié)構(gòu)是一門理論性和實(shí)踐性都很強(qiáng)的課程，培養(yǎng)學(xué)生的實(shí)踐能力是教學(xué)的首要目的，理論知識(shí)的傳授是為提高實(shí)踐能力的，因此必須通過(guò)上機(jī)實(shí)驗(yàn)來(lái)加強(qiáng)實(shí)踐能力。由于學(xué)生的學(xué)習(xí)主動(dòng)性和學(xué)習(xí)能力各不相同，為了達(dá)到因材施教的目的，每個(gè)上機(jī)題目既要考慮學(xué)生總體的動(dòng)手編程能力，又要考慮學(xué)生的個(gè)體差異，上機(jī)內(nèi)容采取層次化思想。上機(jī)題目中包括了基礎(chǔ)性、設(shè)計(jì)性和綜合性實(shí)驗(yàn)，各種類型的上機(jī)題目之間存在著承接關(guān)系。經(jīng)實(shí)踐證明，采用由淺入深的上機(jī)實(shí)踐環(huán)節(jié)，既有全體學(xué)生都能順利完成的基礎(chǔ)驗(yàn)證性題目，可以鞏固并深化理論內(nèi)容，實(shí)現(xiàn)教學(xué)要結(jié)合實(shí)際應(yīng)用的特點(diǎn)，又考慮到學(xué)生專業(yè)特點(diǎn)和個(gè)性的設(shè)計(jì)綜合題，培養(yǎng)了學(xué)生獨(dú)立運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，最大程度挖掘自身潛能。
2.2 注重引導(dǎo)學(xué)生思考，采用多樣化的理論教學(xué)
課堂教學(xué)應(yīng)把學(xué)生放在一種根本的、重要的位置上，從根本上確立以學(xué)生為主體的地位，把學(xué)生看成是積極的、富有創(chuàng)造性的程序語(yǔ)言使用者，而不是被動(dòng)的接受者。為了避免傳統(tǒng)的學(xué)生被動(dòng)地接受書本知識(shí)的教學(xué)模式，在數(shù)據(jù)結(jié)構(gòu)的教學(xué)中，采用“問(wèn)題”組織教學(xué)，包括問(wèn)題設(shè)置、學(xué)生通過(guò)思考和討論提出解決方案、教師對(duì)學(xué)生的解決方案的評(píng)價(jià)并給出最佳解決方案。這樣可以把課程的知識(shí)點(diǎn)轉(zhuǎn)化為對(duì)某個(gè)問(wèn)題的求解過(guò)程，使學(xué)生通過(guò)解決問(wèn)題掌握知識(shí)。強(qiáng)調(diào)學(xué)生在學(xué)習(xí)和發(fā)展中的主體性和潛力的發(fā)揮，同時(shí)又不忽視教師的主導(dǎo)作用，通常采用小組協(xié)作式、個(gè)別化等教學(xué)形式或采用多種教學(xué)形式組合起來(lái)進(jìn)行教學(xué)。數(shù)據(jù)結(jié)構(gòu)教學(xué)的過(guò)程，實(shí)際上就是師生互相協(xié)作的一個(gè)過(guò)程。在課堂教學(xué)中充分發(fā)揮學(xué)生的主體性，讓學(xué)生主動(dòng)積極地去學(xué)習(xí)。
在教學(xué)方式中，如果只通過(guò)傳統(tǒng)的黑板加粉筆的教學(xué)模式讓學(xué)生通過(guò)腦海中執(zhí)行靜態(tài)的程序代碼來(lái)了解數(shù)據(jù)結(jié)構(gòu)的動(dòng)態(tài)變化，這種方式缺乏直觀性效果，難以充分展示算法的動(dòng)態(tài)變化過(guò)程，學(xué)生難以想象數(shù)據(jù)之間的復(fù)雜關(guān)系。因此要充分利用多媒體教學(xué)課件動(dòng)態(tài)地演示各種數(shù)據(jù)結(jié)構(gòu)和算法，把知識(shí)生動(dòng)、形象、動(dòng)態(tài)地呈現(xiàn)給學(xué)生。
2.3 加強(qiáng)前導(dǎo)課程復(fù)習(xí)
學(xué)習(xí)本課程前學(xué)生雖已學(xué)過(guò)C語(yǔ)言程序設(shè)計(jì)與離散數(shù)學(xué)，但僅僅是初步掌握，并不精通，不能熟練運(yùn)用程序設(shè)計(jì)語(yǔ)言進(jìn)行編程。很難將算法轉(zhuǎn)化成程序設(shè)計(jì)語(yǔ)言中的函數(shù)并編寫出調(diào)用該函數(shù)的主函數(shù)，有的同學(xué)甚至直接將算法放到機(jī)器上運(yùn)行，這是擺在學(xué)生面前的難題。針對(duì)以上情況，在開(kāi)始講授數(shù)據(jù)結(jié)構(gòu)前，都會(huì)將之前學(xué)習(xí)的C語(yǔ)言程序設(shè)計(jì)中的數(shù)組、指針、函數(shù)、結(jié)構(gòu)體和離散數(shù)學(xué)中的樹(shù)和圖相關(guān)知識(shí)進(jìn)行復(fù)習(xí)，然后再開(kāi)始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。對(duì)于課程中的算法，除了講解之外，部分算法在課上都會(huì)寫出完整的源程序并運(yùn)行，使學(xué)生理解算法和源程序之間的關(guān)系。
2.4 激勵(lì)個(gè)性化學(xué)習(xí)，改革考核方式
在教學(xué)內(nèi)容和實(shí)施上，適當(dāng)考慮多樣性和靈活性，對(duì)于應(yīng)用型人才著重培養(yǎng)學(xué)生通過(guò)典型數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)的學(xué)習(xí)和訓(xùn)練，逐步掌握根據(jù)實(shí)際問(wèn)題分析數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的運(yùn)算和處理算法。對(duì)于研究型人才著重培養(yǎng)學(xué)生建立數(shù)據(jù)結(jié)構(gòu)與算法的思維方法，形成數(shù)據(jù)結(jié)構(gòu)和問(wèn)題求解的知識(shí)體系，理解抽象的概念和復(fù)雜算法。對(duì)于能力較強(qiáng)的同學(xué)，可以選擇一些數(shù)據(jù)結(jié)構(gòu)應(yīng)用等高級(jí)主題予以介紹，例如紅黑樹(shù)、伸展樹(shù)、后綴樹(shù)等復(fù)雜結(jié)構(gòu)。學(xué)生在將來(lái)的科學(xué)研究和工程項(xiàng)目實(shí)踐中將廣泛接觸到這些實(shí)用的數(shù)據(jù)結(jié)構(gòu)和算法技術(shù)。
為了體現(xiàn)上機(jī)實(shí)踐對(duì)該課程的重要性，我們?cè)跀?shù)據(jù)結(jié)構(gòu)課程考核中采取重視上機(jī)實(shí)踐成績(jī)的考核方式，即平時(shí)成績(jī)30%（其中上機(jī)占20%）+期末考試成績(jī)70%的形式對(duì)學(xué)生學(xué)習(xí)成績(jī)予以評(píng)價(jià)。
3 結(jié)語(yǔ)
以“學(xué)”為中心的教學(xué)設(shè)計(jì)，設(shè)計(jì)起來(lái)容易，因?yàn)槟侵皇亲鲆恍Q策。難在具體地教學(xué)實(shí)施。只有在教學(xué)實(shí)施過(guò)程中才會(huì)檢驗(yàn)出教師是否真的堅(jiān)持以“學(xué)”為中心的教學(xué)。教學(xué)過(guò)程中，以學(xué)生為主體，教師為主導(dǎo)，讓學(xué)生體會(huì)到數(shù)據(jù)結(jié)構(gòu)是一門與實(shí)踐緊密聯(lián)系且非常有趣的課程。通過(guò)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)提高了學(xué)生的邏輯思維能力和數(shù)據(jù)抽象能力，提高了設(shè)計(jì)高質(zhì)量程序的能力，為學(xué)生奠定了扎實(shí)的軟件開(kāi)發(fā)基礎(chǔ)。
注釋
關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；可視化；設(shè)計(jì)
在我國(guó)的科學(xué)技術(shù)得到迅速發(fā)展的過(guò)程中，科學(xué)計(jì)算的工作量也開(kāi)始變得愈來(lái)愈大，可視化的方法能夠有效的幫助工作人員進(jìn)行獲取更多的信息，從而更為直觀的來(lái)對(duì)計(jì)算的結(jié)果進(jìn)行分析。由于受到計(jì)算機(jī)性能以及軟件平臺(tái)限制，在最初的可視化軟件系統(tǒng)方面都是在高性能圖形工作站進(jìn)行發(fā)展的，對(duì)數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)的設(shè)計(jì)能夠有效的將效率得到提高。
一、數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)設(shè)計(jì)的重要性及目的
（一）數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)設(shè)計(jì)的重要性
在使用以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)過(guò)程中，實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的可視化能夠有效的提高對(duì)數(shù)據(jù)結(jié)構(gòu)的直觀分析，從而加深理解。在對(duì)程序進(jìn)行調(diào)試的過(guò)程中，通過(guò)數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)能夠有效的將編程的效率得以提高。從目前的發(fā)展情況來(lái)看，已經(jīng)有了諸多的應(yīng)用廣泛的可視化集成開(kāi)發(fā)環(huán)境，其中最為常見(jiàn)的就是Visual C++等，這些可視化的集成開(kāi)發(fā)環(huán)境簡(jiǎn)化了程序界面的設(shè)計(jì)，對(duì)編寫界面的程序降低了難度，從而有效的提高了軟件的開(kāi)發(fā)效率。
（二）數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)設(shè)計(jì)的目的
在數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)設(shè)計(jì)的目的上就是使得JVDSCL能夠比較容易的在不同用途中進(jìn)行應(yīng)用，這就是要加強(qiáng)其靈活性，JVDSCL能夠直接的應(yīng)用到軟件應(yīng)用程序的開(kāi)發(fā)方面，在開(kāi)發(fā)人員方面也能夠通過(guò)JVDSCL來(lái)進(jìn)行對(duì)新的數(shù)據(jù)結(jié)構(gòu)進(jìn)行構(gòu)造，另外就是加強(qiáng)其可靠性的目的，在這一方面是JVDSCL的最為主要的目的，還有就是面向?qū)ο蟮哪康?，?shù)據(jù)結(jié)構(gòu)是JVDSCL的主要對(duì)象，同時(shí)算法也是對(duì)象，它們保存運(yùn)行的結(jié)果以及提供訪問(wèn)結(jié)果的接口。
二、數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)的設(shè)計(jì)和實(shí)現(xiàn)探究
（一）數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)的設(shè)計(jì)探究。在對(duì)數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)進(jìn)行設(shè)計(jì)的過(guò)程中，要對(duì)問(wèn)題進(jìn)行綜合性的考慮，其中在JVDSCL方面它主要是在Java集合庫(kù)基礎(chǔ)上來(lái)進(jìn)行對(duì)原有的數(shù)據(jù)結(jié)構(gòu)類中進(jìn)行的擴(kuò)展，與此同時(shí)也在這一過(guò)程中添加了相應(yīng)的較為復(fù)雜化的數(shù)據(jù)結(jié)構(gòu)，最為常見(jiàn)的就是樹(shù)圖。在JVDSCL過(guò)程中對(duì)可視化數(shù)據(jù)結(jié)構(gòu)進(jìn)行構(gòu)造來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的可視化，而這一可視化的數(shù)據(jù)結(jié)構(gòu)也是在Java集合庫(kù)當(dāng)中的原有數(shù)據(jù)結(jié)構(gòu)類的操作基礎(chǔ)上進(jìn)行的，另外就是增添了一些可視屬性以及對(duì)可視化的接口進(jìn)行了提供。在每種數(shù)據(jù)結(jié)構(gòu)都會(huì)有著多種顯示的模式，這就需要開(kāi)發(fā)人員進(jìn)行有機(jī)的選擇，而在JVDSCL當(dāng)中，對(duì)于每種數(shù)據(jù)結(jié)構(gòu)會(huì)有這多種布局的方法來(lái)對(duì)其加以布局。
在對(duì)數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)進(jìn)行設(shè)計(jì)的內(nèi)容上主要就是基本的可視化接口的設(shè)計(jì)以及顯示模式和布局方法。其中在可視化接口的設(shè)計(jì)方面，最為主要的接口就是V Collection接口，它不僅是能夠提供Collection接口的基本方法，同時(shí)也提供可視化接口，在這一內(nèi)容上主要有 void draw，操作上就是重畫指定的數(shù)據(jù)結(jié)構(gòu)，通過(guò)display Mode參數(shù)值來(lái)決定選用的顯示模式，在這一接口中的參數(shù)c是表示數(shù)據(jù)結(jié)構(gòu)所顯示的顏色。在顯示模式的設(shè)計(jì)當(dāng)中，JVDSCL的每種數(shù)據(jù)結(jié)構(gòu)都會(huì)有不相同的顯示模式，如下圖所表示的兩種模式。
另外，在布局的設(shè)計(jì)上，關(guān)于數(shù)據(jù)結(jié)構(gòu)可視化的關(guān)鍵問(wèn)題就是圖形的布局問(wèn)題，這對(duì)于相關(guān)的研究人員對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的效果理解有著非常密切的關(guān)系。而在JVDSCL當(dāng)中的最為主要的就是線性布局的方法以及圖布局的方法，針對(duì)于每種不同的布局在算法的實(shí)現(xiàn)上也是不同的。其中在線性的布局方面，主要是能夠適用于隊(duì)列和線性表的數(shù)據(jù)結(jié)構(gòu)，在對(duì)線性的布局方法上其基本的算法框架就是獲取數(shù)據(jù)的元素個(gè)數(shù)以及依靠著所顯示大小和數(shù)據(jù)元素個(gè)數(shù)進(jìn)行對(duì)布局的大小值進(jìn)行計(jì)算。如下圖所示。
在圖布局的設(shè)計(jì)方面在算法上是屬于二維彈性模型的算法，最為基本的思想就是在二維平面上進(jìn)行計(jì)算。這一方法比較的適合圖等數(shù)據(jù)結(jié)構(gòu)，在JVDSCL當(dāng)中能夠提供的多種算法實(shí)現(xiàn)圖的可視化，其中有基于遺傳模擬退火算法圖的三維可視化以及以上所說(shuō)的二維彈性模擬算法等?？梢暬夹g(shù)的主要目的就是來(lái)輔助人們?cè)鰪?qiáng)認(rèn)知上的能力，而在計(jì)算機(jī)的可視化技術(shù)方面能夠?qū)⑵渥鳛槭切畔⒌奶幚砉ぞ?，以此?lái)考慮多樣化的樣本以及變量和聯(lián)系。
（二）數(shù)據(jù)結(jié)構(gòu)可視化類庫(kù)的實(shí)現(xiàn)分析。在數(shù)據(jù)結(jié)構(gòu)的可視化類庫(kù)的實(shí)現(xiàn)方面由于本論文的篇幅有限簡(jiǎn)要進(jìn)行講述，數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)演示系統(tǒng)演示了各種不同算法的數(shù)據(jù)結(jié)構(gòu)變化的過(guò)程，這還需要相關(guān)的設(shè)計(jì)人員在大量的畫圖操作上得以實(shí)現(xiàn)，比如對(duì)鏈表的結(jié)點(diǎn)的繪制，對(duì)于JVDSCL的應(yīng)用就不需要自己來(lái)編碼就能夠?qū)崿F(xiàn)畫圖的操作，在動(dòng)態(tài)演示系統(tǒng)方面有了很大程度上的層次性提高，在這一過(guò)程中設(shè)計(jì)人員不需對(duì)數(shù)據(jù)結(jié)構(gòu)的布局進(jìn)行考慮，在JVDSCL自身已經(jīng)有了布局的功能，只需要根據(jù)自身的的需要來(lái)進(jìn)行重寫即可實(shí)現(xiàn)。另外，在對(duì)數(shù)據(jù)結(jié)構(gòu)中的draw（）進(jìn)行調(diào)用也能夠有效的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的可視化。
三、結(jié)語(yǔ)
總而言之，對(duì)于數(shù)據(jù)結(jié)構(gòu)的可視化類庫(kù)的設(shè)計(jì)以及實(shí)現(xiàn)能夠有效的將軟件的重用性和擴(kuò)展性得到提高，在JVDSCL的基礎(chǔ)上進(jìn)行對(duì)其加以設(shè)計(jì)，對(duì)軟件的開(kāi)發(fā)設(shè)計(jì)的效率有了明顯的提高，在未來(lái)我國(guó)的軟件技術(shù)設(shè)計(jì)水平不斷提升的過(guò)程中，也定能夠在這一領(lǐng)域取得更加優(yōu)異的設(shè)計(jì)成果。
參考文獻(xiàn)：
[1]楊曉波，陳邦澤.數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐教學(xué)體系研究[J].實(shí)驗(yàn)技術(shù)與管理，2013，（08）.
[2]馮月華.《數(shù)據(jù)結(jié)構(gòu)》課程改革下的一堂教學(xué)實(shí)例――最小生成樹(shù)[J].隴東學(xué)院學(xué)報(bào)，2014，（03）.
[關(guān)鍵詞]軟件學(xué)院 數(shù)據(jù)結(jié)構(gòu) 項(xiàng)目導(dǎo)向
[作者簡(jiǎn)介]王峰（1970- ），男，河南湯陰人，華北水利水電學(xué)院，副教授，碩士，研究方向?yàn)檐浖こ?、?shù)據(jù)庫(kù)。（河南 鄭州 450011）魏秀然（1975- ），女，河南鄭州人，河南農(nóng)業(yè)大學(xué)，實(shí)驗(yàn)師，碩士，研究方向?yàn)檐浖こ?。（河?鄭州 450002）
[中圖分類號(hào)]G642.3 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1004-3985（2013）27-0140-02
河南省自2004年開(kāi)始啟動(dòng)示范性軟件職業(yè)技術(shù)學(xué)院建設(shè)工作，到現(xiàn)在共批準(zhǔn)鄭州大學(xué)等43所院校立項(xiàng)建設(shè)。軟件學(xué)院的辦學(xué)目標(biāo)，是為快速發(fā)展的軟件行業(yè)培養(yǎng)急需的一線工程師，培養(yǎng)層次一般為兩年制專科或四年制第三批本科，專業(yè)大多是軟件技術(shù)、信息管理等軟件開(kāi)發(fā)類專業(yè)。課程設(shè)置充分考慮企業(yè)需要，聘請(qǐng)具有豐富軟件開(kāi)發(fā)經(jīng)驗(yàn)的優(yōu)秀教師和軟件企業(yè)資深工程師任教，較注重培養(yǎng)學(xué)生的實(shí)踐動(dòng)手能力。
本文針對(duì)軟件學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)的現(xiàn)狀及課程建設(shè)中存在的相關(guān)問(wèn)題進(jìn)行分析，并結(jié)合多年的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的經(jīng)驗(yàn)，給出軟件學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程建設(shè)的思路。
一、軟件學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程建設(shè)中存在的問(wèn)題
一是課程學(xué)習(xí)難度大。軟件學(xué)院學(xué)生錄取分?jǐn)?shù)較低，基礎(chǔ)相對(duì)較差，因此理論性課程的教學(xué)難度較大。而“數(shù)據(jù)結(jié)構(gòu)”是一門理論性較強(qiáng)的課程，其概念抽象且算法復(fù)雜，導(dǎo)致在教學(xué)過(guò)程中，理論教學(xué)和實(shí)踐教學(xué)不能很好地結(jié)合起來(lái)， 加上學(xué)生的基礎(chǔ)薄弱，學(xué)習(xí)起來(lái)難度特別大。
二是學(xué)生的前導(dǎo)課程基礎(chǔ)不牢。按照教學(xué)要求，學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)前，必須學(xué)習(xí)一門程序設(shè)計(jì)語(yǔ)言，程序設(shè)計(jì)語(yǔ)言如果掌握不好，就無(wú)法理解和學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”課程中的諸多算法，直接影響了學(xué)生的學(xué)習(xí)能力和信心。
三是理論和實(shí)踐聯(lián)系不夠。數(shù)據(jù)結(jié)構(gòu)理論性強(qiáng)，主要介紹常用數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法。教材中一般只給出了算法的關(guān)鍵代碼，不包含相關(guān)的宏定義和結(jié)構(gòu)體定義，學(xué)生無(wú)法直接上機(jī)驗(yàn)證算法，學(xué)習(xí)的積極性不高。而且因?yàn)樗惴ǖ睦碚撔暂^強(qiáng)，離實(shí)際開(kāi)發(fā)項(xiàng)目較遠(yuǎn)，學(xué)生代入感差，理解算法較困難。
四是教師的教學(xué)方法單調(diào)。目前河南省的軟件學(xué)院均是由本科院校依托原有的計(jì)算機(jī)等院系進(jìn)行建設(shè)，大多數(shù)教師以前并沒(méi)有職業(yè)教育的經(jīng)歷和實(shí)踐工作經(jīng)驗(yàn)，如果照搬本科院系的辦學(xué)模式和課程建設(shè)方式，就會(huì)導(dǎo)致學(xué)生覺(jué)得“吃不消”。
五是實(shí)踐環(huán)節(jié)教學(xué)時(shí)間少。因受總學(xué)時(shí)限制等，大多數(shù)學(xué)校“數(shù)據(jù)結(jié)構(gòu)”實(shí)驗(yàn)課課時(shí)所占比重偏低，學(xué)生實(shí)踐機(jī)會(huì)少。
二、軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)課程建設(shè)目標(biāo)
與本科高等教育不同，軟件學(xué)院主要強(qiáng)調(diào)工程實(shí)踐與理論基礎(chǔ)并重，以能力培養(yǎng)為核心，著力培養(yǎng)具有高水平實(shí)踐能力的應(yīng)用型計(jì)算機(jī)人才，以滿足社會(huì)的需求。在課程學(xué)習(xí)過(guò)程上，應(yīng)當(dāng)以“必需、夠用”的原則，設(shè)置課程教學(xué)目標(biāo)。通過(guò)近幾年的教學(xué)實(shí)踐，筆者認(rèn)為軟件學(xué)院的“數(shù)據(jù)結(jié)構(gòu)”課程應(yīng)當(dāng)這樣建設(shè)：基于職業(yè)教育的特點(diǎn)、用人單位的需求及后續(xù)課程的需要，設(shè)置相應(yīng)的教學(xué)計(jì)劃；采用現(xiàn)代化的教學(xué)手段和教學(xué)方法，深入淺出，使學(xué)生理解“數(shù)據(jù)結(jié)構(gòu)”課程的基本知識(shí)；要考慮到學(xué)生參差不齊的水平，課程教學(xué)應(yīng)當(dāng)能夠滿足不同程度學(xué)生的需求；簡(jiǎn)單和常用算法要求學(xué)生理解掌握，復(fù)雜算法要求應(yīng)知即可。利用多媒體等各種手段來(lái)改善課堂教學(xué)的過(guò)程，加強(qiáng)課外輔導(dǎo)和實(shí)踐環(huán)節(jié)；利用動(dòng)畫、FLASH等手段幫助學(xué)生理解和掌握相關(guān)算法。
三、改革方式
1.調(diào)整教學(xué)計(jì)劃。（1）加強(qiáng)前導(dǎo)課程學(xué)習(xí)。學(xué)習(xí)是環(huán)環(huán)相扣的，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)也是一樣。如果沒(méi)有學(xué)好數(shù)據(jù)結(jié)構(gòu)的前導(dǎo)課程，可能就無(wú)法較好地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。C語(yǔ)言程序設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵前導(dǎo)課程?！皵?shù)據(jù)結(jié)構(gòu)”課程教材多數(shù)選用C語(yǔ)言描述算法，算法中大量使用C語(yǔ)言中的數(shù)組、結(jié)構(gòu)體、宏定義、指針和函數(shù)體這些編程知識(shí)，學(xué)生對(duì)它們的熟悉掌握程度，直接關(guān)系到數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)效果。僅通過(guò)一學(xué)期的課程學(xué)習(xí)，學(xué)生的程序設(shè)計(jì)水平還不是很強(qiáng)，這時(shí)直接開(kāi)始復(fù)雜算法的學(xué)習(xí)與設(shè)計(jì)，難免會(huì)有畏難情緒產(chǎn)生。如何來(lái)解決這個(gè)問(wèn)題呢？ 通過(guò)對(duì)省內(nèi)軟件學(xué)院的調(diào)研，提出以下建議：首先，增加C語(yǔ)言程序設(shè)計(jì)課程的學(xué)時(shí)，多數(shù)學(xué)校設(shè)置的64學(xué)時(shí)應(yīng)增加到80學(xué)時(shí)，同時(shí)實(shí)踐教學(xué)應(yīng)由原來(lái)的16學(xué)時(shí)增加到30學(xué)時(shí)；其次，不能照搬本科的教學(xué)大綱，應(yīng)按照“必需、夠用”的原則修訂教學(xué)大綱，同時(shí)加強(qiáng)實(shí)踐能力訓(xùn)練；最后，在“數(shù)據(jù)結(jié)構(gòu)”這門課開(kāi)始，可以利用一兩次課的時(shí)間來(lái)復(fù)習(xí)C 語(yǔ)言的相關(guān)知識(shí)（主要是指針、鏈表），并將這些學(xué)時(shí)納入到教學(xué)進(jìn)度表中。（2）調(diào)整數(shù)據(jù)結(jié)構(gòu)課程計(jì)劃。應(yīng)增加數(shù)據(jù)結(jié)構(gòu)課程的學(xué)時(shí)，由原來(lái)的64學(xué)時(shí)增加到80學(xué)時(shí)，同時(shí)實(shí)踐教學(xué)由20學(xué)時(shí)增加到30學(xué)時(shí)。目的是放慢講授速度，多上習(xí)題課，給學(xué)生留出充分消化吸收的時(shí)間。（3）增加C語(yǔ)言實(shí)訓(xùn)。建議在開(kāi)設(shè)數(shù)據(jù)結(jié)構(gòu)的學(xué)期初或前一學(xué)期末，增加1～2周的C語(yǔ)言實(shí)訓(xùn)，通過(guò)設(shè)計(jì)3～4個(gè)小型C語(yǔ)言程序來(lái)鞏固復(fù)習(xí)C語(yǔ)言的相關(guān)知識(shí)。
2.教材建設(shè)。目前，市場(chǎng)上有大量的數(shù)據(jù)結(jié)構(gòu)課程教材，大多比較注重理論上的探討。對(duì)于軟件學(xué)院，需要根據(jù)學(xué)生實(shí)際情況，選擇難易程度相當(dāng)，教學(xué)內(nèi)容分量適中的教材。教材選擇上，我們調(diào)研了大量的面向職業(yè)教育的教材，但發(fā)現(xiàn)大多是對(duì)清華大學(xué)嚴(yán)蔚敏編寫的數(shù)據(jù)結(jié)構(gòu)教材的刪減，并沒(méi)有增加更多的實(shí)用性或引導(dǎo)性內(nèi)容，反而使內(nèi)容變得不易理解。因此建議軟件學(xué)院仍選用嚴(yán)蔚敏編寫的“數(shù)據(jù)結(jié)構(gòu)”為主教材，再參照其他一些實(shí)用性教材為輔助教材。同時(shí)，河南省各軟件學(xué)院已經(jīng)開(kāi)始聯(lián)合編寫適合軟件學(xué)院教學(xué)的“數(shù)據(jù)結(jié)構(gòu)”教材。
3.分層次教學(xué)方式。軟件學(xué)院的學(xué)生入學(xué)成績(jī)有差異，理解能力有差異，因此更適合采取分層次教學(xué)方式。分層次教學(xué)方式的目的是讓每個(gè)學(xué)生都能在學(xué)習(xí)過(guò)程中一步步學(xué)到知識(shí)，有所收獲并贏得自己的成就感，最大程度地調(diào)動(dòng)學(xué)生學(xué)習(xí)的積極性。
對(duì)于“數(shù)據(jù)結(jié)構(gòu)”課程中的一些基本理論和算法，要求所有同學(xué)必須掌握，如線性表、排序、查找等，這些內(nèi)容要放慢講課節(jié)奏，不斷重復(fù)強(qiáng)調(diào)重點(diǎn)，多講解習(xí)題，并充分利用多媒體技術(shù)，采取直觀形象的教學(xué)方式，動(dòng)態(tài)演示算法過(guò)程等，加深學(xué)生對(duì)算法的理解。并盡量對(duì)照現(xiàn)實(shí)生活中的例子來(lái)引入知識(shí)點(diǎn)，如排隊(duì)、插隊(duì)、壓箱底（堆棧）等。
而對(duì)一些像找最短路徑這樣的復(fù)雜算法，要求多數(shù)同學(xué)明白算法目的和基本原理即可。對(duì)于個(gè)別成績(jī)較好的同學(xué)，利用答疑時(shí)間、實(shí)驗(yàn)時(shí)間對(duì)他們進(jìn)行額外輔導(dǎo)，單獨(dú)布置作業(yè)，要求他們充分理解算法，并最好能把算法轉(zhuǎn)化為程序運(yùn)行，還能根據(jù)教師要求對(duì)代碼進(jìn)行改進(jìn)。
4.項(xiàng)目導(dǎo)向。數(shù)據(jù)結(jié)構(gòu)課程中的多數(shù)知識(shí)理論性較強(qiáng)，在教學(xué)過(guò)程中應(yīng)注意引導(dǎo)分析，還應(yīng)提供一些有代表性的案例或小項(xiàng)目讓學(xué)生討論，如長(zhǎng)整數(shù)相加問(wèn)題、迷宮問(wèn)題、馬跳棋盤問(wèn)題、八皇后問(wèn)題等，由學(xué)生分組討論完成。討論前允許學(xué)生利用網(wǎng)絡(luò)等手段搜索相關(guān)資料，開(kāi)始可以把問(wèn)題簡(jiǎn)化，逐步加大難度，最終把完整程序提供給學(xué)生學(xué)習(xí)。對(duì)學(xué)習(xí)基礎(chǔ)好的學(xué)生要求逐步完成程序設(shè)計(jì)，對(duì)學(xué)習(xí)基礎(chǔ)差的學(xué)生要求明白思路即可。這樣一方面鍛煉了學(xué)生的動(dòng)手能力，促進(jìn)了學(xué)生間的交流與團(tuán)結(jié)協(xié)作；另一方面確實(shí)能將理論與實(shí)踐相結(jié)合，學(xué)以致用，從而大大激發(fā)學(xué)生的學(xué)習(xí)熱情，培養(yǎng)創(chuàng)新思維。
對(duì)于課程中的排序和搜索部分，可以設(shè)計(jì)一個(gè)簡(jiǎn)單的信息管理系統(tǒng)，讓學(xué)生完成按人名搜索、按電話搜索等項(xiàng)目，并比賽誰(shuí)的搜索速度快，從而練習(xí)相關(guān)算法。因?yàn)镃語(yǔ)言操作數(shù)據(jù)庫(kù)比較煩瑣，可以使用結(jié)構(gòu)體數(shù)組存放學(xué)生信息，把相關(guān)信息存放在文件中，并由教師把數(shù)據(jù)的輸入輸出部分實(shí)現(xiàn)，把一些搜索、排序函數(shù)留出讓學(xué)生去實(shí)現(xiàn)。這樣，學(xué)生既能享受到編程的樂(lè)趣，又不至于陷于煩瑣的數(shù)據(jù)輸入輸出處理部分。
5.豐富教學(xué)手段。目前，大多數(shù)高校的教室里都配備了計(jì)算機(jī)和投影設(shè)備，在“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)過(guò)程中，應(yīng)充分利用多媒體設(shè)備和多媒體技術(shù)進(jìn)行教學(xué)。
可以將數(shù)據(jù)結(jié)構(gòu)課程中的大多數(shù)算法制作成FLASH動(dòng)畫，F(xiàn)LASH不僅可動(dòng)動(dòng)態(tài)演示算法執(zhí)行過(guò)程，還可以直接看到每一句代碼的單步執(zhí)行效果，非常有利于學(xué)生對(duì)算法的掌握。例如，把堆排序的過(guò)程用動(dòng)畫來(lái)進(jìn)行演示，就可以很清楚地明白堆排序建堆、輸出堆頂、堆調(diào)整、完成排序的全過(guò)程。
這些FLASH動(dòng)畫可以嵌入到PPT課件中，也可以放到課程網(wǎng)站上供同學(xué)們查看。通過(guò)這些課件和動(dòng)畫的使用，教學(xué)效率和教學(xué)效果比傳統(tǒng)的教學(xué)方法有很明顯的提高，對(duì)學(xué)生的科研開(kāi)發(fā)能力有直接的啟發(fā)作用，同時(shí)，在適當(dāng)?shù)囊龑?dǎo)和濃厚的興趣驅(qū)使下，學(xué)生會(huì)躍躍欲試，進(jìn)行模仿設(shè)計(jì)。
除此以外，還應(yīng)該建立數(shù)據(jù)結(jié)構(gòu)課程網(wǎng)站，網(wǎng)站內(nèi)容包括：教學(xué)課件、習(xí)題與測(cè)試、實(shí)驗(yàn)項(xiàng)目、在線學(xué)習(xí)、動(dòng)畫演示、課堂視頻、作業(yè)上傳等。
“數(shù)據(jù)結(jié)構(gòu)”課程學(xué)生難學(xué)，教師也難教，但我們并不是束手無(wú)策，通過(guò)以上各種方法可以大大改善數(shù)據(jù)結(jié)構(gòu)的教學(xué)效果。教學(xué)改革不是一蹴而就的，這是一項(xiàng)長(zhǎng)期的任務(wù)，在以后的教學(xué)過(guò)程中，我們?nèi)詴?huì)通過(guò)不斷探索、不斷總結(jié)，讓學(xué)生在掌握知識(shí)的基礎(chǔ)上，舉一反三，能分析問(wèn)題、解決問(wèn)題，這樣才能較好地體現(xiàn)軟件學(xué)院培養(yǎng)應(yīng)用型人才的目標(biāo)。
[參考文獻(xiàn)]
王：確切地說(shuō)，是把順序結(jié)構(gòu)部分融入從C到C++的發(fā)展過(guò)程中，然后用C++描述非順序結(jié)構(gòu)部分。應(yīng)該表明，我們不是要否定數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立課程的意義，可是獨(dú)立不表示孤立，獨(dú)立表示這門課程有其特有的、重點(diǎn)研究的內(nèi)容，孤立是它與其他課程沒(méi)有聯(lián)系。而程序語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)是有內(nèi)在聯(lián)系的，我們要研究這種聯(lián)系，目的是探索程序語(yǔ)言發(fā)展的規(guī)律，促進(jìn)程序語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。
奚：數(shù)據(jù)結(jié)構(gòu)重點(diǎn)研究的內(nèi)容是什么呢？
王：算法分析。對(duì)一個(gè)問(wèn)題，僅僅編寫一個(gè)求解程序還不夠，處理大規(guī)模的復(fù)雜數(shù)據(jù)，一個(gè)程序能夠在合理的時(shí)間內(nèi)結(jié)束才有意義，這就需要對(duì)程序正文所代表的算法進(jìn)行嚴(yán)格的時(shí)間復(fù)雜度分析，而這種分析又必須和數(shù)據(jù)結(jié)構(gòu)一起進(jìn)行，因?yàn)闆](méi)有不依賴數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的算法，也沒(méi)有不為算法服務(wù)的數(shù)據(jù)結(jié)構(gòu)。
奚：所以數(shù)據(jù)結(jié)構(gòu)這門課程也可以叫做數(shù)據(jù)結(jié)構(gòu)和算法分析。
王：是的。我國(guó)最早引進(jìn)的一本數(shù)據(jù)結(jié)構(gòu)經(jīng)典教材的名稱便是“算法＋數(shù)據(jù)結(jié)構(gòu)＝程序”。
奚：數(shù)據(jù)結(jié)構(gòu)用偽碼描述在很長(zhǎng)一段時(shí)間是占主流的研究方法，您如何看待這種方法呢？
王：要?dú)v史地看待這個(gè)問(wèn)題。在二十世紀(jì)六十年代，數(shù)據(jù)結(jié)構(gòu)剛剛成為一門科學(xué)的時(shí)候，霍爾的“計(jì)算機(jī)程序設(shè)計(jì)公理化基礎(chǔ)”一文清楚地表明它的研究方法：把注意力集中到程序的構(gòu)成和分析方面，說(shuō)得更明確點(diǎn)，就是集中到程序正文所代表的算法的結(jié)構(gòu)上，以便在數(shù)學(xué)推理的基礎(chǔ)上對(duì)程序進(jìn)行嚴(yán)格的分析。[1]而用偽碼描述，可以不受程序?qū)崿F(xiàn)細(xì)節(jié)的影響，突出重點(diǎn)。再加上當(dāng)時(shí)個(gè)人電腦還不普及，描述數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言還只是主要供教學(xué)使用的PASCAL，而非實(shí)用的軟件開(kāi)發(fā)語(yǔ)言，使數(shù)據(jù)結(jié)構(gòu)的應(yīng)用范圍受到很大限制，這也從另一個(gè)方面促進(jìn)了這種偏向于學(xué)者的研究方法的形成。
奚：您不贊同這種方法嗎？
王：不能簡(jiǎn)單地說(shuō)贊同還是不贊同，要看研究的重點(diǎn)和學(xué)習(xí)的主體?！端惴ǎ珨?shù)據(jù)結(jié)構(gòu)＝程序》一書的作者沃思說(shuō)過(guò)：“盡管對(duì)于學(xué)者們來(lái)說(shuō)，純粹描述算法原則及其數(shù)學(xué)分析可能具有刺激性和挑戰(zhàn)性，但這對(duì)于實(shí)際工程人員似乎是不實(shí)在的。因此，我嚴(yán)格遵循這一原則：將程序的最終形式以某一語(yǔ)言表述出來(lái)，以便確實(shí)能在計(jì)算機(jī)上執(zhí)行?！盵1] 他認(rèn)為把程序表示為充分考慮細(xì)節(jié)的最終形式對(duì)工程人員是很重要的，因?yàn)槌绦蛟O(shè)計(jì)中，錯(cuò)誤正是隱藏在細(xì)節(jié)之中。[1]
奚：用偽碼描述和重視程序?qū)崿F(xiàn)細(xì)節(jié)是兩種對(duì)立的方法嗎？
王：不應(yīng)該是。用偽碼描述，可以突出數(shù)據(jù)結(jié)構(gòu)的研究重點(diǎn)――算法分析，重視程序?qū)崿F(xiàn)細(xì)節(jié)，可以認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)對(duì)程序語(yǔ)言發(fā)展的積極作用。
奚：這兩種方法可以統(tǒng)一起來(lái)嗎？
王：可以。隨著計(jì)算機(jī)的不斷普及，數(shù)據(jù)結(jié)構(gòu)這門課程不僅成為各大學(xué)計(jì)算機(jī)專業(yè)本科的主干課程，也成為非計(jì)算機(jī)類學(xué)生和研究生學(xué)習(xí)計(jì)算機(jī)的必修課程，這些學(xué)生大部分不屬于學(xué)者群，他們很難把偽碼描述的數(shù)據(jù)結(jié)構(gòu)用程序語(yǔ)言描述出來(lái)，并且在計(jì)算機(jī)上通過(guò)。
奚：他們需要用程序語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)的方法。
王：是的。
奚：可是如您所說(shuō)，數(shù)據(jù)結(jié)構(gòu)最初的描述語(yǔ)言是PASCAL，您為什么選擇了C呢？
王：從描述數(shù)據(jù)結(jié)構(gòu)的作用上說(shuō)，PASCAL和C是一樣的，但是從研究程序語(yǔ)言發(fā)展規(guī)律上說(shuō)，從C到C++比從PASCAL到C++更容易講述，而且C和C++都是軟件設(shè)計(jì)的核心語(yǔ)言，這種研究更有實(shí)際價(jià)值。
奚：現(xiàn)在不僅有許多用C描述的數(shù)據(jù)結(jié)構(gòu)教材，而且還有用C++、JAVA描述的，它們都不能滿足您的要求嗎？
王：應(yīng)該說(shuō)，是程序語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)相互脫節(jié)的教學(xué)模式不能滿足計(jì)算機(jī)科學(xué)發(fā)展的要求，教材是為教學(xué)服務(wù)的。這種教學(xué)模式的思想根源是，程序語(yǔ)言僅僅是描述數(shù)據(jù)結(jié)構(gòu)的工具，而數(shù)據(jù)結(jié)構(gòu)不依賴任何編程語(yǔ)言的描述，或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)既不影響程序語(yǔ)言的發(fā)展，也不受程序語(yǔ)言發(fā)展的影響?，F(xiàn)在，C++的最新發(fā)展將運(yùn)用最廣的一些數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)出來(lái)，而且成為C++新標(biāo)準(zhǔn)的一部分，使這種教學(xué)模式陷入一種困境：如果用C++描述數(shù)據(jù)結(jié)構(gòu)，就要先學(xué)習(xí)C++，而學(xué)習(xí)C++又需要數(shù)據(jù)結(jié)構(gòu)的知識(shí)。你中有我，我中有你。
奚：如何走出這個(gè)困境呢？
王：C++新標(biāo)準(zhǔn)為我們具體指出了走出這個(gè)困境的道路：首先把C++新標(biāo)準(zhǔn)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)內(nèi)容，例如連續(xù)順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)巾樞虼鎯?chǔ)結(jié)構(gòu)、string，歸入到C 語(yǔ)言教學(xué)中，用C語(yǔ)言實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)，完成對(duì)C語(yǔ)言的第一次辯證意義上的否定。
奚：如您在本期文章中所講述的那樣。
王：是的。然后發(fā)現(xiàn)問(wèn)題，再完成第二次辯證意義上的否定，把數(shù)據(jù)結(jié)構(gòu)的C代碼轉(zhuǎn)化為C++代碼，達(dá)到C++的新標(biāo)準(zhǔn)。這是我們下一期要講述的內(nèi)容。
奚：這是一個(gè)否定之否定的過(guò)程。
王：是的。這是C、C++和結(jié)構(gòu)的辯證關(guān)系決定的C的必然發(fā)展過(guò)程：C需要?jiǎng)?chuàng)建結(jié)構(gòu)，但是C語(yǔ)言結(jié)構(gòu)不能像語(yǔ)言內(nèi)部類型一樣使用，這不利于軟件重用程度的進(jìn)一步提高，于是，用戶從設(shè)計(jì)自定義數(shù)據(jù)類型開(kāi)始擴(kuò)展C語(yǔ)言 [2]，C++對(duì)C的結(jié)構(gòu)體類型作了實(shí)質(zhì)性的擴(kuò)充 [2]。可以說(shuō)，C++的許多性能都圍繞著一個(gè)根本的思想：創(chuàng)建新的數(shù)據(jù)類型的能力[3]。這就是哲學(xué)所說(shuō)的事物內(nèi)部的必然的自己的運(yùn)動(dòng)。
奚：這就是規(guī)律。
王：是的。這兩次否定過(guò)程構(gòu)成我們的教材《C/C++與數(shù)據(jù)結(jié)構(gòu)》（第3版）（上冊(cè)），可以作為C和C++語(yǔ)言教材。
奚：教材下冊(cè)的內(nèi)容呢？
王：用C++描述數(shù)據(jù)結(jié)構(gòu)非線性部分和算法的時(shí)間復(fù)雜度分析構(gòu)成我們的教材《C/C++與數(shù)據(jù)結(jié)構(gòu)》（第3版）（下冊(cè)）。這樣，數(shù)據(jù)結(jié)構(gòu)教學(xué)就可以在比較堅(jiān)實(shí)的C++語(yǔ)言基礎(chǔ)上，相對(duì)獨(dú)立地開(kāi)展算法研究。
奚：兩種方法統(tǒng)一了，既促進(jìn)C語(yǔ)言的學(xué)習(xí)，也促進(jìn)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。
王：是的。從C語(yǔ)言，到數(shù)據(jù)結(jié)構(gòu)的順序部分的C描述，再到C++，再到數(shù)據(jù)結(jié)構(gòu)的非順序部分的C++描述，
奚：那么就可以說(shuō)C、C++和數(shù)據(jù)結(jié)構(gòu)已經(jīng)成為相互包含的整體了？
王：可以這樣說(shuō)。我們要知道，辯證法所說(shuō)的相互包含或某物中包含他物，并不是指他物作為一個(gè)現(xiàn)成的細(xì)小的東西包含在某物中，而是作為某物的一個(gè)方面、一種趨勢(shì)、一種因素包含在某物中。C包含C++，是指C包含著C++作為其必然的發(fā)展。C++包含C是因?yàn)樗歉玫腃。
奚：這是否定之否定運(yùn)動(dòng)的結(jié)果。
王：或者說(shuō)是辯證運(yùn)動(dòng)的結(jié)果。
奚：那么如何把握這種辯證運(yùn)動(dòng)的實(shí)質(zhì)呢？
王：“兩個(gè)矛盾方面的共存、斗爭(zhēng)以及融合成一個(gè)新范疇，就是辯證運(yùn)動(dòng)的實(shí)質(zhì)。誰(shuí)要給自己提出消除壞的方面的任務(wù)，就是立即使辯證運(yùn)動(dòng)終結(jié)”。[4]
奚：就程序設(shè)計(jì)而言，兩個(gè)矛盾的方面就是存儲(chǔ)和處理。
王：或者說(shuō)是數(shù)據(jù)結(jié)構(gòu)和算法，數(shù)據(jù)結(jié)構(gòu)是發(fā)展的存儲(chǔ)?？v觀短暫的計(jì)算機(jī)發(fā)展史，這兩個(gè)方面一直保持不變。發(fā)展演化的是它們之間的關(guān)系，就是所謂的程序設(shè)計(jì)方法。[5]
奚：算法+數(shù)據(jù)結(jié)構(gòu)=程序，簡(jiǎn)明地表示了這種辯證運(yùn)動(dòng)的實(shí)質(zhì)。
王：是的。抓住矛盾，否定之否定這個(gè)過(guò)程就容易看出來(lái)了?？梢杂脗€(gè)比喻，形象的說(shuō)明這個(gè)否定之否定的過(guò)程。一顆麥粒種子，在適宜的土壤和氣候中發(fā)芽，是麥粒的一次否定，在精心培育下，它生長(zhǎng)，開(kāi)花，結(jié)果，最后又產(chǎn)生了麥粒，這是否定之否定。這兩次否定的結(jié)果就不僅是收獲更多的麥粒種子，而且種子的品質(zhì)得到改良。這個(gè)過(guò)程的每一次否定都推進(jìn)事物的完善化。
奚：可以把第一顆麥粒種子比作C，把在適宜的土壤和氣候中發(fā)芽比作數(shù)據(jù)結(jié)構(gòu)的C描述，把精心培育和收獲比作C++。
王：是這樣的。沒(méi)有適宜的土壤和氣候，種子不會(huì)發(fā)芽結(jié)果，類似，沒(méi)有數(shù)據(jù)結(jié)構(gòu)的C描述過(guò)程，就沒(méi)有C++的新標(biāo)準(zhǔn)。在數(shù)據(jù)結(jié)構(gòu)的C描述過(guò)程中，C語(yǔ)言內(nèi)部類型代表存儲(chǔ)，函數(shù)代表處理。要實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，就需要存儲(chǔ)復(fù)雜數(shù)據(jù)，而C語(yǔ)言沒(méi)有相應(yīng)的內(nèi)部類型，這就要求程序員自己在C語(yǔ)言的機(jī)制上構(gòu)造這樣的存儲(chǔ)。例如，雖然C數(shù)組類型提供了數(shù)據(jù)的連續(xù)存儲(chǔ)模式，但是沒(méi)有提供對(duì)數(shù)組插入、刪除等基本處理，而這是存儲(chǔ)應(yīng)該包含的內(nèi)容，它們是算法或者說(shuō)處理所依賴的方法。于是程序員通過(guò)創(chuàng)建基本函數(shù)克服了C的這種局限性，他們由此創(chuàng)建了基本順序表，結(jié)構(gòu)串等，作為語(yǔ)言類型的補(bǔ)充。不僅如此，C語(yǔ)言沒(méi)有直接支持鏈?zhǔn)酱鎯?chǔ)模式的類型，程序員還創(chuàng)建了鏈表存儲(chǔ)結(jié)構(gòu)（由于篇幅的限制，我們沒(méi)有在文章中一一講述這方面的內(nèi)容）。這個(gè)過(guò)程持續(xù)了約40年，可是人們簡(jiǎn)單地把它歸結(jié)為傳統(tǒng)的設(shè)計(jì)方法，如《標(biāo)準(zhǔn)C++寶典》一書中所說(shuō)，“在傳統(tǒng)的程序設(shè)計(jì)方法中，程序員先設(shè)計(jì)幾組數(shù)據(jù)結(jié)構(gòu)，然后用函數(shù)和過(guò)程處理這些數(shù)據(jù)。該方法稱為過(guò)程化程序設(shè)計(jì)，這種方法已經(jīng)沿用了40年”。[6]而實(shí)際上，在這個(gè)過(guò)程中，程序員不僅最大限度地克服了C語(yǔ)言局限性，而且也具體表達(dá)了對(duì)C語(yǔ)言未來(lái)方展的要求，這是改造世界的主體的主觀能動(dòng)性。
奚：程序語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)脫節(jié)的教學(xué)模式，把從C到C++的過(guò)程給抽象掉了。
王：是的，也可以說(shuō)是把人的主觀能動(dòng)性給抽象掉了，把改造世界的主體給抽象掉了，把認(rèn)識(shí)的主體也給抽象掉了，因?yàn)槿耸紫仁歉脑焓澜绲闹黧w，然后才是認(rèn)識(shí)世界的主體。
奚：那就是說(shuō)把學(xué)習(xí)的主動(dòng)性和積極性也給抽象掉了。
王：是的。主動(dòng)性和積極性不是固有的抽象物，而是產(chǎn)生于包含主體的改造世界的實(shí)踐活動(dòng)。
奚：這個(gè)活動(dòng)不存在了，主動(dòng)性和積極性也就不存在了。
王：C++迫使我們走上辯證唯物主義道路。這樣我們就會(huì)少走很多彎路。
參考文獻(xiàn)
[1] 沃思著.曹德和,劉椿年譯. 算法+數(shù)據(jù)=結(jié)構(gòu)程序[M]. 北京: 科學(xué)出版社,1987.1,5.
[2] AI Stevens，Clayton Walnum著.林麗閔,別紅霞譯.標(biāo)準(zhǔn)C++寶典.北京:電子工業(yè)出版社,2001.245.
[3] Bruce Eckel著.劉宗田,邢大紅,孫慧杰譯.C++編程思想[M].北京:機(jī)械工業(yè)出版社,2001.前言.
[4] 馬克思恩格斯全集（第4卷）. 北京: 人民出版社,1960. 145-146.
