智能化數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)輔助演示系統(tǒng)

● 引言

《數(shù)據(jù)結(jié)構(gòu)》這門課程對(duì)于大多數(shù)初學(xué)者來(lái)說(shuō)十分抽象，枯燥無(wú)味，尤其是實(shí)驗(yàn)內(nèi)容里面關(guān)于各種數(shù)據(jù)結(jié)構(gòu)的算法程序較以前學(xué)過(guò)的程序設(shè)計(jì)內(nèi)容更復(fù)雜，也不容易被理解，學(xué)生學(xué)起來(lái)十分吃力，所以我們希望有一種工具輔助實(shí)驗(yàn)教學(xué)，使抽象的內(nèi)容形象化，改善實(shí)驗(yàn)教學(xué)環(huán)境，并使學(xué)生加深對(duì)程序的理解，提高學(xué)生學(xué)習(xí)的興趣。

基于以上兩個(gè)原因，我們開發(fā)了智能化數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)輔助演示系統(tǒng)，它可以滿足學(xué)生的這種需要，把數(shù)據(jù)結(jié)構(gòu)中那些復(fù)雜的算法以直觀生動(dòng)的形式呈現(xiàn)出來(lái)，并且能生成適合個(gè)別化學(xué)習(xí)的教學(xué)內(nèi)容和策略，給出系統(tǒng)建議，從而輔助教師更好地把知識(shí)傳授給學(xué)生。

● 系統(tǒng)功能簡(jiǎn)介

1.系統(tǒng)的功能簡(jiǎn)介

智能化數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)輔助演示系統(tǒng)的最大特點(diǎn)是具有智能性，它可根據(jù)學(xué)生以前的學(xué)習(xí)情況，給出系統(tǒng)建議和相應(yīng)水平的測(cè)試題。它采用建構(gòu)主義學(xué)習(xí)方法，以學(xué)生為中心，以測(cè)試題為驅(qū)動(dòng)，引導(dǎo)學(xué)生自主學(xué)習(xí)，使學(xué)生能更加深刻地理解所學(xué)的內(nèi)容。

這一系統(tǒng)從總體上可分為前端和后端，前端包括人機(jī)交互子系統(tǒng)，后端包括學(xué)習(xí)環(huán)境子系統(tǒng)、教學(xué)決策子系統(tǒng)和領(lǐng)域知識(shí)庫(kù)。人機(jī)交互子系統(tǒng)向用戶提供了友好的學(xué)習(xí)界面，其由用戶注冊(cè)登錄界面、學(xué)習(xí)主界面、系統(tǒng)給出建議界面等組成。學(xué)習(xí)環(huán)境子系統(tǒng)圍繞各種典型算法，展開講解，它是這個(gè)教學(xué)輔助系統(tǒng)最基礎(chǔ)最主要的內(nèi)容。教學(xué)決策子系統(tǒng)根據(jù)一些決策原則和學(xué)生以前的學(xué)習(xí)情況給出適合學(xué)生當(dāng)前水平的系統(tǒng)建議和測(cè)試題，這個(gè)子系統(tǒng)是本系統(tǒng)智能化的核心。領(lǐng)域知識(shí)庫(kù)存儲(chǔ)與演示算法相關(guān)的知識(shí)點(diǎn)、知識(shí)單元等內(nèi)容，為教學(xué)決策子系統(tǒng)提供了決策的依據(jù)。圖1是該子系統(tǒng)的系統(tǒng)功能圖。

2.學(xué)習(xí)環(huán)境子系統(tǒng)簡(jiǎn)介

子系統(tǒng)以用克魯斯卡爾算法生成最小生成樹為例探討數(shù)據(jù)結(jié)構(gòu)中典型算法的演示過(guò)程，以此作為標(biāo)準(zhǔn)模板，逐步完善系統(tǒng)的實(shí)現(xiàn)，下面以克魯斯卡爾為例來(lái)介紹學(xué)習(xí)環(huán)境子系統(tǒng)的主要功能。

（1）輸入數(shù)據(jù)：先輸入圖的頂點(diǎn)個(gè)數(shù)，然后依次輸入每一條邊，這樣系統(tǒng)就記下了原始的圖。

（2）連續(xù)運(yùn)行：輸入數(shù)據(jù)后，界面上顯示連續(xù)運(yùn)行后原始圖、原始圖的臨界矩陣、最小生成樹、最小生成樹的鄰接矩陣及源程序代碼。

（3）單步運(yùn)行：連續(xù)運(yùn)行后，就可以單步運(yùn)行，每次只執(zhí)行一行代碼，同時(shí)與每行代碼相關(guān)的變量也顯示在界面上，最小生成樹、其鄰接矩陣和相關(guān)變量也隨著程序的執(zhí)行相應(yīng)的發(fā)生變化。

（4）設(shè)置斷點(diǎn)：如果想要程序執(zhí)行到某條語(yǔ)句停下來(lái)，就可以設(shè)置相應(yīng)的斷點(diǎn)，接著與單步運(yùn)行執(zhí)行過(guò)程一樣，直至執(zhí)行到設(shè)置斷點(diǎn)的位置。

● 實(shí)現(xiàn)過(guò)程中的技術(shù)難點(diǎn)

1.克魯斯卡爾算法類模型的設(shè)計(jì)和實(shí)現(xiàn)

我們之所以選擇克魯斯卡爾算法作為模板，是因?yàn)樵跀?shù)據(jù)結(jié)構(gòu)中，用克魯斯卡爾算法生成最小生成樹這個(gè)算法僅憑老師在黑板上講不夠直觀，因此不容易被理解。此外它是非常經(jīng)典的算法，基本不會(huì)隨著時(shí)間的推移而修改。在本系統(tǒng)中我們把克魯斯卡爾算法設(shè)計(jì)成一個(gè)類，克魯斯卡爾算法類包括四個(gè)成員變量，它們分別是頂點(diǎn)個(gè)數(shù)、頂點(diǎn)的連通分量數(shù)組、原始圖的鄰接矩陣及圖的最小生成樹鄰接矩陣；包括三個(gè)成員函數(shù)，分別是獲得頂點(diǎn)數(shù)函數(shù)、原始圖的初始化函數(shù)、將圖轉(zhuǎn)化成最小生成樹的函數(shù)。具體實(shí)現(xiàn)過(guò)程如下：

（1）原始圖的初始化函數(shù)：從前端接受頂點(diǎn)個(gè)數(shù)、原始圖的鄰接矩陣，并把最小生成樹的鄰接矩陣和原始圖的鄰接矩陣中無(wú)權(quán)值的位置都賦為-1，把各頂點(diǎn)的連通分量設(shè)為各不相同。

（2）把圖轉(zhuǎn)化成最小生成樹的函數(shù)流程如圖2所示。

2.讀寫文件

為了達(dá)到算法演示直觀動(dòng)態(tài)的效果，需要給出算法的動(dòng)態(tài)演示環(huán)境。但由于系統(tǒng)運(yùn)行時(shí)脫離算法程序的調(diào)試環(huán)境，需在連續(xù)運(yùn)行時(shí)把運(yùn)行過(guò)程每一步的結(jié)果寫入文件，在單步運(yùn)行和設(shè)置斷點(diǎn)時(shí)從文件中把每一步結(jié)果一條條地讀出，然后給學(xué)生。在這一過(guò)程中，就要頻繁地讀寫文件。常用讀寫文件的函數(shù)如下：

（1）fopen：打開一個(gè)文件，以一個(gè)文件指針名稱代表此文件，設(shè)置此文件屬性并在主存儲(chǔ)器規(guī)劃一個(gè)緩沖區(qū)來(lái)暫時(shí)存放數(shù)據(jù)。其語(yǔ)法說(shuō)明如下：FILE *fopen（const char *filename，const *mode）；即以一個(gè)指定屬性打開文件。

（2）flose：關(guān)閉此文件，并釋放所用緩沖區(qū)。其語(yǔ)法說(shuō)明如下：int fclose（FILE *stream）；即將文件指針?biāo)鶎?duì)應(yīng)的數(shù)據(jù)文件關(guān)閉。

（3）fprintf：以格式化將數(shù)據(jù)寫于文件中，只能用于循環(huán)文件。其語(yǔ)法說(shuō)明如下：Intfprintf（FILE*stream，const char * format[，argument，…]）。

（4）fscanf：以格式化將文件中數(shù)據(jù)讀取，并存于變量中，只能用于循環(huán)文件，其語(yǔ)法說(shuō)明如下： Int fscanf（FILE *stream，const char *format[，address，…]）。

在本系統(tǒng)中主要使用以下兩條寫語(yǔ)句：①fprintf（order，“%d”，flag）；②fprintf（data1，“%d…”，flag，…）；其中order文件存儲(chǔ)源程序編號(hào)，data文件存儲(chǔ)order文件中每一個(gè)編號(hào)對(duì)應(yīng)的一行源程序中的變量及其值，flag表示每一行源程序的編號(hào)。

3.單步運(yùn)行和設(shè)置斷點(diǎn)

為了讓學(xué)生更加清晰地認(rèn)識(shí)程序的執(zhí)行過(guò)程和最小生成樹是怎樣從原始圖中一步步獲得的，本系統(tǒng)除了能夠連續(xù)運(yùn)行外，還設(shè)置了單步運(yùn)行，在單步運(yùn)行時(shí)，程序執(zhí)行到哪一步，相應(yīng)的源代碼就被亮條覆蓋，以示區(qū)別，同時(shí)與本條代碼相關(guān)的變量也被顯示出來(lái)了。這里需要再次強(qiáng)調(diào)的是，單步運(yùn)行時(shí)并不是程序真的在一步步執(zhí)行，亮條覆蓋的語(yǔ)句也不是正在執(zhí)行的語(yǔ)句。算法程序脫離了程序的調(diào)試環(huán)境，不能夠真正實(shí)現(xiàn)這些功能，真正執(zhí)行程序是在連續(xù)運(yùn)行時(shí)，單步執(zhí)行只不過(guò)是把連續(xù)運(yùn)行時(shí)寫入文件的執(zhí)行結(jié)果以單步的形式顯示給學(xué)生，以達(dá)到更直觀明了的目的。為了實(shí)現(xiàn)這個(gè)功能，需要在連續(xù)運(yùn)行時(shí)寫兩個(gè)文件order和文件data1，order中只寫入源程序每一條語(yǔ)句的編號(hào)，從零開始；文件data1寫入order文件中的每一個(gè)編號(hào)對(duì)應(yīng)的一行源程序變量及其值。單步運(yùn)行時(shí)，首先從order文件中讀出源程序的標(biāo)號(hào)，同時(shí)到data1文件中讀出此標(biāo)號(hào)對(duì)應(yīng)的變量和它的值，判斷如果沒(méi)有到文件尾，把標(biāo)號(hào)對(duì)應(yīng)的一行程序加亮條顯示，同時(shí)顯示相應(yīng)的變量和它的值。

如果學(xué)生想看到程序從開始到某一固定位置的單步運(yùn)行過(guò)程，就需要設(shè)置斷點(diǎn)，設(shè)置斷點(diǎn)時(shí)，首先應(yīng)讓系統(tǒng)記住要執(zhí)行到的位置，點(diǎn)擊源程序中的任意條語(yǔ)句，系統(tǒng)就會(huì)把這個(gè)位置記下，用一條語(yǔ)句（x=listbox->itemindex）即可，以后就用x控制程序的執(zhí)行，直到完成，這里所用到的技術(shù)同單步運(yùn)行時(shí)基本相同。

● 結(jié)論

本系統(tǒng)借助MySQL4.0數(shù)據(jù)庫(kù)，運(yùn)用Borland C++ Builder 6.0這種編程工具開發(fā)，并在Windows 2000 server環(huán)境下調(diào)試成功。