數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)驗(yàn)平臺(tái)的設(shè)計(jì)與開(kāi)發(fā)

張 巖, 婁 久, 李秀坤, 劉 揚(yáng), 王春宇

(哈爾濱工業(yè)大學(xué)， 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 黑龍江 哈爾濱 150001)

?

數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)驗(yàn)平臺(tái)的設(shè)計(jì)與開(kāi)發(fā)

張 巖, 婁 久, 李秀坤, 劉 揚(yáng), 王春宇

(哈爾濱工業(yè)大學(xué)， 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 黑龍江 哈爾濱 150001)

為更好地滿足數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)需求，設(shè)計(jì)實(shí)現(xiàn)了一個(gè)以數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法為主體的雙邊教學(xué)實(shí)驗(yàn)平臺(tái)，可以支持教師的算法動(dòng)態(tài)教學(xué)演示和學(xué)生的自學(xué)推導(dǎo)。該平臺(tái)通過(guò)圖形化、虛擬化的方法逐步展示經(jīng)典數(shù)據(jù)結(jié)構(gòu)與算法分析和計(jì)算過(guò)程。同時(shí)為便于學(xué)生理解算法，避免界面化技術(shù)產(chǎn)生的工程代碼對(duì)算法代碼的干擾，該平臺(tái)提供控制臺(tái)代碼展示功能，學(xué)生可以通過(guò)控制臺(tái)和界面實(shí)現(xiàn)雙向輸入或輸出。該實(shí)驗(yàn)平臺(tái)可以幫助學(xué)生理解數(shù)據(jù)結(jié)構(gòu)課程中經(jīng)典算法的設(shè)計(jì)思想，設(shè)計(jì)策略，時(shí)空復(fù)雜性以及實(shí)現(xiàn)過(guò)程，使學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)與算法課程的教學(xué)內(nèi)容，提高課堂教學(xué)效率和學(xué)生的自學(xué)創(chuàng)新能力。

實(shí)驗(yàn)教學(xué)； 實(shí)驗(yàn)平臺(tái)； 數(shù)據(jù)結(jié)構(gòu)； 算法

0 引 言

“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)學(xué)科的基礎(chǔ)骨干核心課程，是本科教學(xué)的重中之重[1]。但由于課程內(nèi)容本身具有高度抽象性和較強(qiáng)的理論性，在學(xué)習(xí)時(shí)，學(xué)生會(huì)感到有些枯燥和單調(diào)，不容易理解[2-4]。因此，需要通過(guò)實(shí)驗(yàn)教學(xué)促進(jìn)學(xué)生對(duì)理論教學(xué)的理解，從而達(dá)到培養(yǎng)具有實(shí)踐創(chuàng)新能力人才的目的。然而，為達(dá)到這一目的不僅需要在教學(xué)模式和教學(xué)方法上進(jìn)行改革[5-6]，還需要借助于圖形化、虛擬化等信息技術(shù)構(gòu)建適應(yīng)教學(xué)需求的實(shí)驗(yàn)平臺(tái)[7-8]。

本文研究并設(shè)計(jì)了一種數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)驗(yàn)平臺(tái)，旨在對(duì)經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行歸納、分類、編碼和展示，教師可以用圖形化方式直觀地演示算法流程和代碼，學(xué)生可以通過(guò)該平臺(tái)學(xué)習(xí)和推演算法，這將加深學(xué)生對(duì)教學(xué)內(nèi)容的理解深度，有利于教學(xué)效率的提高和課后學(xué)生自學(xué)創(chuàng)新能力的培養(yǎng)。

1 實(shí)驗(yàn)平臺(tái)的總體設(shè)計(jì)

本實(shí)驗(yàn)平臺(tái)是雙邊實(shí)驗(yàn)平臺(tái)，即要求平臺(tái)不僅能夠支持教師的教學(xué)演示需求，還需要滿足輔助學(xué)生學(xué)習(xí)的需求。因此，平臺(tái)物理框架共為三層，即用戶層、應(yīng)用層和文件層，具體如圖1所示。從圖中可以看出，在用戶層中用戶可通過(guò)前端界面，選擇想要學(xué)習(xí)的算法或相應(yīng)的功能。如果用戶選擇的是算法學(xué)習(xí)，則用戶可根據(jù)所選擇的算法提供輸入，程序有簡(jiǎn)單的容錯(cuò)能力，如果輸入有誤，程序會(huì)在一定范圍內(nèi)給予提示和改正；在應(yīng)用層，程序會(huì)根據(jù)用戶提供的輸入和選擇的算法進(jìn)行運(yùn)算，然后將運(yùn)算結(jié)果返回給前臺(tái)，用戶即可查詢?yōu)g覽；在文件層，支持代碼查詢功能，如果用戶選擇的是代碼查詢功能，則系統(tǒng)會(huì)根據(jù)用戶選擇的算法，從文件中讀取相應(yīng)內(nèi)容，顯示到前臺(tái)。

圖1 平臺(tái)的物理架構(gòu)圖

1.2 功能模塊設(shè)計(jì)

通過(guò)實(shí)際調(diào)研和分析發(fā)現(xiàn)，學(xué)生在進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法課程的學(xué)習(xí)過(guò)程中，主要難點(diǎn)集中于非線性數(shù)據(jù)結(jié)構(gòu)、查找、排序算法以及數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用[9]。因此，為滿足教學(xué)需求，平臺(tái)設(shè)計(jì)了四個(gè)功能模塊，樹(shù)及樹(shù)的應(yīng)用模塊、圖及圖的應(yīng)用模塊、查找及排序模塊和綜合應(yīng)用模塊，具體包含內(nèi)容如圖2所示。平臺(tái)可以展示基于樹(shù)和圖等基本數(shù)據(jù)結(jié)構(gòu)的經(jīng)典算法代碼；展示基本數(shù)據(jù)結(jié)構(gòu)的查找、排序流程；能夠直觀地展示算法的運(yùn)行過(guò)程；并能夠分析算法效率。此外，用戶還能夠根據(jù)已完成的算法和界面，實(shí)現(xiàn)一個(gè)小的應(yīng)用。

數(shù)據(jù)結(jié)果經(jīng)典算法的分析及應(yīng)用 樹(shù)及樹(shù)的應(yīng)用模塊 圖及圖的應(yīng)用模塊樹(shù)的存儲(chǔ)及遍歷(包含各種存儲(chǔ)方式及遍歷方式)哈夫曼樹(shù)選擇樹(shù)判定樹(shù)BST樹(shù)AVL樹(shù)圖的存儲(chǔ)及遍歷(包含各種存儲(chǔ)方式及遍歷方式)Prim算法Kruskal算法BellmanFord算法Dijkstra算法Floyed算法查找排序模塊綜合應(yīng)用模塊線性查找二分查找選擇排序 插入排序 冒泡排序堆排序 希爾排序 快排序 歸并排序代碼展示流程圖展示啟動(dòng)界面算法綜合應(yīng)用模塊

圖2 平臺(tái)的功能結(jié)構(gòu)圖

2 實(shí)驗(yàn)平臺(tái)的開(kāi)發(fā)

2.1 樹(shù)及樹(shù)的應(yīng)用模塊開(kāi)發(fā)

樹(shù)及樹(shù)的應(yīng)用包含樹(shù)的經(jīng)典存儲(chǔ)方式及遍歷方法，如哈夫曼樹(shù)(含哈夫曼編碼)、勝者樹(shù)[10]、判定樹(shù)[11]、BST樹(shù)[12]、AVL樹(shù)[13]。在主屬性頁(yè)上方看到所有的算法信息，復(fù)選框高亮的部分為選擇的算法的信息，圖3～6分別給出哈夫曼樹(shù)、判定樹(shù)、選擇樹(shù)和BST樹(shù)的實(shí)例展示。

圖3 哈夫曼樹(shù)實(shí)例展示

圖4 判定樹(shù)實(shí)例展示

(1) 哈夫曼樹(shù)實(shí)例展示。圖3展示了哈夫曼樹(shù)及編碼過(guò)程，用戶可在輸入欄中輸入任何英文文章，不限內(nèi)容和字?jǐn)?shù)。然后可點(diǎn)擊建立哈夫曼樹(shù)按鈕，會(huì)彈出樹(shù)已建立提示，而后用戶可點(diǎn)擊哈夫曼編碼，就會(huì)在下方區(qū)域顯示具體的編碼。如果用戶對(duì)原有文章進(jìn)行修改，則需要重新建立樹(shù)，再次點(diǎn)擊哈夫曼編碼按鈕時(shí)，可重新編碼，用戶可比較修改后的結(jié)果和原有結(jié)果的不同。

(2) 判定樹(shù)實(shí)例展示。圖4展示了以八硬幣問(wèn)題為例的判定樹(shù)演示界面。用戶首先在屬性頁(yè)資源上選擇判定樹(shù)，這樣進(jìn)入判定樹(shù)頁(yè)面，可以修改圖中任何一個(gè)硬幣的重量，而后點(diǎn)擊判定按鈕，則會(huì)在對(duì)話框上顯示假硬幣重量，并告知用戶假硬幣較真硬幣是輕是重。所有硬幣初始值10 g，用戶可重復(fù)操作。

(3) 選擇樹(shù)實(shí)例展示。圖5為勝者樹(shù)展示界面。用戶首先在屬性頁(yè)資源上選取勝者樹(shù)按鈕，進(jìn)入勝者樹(shù)頁(yè)面，而后輸入需歸并的數(shù)量，再次輸入歸并段內(nèi)容，每個(gè)歸并段以‘ ’號(hào)分隔，數(shù)據(jù)輸入完成后擊建立選擇樹(shù)按鈕，可看到排序后的結(jié)果，并且在頁(yè)面的最下方給出了算法的時(shí)間復(fù)雜度分析。

公司的經(jīng)營(yíng)績(jī)效通過(guò)盈利能力、營(yíng)運(yùn)能力、償債能力、成長(zhǎng)能力等來(lái)表現(xiàn)，其中代表盈利能力的指標(biāo)如凈資產(chǎn)收益率、總資產(chǎn)收益率等，代表營(yíng)運(yùn)能力的指標(biāo)如總資產(chǎn)周轉(zhuǎn)率，代表償債能力的指標(biāo)如資產(chǎn)負(fù)債率、流動(dòng)比率等，代表成長(zhǎng)能力的指標(biāo)如營(yíng)業(yè)總收入同比增長(zhǎng)率等。

圖5 選擇樹(shù)的實(shí)例展示

(4) BST樹(shù)實(shí)例展示。圖6為BST樹(shù)的建立過(guò)程，首先用戶需在屬性頁(yè)上選擇BST 樹(shù)資源，進(jìn)入BST算法展示，而后用戶在輸入對(duì)話框中輸入節(jié)點(diǎn)信息，同時(shí)，用戶可隨時(shí)點(diǎn)擊插入、刪除、查找按鈕對(duì)BST樹(shù)進(jìn)行增刪改操作。最后可用中序輸出這個(gè)BST樹(shù)，由于樹(shù)的性質(zhì)，中序輸出是一個(gè)遞增序列。

圖6 BST樹(shù)的實(shí)例展示

2.2 圖及圖的應(yīng)用模塊的開(kāi)發(fā)

從圖2中可以看出，圖及圖的應(yīng)用模塊主要包含經(jīng)典的圖的建立與遍歷算法的展示，圖7～9分別為圖的建立及遍歷，BellmanFord算法[14]和Floyed[15]算法的實(shí)例展示。

(1) 圖的建立與遍歷實(shí)例展示。圖7展示了圖的建立和最基本遍歷算法，用戶可在界面最頂層輸入定點(diǎn)數(shù)和邊數(shù)，而后在第二行輸入頂點(diǎn)信息，在第三行輸入邊信息。當(dāng)用戶點(diǎn)擊建立圖按鍵時(shí)，系統(tǒng)可提示圖是否建立正確，如圖正確建立，則用戶點(diǎn)擊深度優(yōu)先或廣度優(yōu)先按鈕時(shí)，可查詢深度優(yōu)先和廣度優(yōu)先結(jié)果。

(2) BellmanFord算法實(shí)例展示。圖8展示了利用BellmanFord算法求單源最短路徑的過(guò)程，用戶可在本系統(tǒng)中輸入任意個(gè)圖，輸入方法和上例相同，而后點(diǎn)擊建立圖按鈕，如果圖正確建立，點(diǎn)擊BellmanFord算法按鈕，系統(tǒng)將用中文輸出運(yùn)行結(jié)果。

圖7 圖的建立及遍歷實(shí)例展示

圖8 BellmanFord算法的實(shí)例展示

(3) Floyed算法實(shí)例展示。圖9展示了利用Floyed算法求所有節(jié)點(diǎn)最短路徑的過(guò)程，在本實(shí)驗(yàn)平臺(tái)，用戶只需輸入想要遍歷的圖，點(diǎn)擊建立圖，程序就會(huì)自動(dòng)進(jìn)行迭代，將輸出的結(jié)果保存在距離矩陣中，用戶可在對(duì)話框內(nèi)隨便輸入兩節(jié)點(diǎn)編號(hào)，點(diǎn)擊Floyed算法，將會(huì)給出兩節(jié)點(diǎn)的最短路徑。

圖9 Floyed算法的實(shí)例展示

2.3 查找部分的開(kāi)發(fā)

查找排序部分所涉及的算法最多，但由于功能單一，這里只給出堆排序和二分搜索的實(shí)例展示界面。

(1) 堆排序算法實(shí)例展示。圖10為堆排序算法，用戶需輸入堆的大小和堆的內(nèi)容，點(diǎn)擊建立堆。同時(shí)用戶可通過(guò)點(diǎn)擊向堆中添加元素按鈕向堆中添加元素。當(dāng)用戶點(diǎn)擊堆排序按鈕時(shí)。系統(tǒng)會(huì)在最后一個(gè)對(duì)話框中以遞減的順序展示排序結(jié)果。

圖10 堆排序展示

(2) 二分搜索算法實(shí)例展示。圖11為二分搜索算法，用戶首先輸入數(shù)組大小和數(shù)組內(nèi)容，注意此處數(shù)組內(nèi)容要是一個(gè)有序序列，在查找項(xiàng)窗口中輸入待查找項(xiàng)，而后點(diǎn)擊查找按鈕，系統(tǒng)此時(shí)會(huì)顯示查找結(jié)果，如果存在則顯示數(shù)組下標(biāo)，不存在則顯示-1。

圖11 二分搜索展示

2.4 綜合應(yīng)用模塊的開(kāi)發(fā)

為了便于學(xué)生自學(xué)和實(shí)踐開(kāi)發(fā)，平臺(tái)設(shè)計(jì)了綜合應(yīng)用模塊，該模塊可以幫助學(xué)生通過(guò)圖形界面來(lái)實(shí)現(xiàn)算法演繹推理。圖12～15為圖的建立、遍歷以及最短路徑演繹結(jié)果。用戶首先通過(guò)鼠標(biāo)的點(diǎn)擊在對(duì)話框上建立圖的節(jié)點(diǎn)，然后通過(guò)鼠標(biāo)右鍵點(diǎn)擊兩個(gè)節(jié)點(diǎn)的圓心，建立圖的邊，邊的權(quán)值為兩個(gè)節(jié)點(diǎn)相距的像素值。在圖建立完成后，可選擇點(diǎn)擊深度優(yōu)先搜索或廣度優(yōu)先搜索按鈕，深度優(yōu)先是通過(guò)藍(lán)色點(diǎn)閃爍實(shí)現(xiàn)的，廣度優(yōu)先搜索是通過(guò)粉色點(diǎn)閃爍實(shí)現(xiàn)的。當(dāng)用戶點(diǎn)擊查找按鈕時(shí)，即選擇一個(gè)源點(diǎn)，再隨便點(diǎn)擊一個(gè)已經(jīng)建立好的點(diǎn)，則系統(tǒng)會(huì)按照最短路徑算法，用橙色的點(diǎn)標(biāo)定出路徑。

圖12 圖的建立

圖13 單源最短路徑展示

圖14 深度優(yōu)先算法

圖15 廣度優(yōu)先算法

3 結(jié) 語(yǔ)

數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)驗(yàn)平臺(tái)是一個(gè)雙邊教學(xué)實(shí)驗(yàn)平臺(tái)。教師利用該實(shí)驗(yàn)平臺(tái)展示算法流程及代碼，將抽象化的算法直觀化；學(xué)生通過(guò)參數(shù)設(shè)置、碼演示、流程演示和綜合開(kāi)發(fā)等環(huán)節(jié)，參與到教學(xué)實(shí)踐中，加深了對(duì)授課內(nèi)容的理解并提高了自身實(shí)踐創(chuàng)新的能力。同時(shí)，該平臺(tái)具有一定的通用性與擴(kuò)展性，可以對(duì)大規(guī)模數(shù)據(jù)進(jìn)行樹(shù)、圖等的運(yùn)算。因此，該平臺(tái)可以作為科學(xué)研究的基礎(chǔ)平臺(tái)，具有一定的推廣價(jià)值。

[1] 李曉鴻，駱嘉偉，季 潔.“數(shù)據(jù)結(jié)構(gòu)與算法分析”研究型實(shí)踐教學(xué)的探索[J]. 實(shí)驗(yàn)室研究與探索，2012，31(1)：121-125.

[2] 鄒恒明. 分而治之為上策：數(shù)據(jù)結(jié)構(gòu)課程的反思與變革[J]. 中國(guó)大學(xué)教學(xué)，2011(6)：53-56.

[3] 杜小坤，涂 韜. 數(shù)據(jù)結(jié)構(gòu)教學(xué)方法探討[J]. 計(jì)算機(jī)教育，2014(18)：46-48.

[4] 曹春萍，陳 平. 問(wèn)題驅(qū)動(dòng)法在“數(shù)據(jù)結(jié)構(gòu)”教學(xué)中的應(yīng)用探討[J].中國(guó)電力教育，2014(23)：78-79.

[5] 徐 翀. 微課在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用[J]. 中國(guó)教育信息化，2014(11)：37-39.

[6] 婁 久，李秀坤，張 茹. 軟件設(shè)計(jì)與開(kāi)發(fā)實(shí)踐課程探討分析[J].實(shí)驗(yàn)技術(shù)與管理，2012，29(4)：186-188.

[7] 劉小晶，鐘 琦，張劍平. 翻轉(zhuǎn)課堂模式在“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中的應(yīng)用研究[J]. 中國(guó)電化教育，2014，331：106-110.

[8] 林瑜華. 云計(jì)算環(huán)境下高校實(shí)驗(yàn)教學(xué)模式的創(chuàng)新與實(shí)踐[J]. 實(shí)驗(yàn)室研究與探索，2011，30(8)：271-274.

[9] 鹿 旸. 數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)方法的思考[J]. 計(jì)算機(jī)教育，2010(5)：88-90.

[10] 裴 松，武 彤. 擴(kuò)展哈弗曼前綴編碼實(shí)現(xiàn)XML數(shù)據(jù)與關(guān)系數(shù)據(jù)轉(zhuǎn)換[J].微型機(jī)與應(yīng)用，2013，32(17)：56-59.

[11] 維 斯. 數(shù)據(jù)結(jié)構(gòu)與算法分析——C語(yǔ)言描述[M].北京：機(jī)械工業(yè)出版，2010：186-188.

[12] Horowitz E，Sahni S，Rajas-ekaran S. Computer Algorithms [M]. Silicon Press，2008： 773-775.

[13] 鄭麗英. 數(shù)據(jù)結(jié)構(gòu)Trie及其應(yīng)用[J].現(xiàn)代計(jì)算機(jī)，2004，193：20-22.

[14] 李漢兵，喻建平，黃建雄,等. 基于時(shí)延限制的Bellman Ford算法[J]. 西安電子科技大學(xué)學(xué)報(bào)，2000，27(3)：330-334.

[15] Clifford A Shaffer. Data Structure and Algorithms(C++)[M]. Electronic Industry Press，2013：214-218.

Design and Development Experimental Platform for Data Structure Classical Algorithm

ZHANGYan，LOUJiu，LIXiu-kun，LIUYang，WANGChun-yu

(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001，China)

In order to meet the needs of the teaching of data structures and algorithms, a bilateral teaching experiment platform that can support teachers teaching and students self-teaching is designed and implemented for classic data structures and algorithms. It used graphical and visual technologies to gradually show the classic data structures and algorithms analysis and calculation processes. Meanwhile, in order to facilitate the students' understanding of algorithms and avoiding interface technology project code generated by the interference of the algorithm code, the platform provides console code display function, students can achieve bidirectional input or output via the console and interface. The experimental platform can greatly help students understand the data structures course in classical algorithm design, design strategy, time and space complexity and implementation process, it not only enables students to better grasp the teaching curriculum content of data structures and algorithms, but also improves the efficiency of classroom teaching and students' self-learning and innovative ability.

experiment teaching； experiment platform； data structure； algorithms

2015-01-08

2014年黑龍江省高等教育教學(xué)改革項(xiàng)目(JG2014010704)

張 巖(1965-)，男，黑龍江穆棱人，副教授，主要研究方向：數(shù)據(jù)庫(kù)、信息可用性管理、算法理論等。

Tel.:0451-86413341; E-mail:zhangy@hit.edu.cn

TP 30

A

1006-7167(2015)08-0127-04