數據結構算法演示系統的設計與實現

劉鶴　王佳欣　段云鵬等

關鍵詞：算法；Python; GUI

中圖法分類號：TP311 文獻標識碼：A

1引言

近年來，隨著國內互聯網市場的快速發展，尤其在移動互聯網市場已經領先全球的大背景下，國內各大院校爭先開設計算機專業及軟件工程專業。而對于剛踏人大學的計算機專業的學生來說，“如何學習‘數據結構課程”就可能影響他們對本專業的學習態度，甚至是影響未來一生工作選擇的重大問題。之所以很多學生認為“數據結構”課程中的許多算法晦澀難懂，一方面是大學教材中對于算法的解釋多數只有讓人摸不著頭腦的代碼和算不上通俗的文字講解，另一方面大多數的學生并不能腳踏實地地去理解代碼中的邏輯。換言之，采用通過思考從而模擬的方式去“運行”代碼顯然不適合剛接觸計算機專業的大學生。反而，“數據結構”這門需要大量計算機基礎并且是計算機學習體系中的基礎課程將許多學生推向了學習編程的反面。因此，如何讓學生以簡單易懂的方式去學習算法，就成為每個開設計算機專業的院校需要研究的課題。

2系統設計

2.1概要設計

在概要設計階段，首先要解決的是系統如何實現的問題。之后，將系統的主要內容進行劃分，即劃分出系統的結構。壞的系統結構在模塊之間耦合度較高的情況下，甚至會導致原本只需要做一行的修改，結果卻出現涉及上百個模塊的情況。有經驗的開發者都知道，前期的混亂會在開發時拖自己的后腿。但是，開發者又背負著期限的壓力，所以只好繼續在混亂的系統設計中繼續制造混亂。在具有較好的系統結構后，無論是對系統進行開發或是維護的效率都將大大提高。

2.2系統功能結構設計

通過對需要完成的算法進行分析，可以大致將系統分為圖、排序、二叉樹三個模塊，本文以圖的存儲結構及遍歷算法來表示與實現，圖算法子系統模塊內容如圖1所示。

對單個算法實現的GUI程序分解成類似于MVC模式的結構，以及針對幾個小題，在不同的Python文件中解決。

（1）GUI界面：每個算法都會有一個獨立的GUI界面Python文件作為UI的顯示。

（2）Paint類：繼承了PyQt4庫中的QtGui.QGraphicsScene類，其中封裝了繪制開發需要的動畫的方法，以及動畫運行的邏輯方法。

（3）Text類：主要用于控制在GUI界面顯示的文本，并且對正在執行的語句進行背景色變紅的高亮顯示。

（4）Data類：用于封裝在算法運行過程中使用的數據，以及改變數據的方法。

2.3系統功能模塊描述

針對本系統的四個算法，每一個算法都有其子算法，每一個子算法都有些許不同的設計。圖的存儲結構及遍歷算法模塊如下。

（1）鄰接矩陣的插入：點擊新建圖按鈕，將數據清空并初始化界面：勾選有向圖并點擊新建圖，將得到有向圖的鄰接矩陣，使用數組表示數據元素和元素之間的關系；在動畫演示窗口雙擊，可以生成一個新的頂點；在輸入弧頂點的文本框中輸入弧名，再點擊插入弧按鈕就會生成弧。

（2）圖的廣度優先遍歷：點擊新建圖按鈕，將數據清空并初始化界面；勾選有向圖并點擊新建圖，將得到有向圖的鄰接矩陣；在動畫演示窗口雙擊，可以生成一個新的頂點；點住圖中的某一個頂點，再將鼠標拖拽到另一個頂點，就可以生成兩個頂點之間的邊（弧）；在輸入遍歷開始的頂點的文本框中輸入頂點名，點擊開始遍歷按鈕，就可以對當前的圖進行遍歷。

（3）圖的深度優先遍歷：步驟同圖的廣度優先遍歷。

3系統實現

系統的每個子界面都是根據要實現的算法內容所設計的，每個算法的數據結構不同使得算法動畫也不同，且控制面板上的各種控制按鈕的功能也各不相同。

3.1圖的算法

在圖的算法模塊中，圓圈代表圖的頂點，圓圈之間的直線代表無向圖中頂點之間的弧，帶箭頭的線代表有向圖中頂點之間的弧。圖的算法下有三個子界面，分別是鄰接矩陣、圖的深度優先遍歷、圖的廣度優先遍歷。鄰接矩陣界面有如下幾個功能。

只要在動畫演示窗口內雙擊，就會自動生成新的頂點，如圖2所示。

在該界面下的文本“輸入弧的頂點”右側輸入要生成的弧的兩個頂點名，再點擊插入弧按鈕，就會自動生成對應的弧，并改變動畫演示窗口中的圖形和鄰接矩陣窗口中的數組，如圖3所示。

若新建圖，則把原先的數據清除重置，而將“有向圖”勾選后，再點擊新建圖，就會生成一個有向圖。此時插入弧，在動畫演示窗口就會顯示為一個帶箭頭的弧，右側顯示鄰接矩陣的同時，也會顯示對應的數值，如圖4所示。

3.2深度優先遍歷的功能

與鄰接矩陣界面一樣，深度優先遍歷也能夠在動畫演示窗口點擊生成頂點。但是，與鄰接矩陣頁面又有所不同，在該界面可以通過用鼠標點住一個頂點，再拖拽到另一個頂點，從而生成弧，如圖5所示。

在文本輸入框輸入遍歷開始的結點后，點擊開始遍歷按鈕，可以自動進行深度優先遍歷動畫，并將訪問過的頂點和進入棧顯示在數據演示窗口，如圖6所示。

深度優先遍歷同樣可以通過新建圖清除重置數據，也可以通過勾選有向圖來創建有向圖進行深度優先遍歷，如圖7所示。

3.3廣度優先遍歷的功能

廣度優先遍歷的功能基本與深度優先遍歷相同，但其算法運行的過程及結果與深度優先遍歷有所不同，如圖8所示。

4結束語

該系統是一個圖形化用戶界面程序，使用的語言為Python和PyQt4庫，并且使用py2exe將py文件轉換成可執行文件（.exe），實現的功能主要有動畫與文本的同步演示、用戶交互式輸入數據、動畫執行及單步執行等，實現的算法包括圖（Graph）、排序、哈夫曼編碼、二叉樹。在經過程序的動畫演示后，這些復雜而又難以理解的算法也能夠被大部分學生所接受，達到提高學習效率的目的。

對于一個用于學習的工具來說，僅實現功能遠遠不夠，它需要的是真正被學生所使用、所接受。為此，必須從學生處獲取關于使用體驗的調查報告，再將調查報告轉換成需求和代碼。而本系統基于Python，擁有較好的可讀性與可修改性，在面臨需要對其進行擴展、增加部件的情況下，本系統的子系統之間相互獨立，因此也表現出極好的可擴展性。所以，該系統程序的開發將不會就此停滯，未來也會以開發新模塊并將其加入系統中和完善舊模塊為目標繼續前進。

作者簡介：

劉鶴（1979—），碩士，副教授，研究方向：計算機教育。