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

● 引言

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

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

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

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

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

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

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

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

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

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

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

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

● 實現(xiàn)過程中的技術(shù)難點

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

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

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

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

2.讀寫文件

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

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

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

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

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

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

3.單步運行和設(shè)置斷點

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

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

● 結(jié)論

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