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

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

?

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

實(shí)驗(yàn)教學(xué)； 實(shí)驗(yàn)平臺； 數(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é)生會感到有些枯燥和單調(diào)，不容易理解[2-4]。因此，需要通過實(shí)驗(yàn)教學(xué)促進(jìn)學(xué)生對理論教學(xué)的理解，從而達(dá)到培養(yǎng)具有實(shí)踐創(chuàng)新能力人才的目的。然而，為達(dá)到這一目的不僅需要在教學(xué)模式和教學(xué)方法上進(jìn)行改革[5-6]，還需要借助于圖形化、虛擬化等信息技術(shù)構(gòu)建適應(yīng)教學(xué)需求的實(shí)驗(yàn)平臺[7-8]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 圖及圖的應(yīng)用模塊的開發(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算法求單源最短路徑的過程，用戶可在本系統(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)最短路徑的過程，在本實(shí)驗(yàn)平臺，用戶只需輸入想要遍歷的圖，點(diǎn)擊建立圖，程序就會自動進(jìn)行迭代，將輸出的結(jié)果保存在距離矩陣中，用戶可在對話框內(nèi)隨便輸入兩節(jié)點(diǎn)編號，點(diǎn)擊Floyed算法，將會給出兩節(jié)點(diǎn)的最短路徑。

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

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

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

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

圖10 堆排序展示

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

圖11 二分搜索展示

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

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

圖12 圖的建立

圖13 單源最短路徑展示

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

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

3 結(jié) 語

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

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

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

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

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

[7] 劉小晶，鐘 琦，張劍平. 翻轉(zhuǎn)課堂模式在“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中的應(yīng)用研究[J]. 中國電化教育，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語言描述[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ù)庫、信息可用性管理、算法理論等。

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

TP 30

A

1006-7167(2015)08-0127-04