基于Visual C++的數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法的演示系統(tǒng)

摘 要：本文利用Visual C++ 6.0開發(fā)平臺(tái)的可視化界面以及其中的MFC環(huán)境的優(yōu)點(diǎn)，設(shè)計(jì)并建立了一個(gè)基于C++的數(shù)據(jù)結(jié)構(gòu)的經(jīng)典算法的演示系統(tǒng)，這使得學(xué)生加深了算法的理解，也提高了學(xué)生的學(xué)習(xí)興趣，達(dá)到了更好的授課效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法；動(dòng)態(tài)演示

中圖分類號(hào)：TP391.72

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，也是計(jì)算機(jī)及相關(guān)專業(yè)考研和水平等級(jí)考試的必考科目，而且正逐漸發(fā)展成為眾多理工專業(yè)的熱門選修課[1]。這門課程在計(jì)算機(jī)專業(yè)中具有非常重要地位，這對(duì)于提高數(shù)據(jù)結(jié)構(gòu)算法的教學(xué)效率具有著一定的實(shí)用價(jià)值[2]。本系統(tǒng)利用Visual C++ 6.0作為開發(fā)平臺(tái)，基于SDI單文檔框架，通過將視圖一分為二，通過動(dòng)態(tài)創(chuàng)建非模態(tài)對(duì)話框來演示不同的算法。用繪圖或者Flash兩種方式表達(dá)出算法的思想。運(yùn)用VC編程語言，把一個(gè)程序中的算法和程序框架有效的結(jié)合起來，并且實(shí)現(xiàn)算法的動(dòng)態(tài)演示。

1 系統(tǒng)功能分析

本系統(tǒng)是基于SDI單文檔框架，采用基于對(duì)話框風(fēng)格的界面，整體采用分割視圖將視圖一分為二，左邊采用樹形控件為操作區(qū)，右邊視圖為顯示區(qū)，通過動(dòng)態(tài)創(chuàng)建非模態(tài)對(duì)話框來演示不同的算法。每個(gè)算法演示界面中都有其詳細(xì)的操作界面，本文以線性表的設(shè)計(jì)為例進(jìn)行說明，線性表菜單中順序表界面的功能如下：（1）順序表概念及相關(guān)算法描述：對(duì)演示算法的說明，清楚的表明算法思想。方便學(xué)生深入了解算法概念。（2）插入和刪除（選擇演示代碼）：在選擇代碼框中可以選擇插入或者刪除，操作時(shí)非法插入或者刪除系統(tǒng)不能接受并且彈出錯(cuò)誤提示。（3）開始：在輸入數(shù)據(jù)或者插入元素之后，點(diǎn)擊開始后調(diào)用相應(yīng)函數(shù)進(jìn)行算法演示。（4）暫停：演示過程中可以暫停。（5）恢復(fù)：在演示過程中或者完成后用戶想要恢復(fù)到初始狀態(tài)的話，可以用這個(gè)功能來把數(shù)據(jù)恢復(fù)到初始的狀態(tài)。（6）單步：可以使程序一個(gè)語句接著一個(gè)語句一步步的執(zhí)行。（7）執(zhí)行源碼：直接運(yùn)行源程序，真實(shí)的上機(jī)實(shí)踐感受。（8）圖形演示：在輸入數(shù)據(jù)后演示模塊點(diǎn)擊開始后演示模塊生成一個(gè)順序表并在順序表上方顯示。圖形的動(dòng)態(tài)對(duì)應(yīng)相應(yīng)的操作。

其他算法的演示跟順序表的相似，根據(jù)其特點(diǎn)實(shí)現(xiàn)相應(yīng)的功能。

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

2.1 Flash控制模塊設(shè)計(jì)

系統(tǒng)用繪圖或者Flash兩種方式表達(dá)出算法的思想。界面布局合理緊湊，功能清晰，界面簡(jiǎn)潔大方。結(jié)合功能分析，播放Flash功能可采用插入shockwave Flash object控件來實(shí)現(xiàn)二次開發(fā)。該控件對(duì)應(yīng)的類是CShockwaveFlash類。具體通過CShockwaveFlash：Create（）函數(shù)實(shí)現(xiàn)的。交互操作是通過兩個(gè)交互函數(shù)實(shí)現(xiàn)的：用來獲得Flash動(dòng)畫中變量name的值的GetVariable（LPCTSTR name），以及可以用來改變Flash動(dòng)畫中name變量值value的SetVariable（LPCTSTR name，LPCTSTR value）[3]。

2.2 算法描述及系統(tǒng)詳細(xì)設(shè)計(jì)

系統(tǒng)的算法演示包括：順序表操作、單鏈表操作、棧操作以及遍歷二叉樹過程，以順序表操作演示為例進(jìn)行說明，其他算法設(shè)計(jì)思路方法類似。

順序表算法描述。線性表是具有相同數(shù)據(jù)類型的n（n≥0）個(gè)數(shù)據(jù)元素的有限序列，通常記為：a1，a2，…ai-1，ai，ai+1，…an。順序表是指線性表中的所有元素按其邏輯順序相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中，其存儲(chǔ)地址與次序相同，所以也可以說它是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。它具有如下特點(diǎn)：

（1）每個(gè)元素所占的存儲(chǔ)空間在物理上是連續(xù)的。

（2）每個(gè)元素在順序表中是按邏輯順序一次存放的。

順序表的定義：

typedey int DataType；

typedey struct

{

DataType *Elem； //元素

int length； //當(dāng)前元素個(gè)數(shù)

int listsize； //順序表大小

}

需要定義參數(shù)：const UINT WM_MYMESSAGE = WM_USER + 100；當(dāng)左側(cè)樹型對(duì)話框接收到消息時(shí)，調(diào)用移動(dòng)函數(shù)，就可以實(shí)現(xiàn)非模態(tài)對(duì)話框隨主框架一起同步移動(dòng)。界面上添加兩個(gè)列表控件分別來存儲(chǔ)算法的代碼和算法運(yùn)行中產(chǎn)生的中間數(shù)據(jù)。添加兩個(gè)單旋鈕控件分別表示當(dāng)前演示操作的類型。當(dāng)單擊插入操作的單旋鈕時(shí)，就在代碼列表中動(dòng)態(tài)加載插入算法的代碼，否則，加載刪除算法的代碼。同時(shí)，為了實(shí)現(xiàn)交互性，還添加了多個(gè)編輯框存儲(chǔ)用戶輸入的數(shù)據(jù)及顯示算法的描述。另外，還設(shè)計(jì)了四個(gè)操作按鈕實(shí)現(xiàn)對(duì)算法演示的控制。整個(gè)界面的最上面區(qū)域是算法演示的繪圖區(qū)域，主要是繪制算法運(yùn)行中的各種狀態(tài)圖。整個(gè)算法演示是通過定時(shí)器來控制實(shí)現(xiàn)的。當(dāng)單步執(zhí)行時(shí)候，每一次單步按鈕消息中都可以獲取當(dāng)前算法代碼運(yùn)行的每一個(gè)步驟，并讀取當(dāng)前的結(jié)點(diǎn)數(shù)據(jù)元素信息，同時(shí)并繪制在上方由Picture控件組成的繪圖區(qū)域中。如果是自動(dòng)執(zhí)行，則根據(jù)當(dāng)前結(jié)點(diǎn)的數(shù)量和定時(shí)器來控制運(yùn)行的次數(shù)。每一個(gè)中間過程和單步執(zhí)行過程是相同的。用戶還可以通過單擊執(zhí)行源碼按鈕實(shí)現(xiàn)現(xiàn)場(chǎng)運(yùn)行程序，增強(qiáng)上機(jī)真實(shí)感體驗(yàn)。

3 結(jié)束語

系統(tǒng)將數(shù)據(jù)結(jié)構(gòu)中的一些常用算法，通過動(dòng)態(tài)繪圖的形式，或者Flash，將算法的思想動(dòng)態(tài)展示出來。系統(tǒng)具有一般的授課課件不能達(dá)到的動(dòng)態(tài)演示效果，并擁有精美的界面，系統(tǒng)具有的優(yōu)點(diǎn)如下：（1）基于SDI單文檔框架，并通過固定分割線以及窗口的大?。唬?）通過常用繪圖函數(shù)的組合，結(jié)合具體代碼，實(shí)現(xiàn)算法的演示。程序基本覆蓋了數(shù)據(jù)結(jié)構(gòu)中那些基本和重要的算法；提供了演示的算法主要包括線性表的基本操作（順序表、單鏈表創(chuàng)建、刪除等）、棧的入棧和出棧操作、二叉樹（二叉樹的三種遍歷）、最小生成樹等問題；（3）提供了一些算法的實(shí)例程序，即能夠直接運(yùn)行的源代碼。在程序中可直接通過按鈕調(diào)用.exe程序，也可直接查看源代碼；每個(gè)算法界面上提供了相關(guān)的算法詳細(xì)描述；（4）將數(shù)據(jù)結(jié)構(gòu)課程中所學(xué)的常用或重要的算法，和動(dòng)畫結(jié)合起來，包含制作好的Flash文件，更加形象的將算法的含義演示出來。（5）提供了背景音樂功能，演示時(shí)可以選擇是否播放。

本系統(tǒng)界面簡(jiǎn)潔大方，操作簡(jiǎn)單，圖形形象生動(dòng)，有背景音樂，這都有助于學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法的理解，也有助于學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的興趣，將能提高數(shù)據(jù)結(jié)構(gòu)算法教學(xué)的質(zhì)量和效率，值得推廣和使用。

參考文獻(xiàn)：

[1]張海潘.軟件工程導(dǎo)論[M].北京：清華大學(xué)出版社，2008（03）.

[2]楊樹林.算法演示軟件的設(shè)計(jì)思路?實(shí)現(xiàn)方法及技術(shù)[J].北京印刷學(xué)院學(xué)報(bào)，2003（03）：20-23.

[3]王曉東.計(jì)算計(jì)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2007（05）.

[4]王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)（C++版）[M].北京：清華大學(xué)出版社，2005（07）.

[5]周治鈺.開發(fā)應(yīng)用程序用戶界面設(shè)計(jì)的基本原則[J].三峽大學(xué)學(xué)報(bào)，2004（26）.

作者簡(jiǎn)介：禤世麗（1985.09-），女，廣西興業(yè)人，助教，碩士，研究方向：數(shù)據(jù)挖掘、數(shù)據(jù)庫應(yīng)用技術(shù)計(jì)計(jì)算機(jī)應(yīng)用技術(shù)等。

作者單位：欽州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，廣西欽州 535099

基金項(xiàng)目：基于協(xié)同創(chuàng)新的應(yīng)用型本科院校計(jì)算機(jī)專業(yè)實(shí)踐教學(xué)體系的研究（項(xiàng)目編號(hào)：2013C088）；模糊支持向量機(jī)及其在海洋災(zāi)害風(fēng)險(xiǎn)預(yù)測(cè)的應(yīng)用研究（項(xiàng)目編號(hào)：2013YB259）。