數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)的設計與實現(xiàn)

劉鶴　王佳欣　段云鵬等

關鍵詞：算法；Python; GUI

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

1引言

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

2系統(tǒng)設計

2.1概要設計

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

2.2系統(tǒng)功能結(jié)構(gòu)設計

通過對需要完成的算法進行分析，可以大致將系統(tǒng)分為圖、排序、二叉樹三個模塊，本文以圖的存儲結(jié)構(gòu)及遍歷算法來表示與實現(xiàn)，圖算法子系統(tǒng)模塊內(nèi)容如圖1所示。

對單個算法實現(xiàn)的GUI程序分解成類似于MVC模式的結(jié)構(gòu)，以及針對幾個小題，在不同的Python文件中解決。

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

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

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

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

2.3系統(tǒng)功能模塊描述

針對本系統(tǒng)的四個算法，每一個算法都有其子算法，每一個子算法都有些許不同的設計。圖的存儲結(jié)構(gòu)及遍歷算法模塊如下。

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

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

（3）圖的深度優(yōu)先遍歷：步驟同圖的廣度優(yōu)先遍歷。

3系統(tǒng)實現(xiàn)

系統(tǒng)的每個子界面都是根據(jù)要實現(xiàn)的算法內(nèi)容所設計的，每個算法的數(shù)據(jù)結(jié)構(gòu)不同使得算法動畫也不同，且控制面板上的各種控制按鈕的功能也各不相同。

3.1圖的算法

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

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

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

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

3.2深度優(yōu)先遍歷的功能

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

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

深度優(yōu)先遍歷同樣可以通過新建圖清除重置數(shù)據(jù)，也可以通過勾選有向圖來創(chuàng)建有向圖進行深度優(yōu)先遍歷，如圖7所示。

3.3廣度優(yōu)先遍歷的功能

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

4結(jié)束語

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

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

作者簡介：

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