數據結構經典算法實驗平臺的設計與開發

張 巖, 婁 久, 李秀坤, 劉 揚, 王春宇

(哈爾濱工業大學， 計算機科學與技術學院， 黑龍江 哈爾濱 150001)

?

數據結構經典算法實驗平臺的設計與開發

張 巖, 婁 久, 李秀坤, 劉 揚, 王春宇

(哈爾濱工業大學， 計算機科學與技術學院， 黑龍江 哈爾濱 150001)

為更好地滿足數據結構與算法課程教學需求，設計實現了一個以數據結構經典算法為主體的雙邊教學實驗平臺，可以支持教師的算法動態教學演示和學生的自學推導。該平臺通過圖形化、虛擬化的方法逐步展示經典數據結構與算法分析和計算過程。同時為便于學生理解算法，避免界面化技術產生的工程代碼對算法代碼的干擾，該平臺提供控制臺代碼展示功能，學生可以通過控制臺和界面實現雙向輸入或輸出。該實驗平臺可以幫助學生理解數據結構課程中經典算法的設計思想，設計策略，時空復雜性以及實現過程，使學生更好地掌握數據結構與算法課程的教學內容，提高課堂教學效率和學生的自學創新能力。

實驗教學； 實驗平臺； 數據結構； 算法

0 引 言

“數據結構與算法”是計算機學科的基礎骨干核心課程，是本科教學的重中之重[1]。但由于課程內容本身具有高度抽象性和較強的理論性，在學習時，學生會感到有些枯燥和單調，不容易理解[2-4]。因此，需要通過實驗教學促進學生對理論教學的理解，從而達到培養具有實踐創新能力人才的目的。然而，為達到這一目的不僅需要在教學模式和教學方法上進行改革[5-6]，還需要借助于圖形化、虛擬化等信息技術構建適應教學需求的實驗平臺[7-8]。

本文研究并設計了一種數據結構經典算法實驗平臺，旨在對經典數據結構和算法進行歸納、分類、編碼和展示，教師可以用圖形化方式直觀地演示算法流程和代碼，學生可以通過該平臺學習和推演算法，這將加深學生對教學內容的理解深度，有利于教學效率的提高和課后學生自學創新能力的培養。

1 實驗平臺的總體設計

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

圖1 平臺的物理架構圖

1.2 功能模塊設計

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

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

圖2 平臺的功能結構圖

2 實驗平臺的開發

2.1 樹及樹的應用模塊開發

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

圖3 哈夫曼樹實例展示

圖4 判定樹實例展示

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

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

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

公司的經營績效通過盈利能力、營運能力、償債能力、成長能力等來表現，其中代表盈利能力的指標如凈資產收益率、總資產收益率等，代表營運能力的指標如總資產周轉率，代表償債能力的指標如資產負債率、流動比率等，代表成長能力的指標如營業總收入同比增長率等。

圖5 選擇樹的實例展示

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

圖6 BST樹的實例展示

2.2 圖及圖的應用模塊的開發

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

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

(2) BellmanFord算法實例展示。圖8展示了利用BellmanFord算法求單源最短路徑的過程，用戶可在本系統中輸入任意個圖，輸入方法和上例相同，而后點擊建立圖按鈕，如果圖正確建立，點擊BellmanFord算法按鈕，系統將用中文輸出運行結果。

圖7 圖的建立及遍歷實例展示

圖8 BellmanFord算法的實例展示

(3) Floyed算法實例展示。圖9展示了利用Floyed算法求所有節點最短路徑的過程，在本實驗平臺，用戶只需輸入想要遍歷的圖，點擊建立圖，程序就會自動進行迭代，將輸出的結果保存在距離矩陣中，用戶可在對話框內隨便輸入兩節點編號，點擊Floyed算法，將會給出兩節點的最短路徑。

圖9 Floyed算法的實例展示

2.3 查找部分的開發

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

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

圖10 堆排序展示

(2) 二分搜索算法實例展示。圖11為二分搜索算法，用戶首先輸入數組大小和數組內容，注意此處數組內容要是一個有序序列，在查找項窗口中輸入待查找項，而后點擊查找按鈕，系統此時會顯示查找結果，如果存在則顯示數組下標，不存在則顯示-1。

圖11 二分搜索展示

2.4 綜合應用模塊的開發

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

圖12 圖的建立

圖13 單源最短路徑展示

圖14 深度優先算法

圖15 廣度優先算法

3 結 語

數據結構經典算法實驗平臺是一個雙邊教學實驗平臺。教師利用該實驗平臺展示算法流程及代碼，將抽象化的算法直觀化；學生通過參數設置、碼演示、流程演示和綜合開發等環節，參與到教學實踐中，加深了對授課內容的理解并提高了自身實踐創新的能力。同時，該平臺具有一定的通用性與擴展性，可以對大規模數據進行樹、圖等的運算。因此，該平臺可以作為科學研究的基礎平臺，具有一定的推廣價值。

[1] 李曉鴻，駱嘉偉，季 潔.“數據結構與算法分析”研究型實踐教學的探索[J]. 實驗室研究與探索，2012，31(1)：121-125.

[2] 鄒恒明. 分而治之為上策：數據結構課程的反思與變革[J]. 中國大學教學，2011(6)：53-56.

[3] 杜小坤，涂 韜. 數據結構教學方法探討[J]. 計算機教育，2014(18)：46-48.

[4] 曹春萍，陳 平. 問題驅動法在“數據結構”教學中的應用探討[J].中國電力教育，2014(23)：78-79.

[5] 徐 翀. 微課在數據結構課程中的應用[J]. 中國教育信息化，2014(11)：37-39.

[6] 婁 久，李秀坤，張 茹. 軟件設計與開發實踐課程探討分析[J].實驗技術與管理，2012，29(4)：186-188.

[7] 劉小晶，鐘 琦，張劍平. 翻轉課堂模式在“數據結構”課程教學中的應用研究[J]. 中國電化教育，2014，331：106-110.

[8] 林瑜華. 云計算環境下高校實驗教學模式的創新與實踐[J]. 實驗室研究與探索，2011，30(8)：271-274.

[9] 鹿 旸. 數據結構與算法課程教學方法的思考[J]. 計算機教育，2010(5)：88-90.

[10] 裴 松，武 彤. 擴展哈弗曼前綴編碼實現XML數據與關系數據轉換[J].微型機與應用，2013，32(17)：56-59.

[11] 維 斯. 數據結構與算法分析——C語言描述[M].北京：機械工業出版，2010：186-188.

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

[13] 鄭麗英. 數據結構Trie及其應用[J].現代計算機，2004，193：20-22.

[14] 李漢兵，喻建平，黃建雄,等. 基于時延限制的Bellman Ford算法[J]. 西安電子科技大學學報，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年黑龍江省高等教育教學改革項目(JG2014010704)

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

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

TP 30

A

1006-7167(2015)08-0127-04