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

● 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.讀寫文件

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

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

（2）flose：關閉此文件，并釋放所用緩沖區(qū)。其語法說明如下：int fclose（FILE *stream）；即將文件指針所對應的數(shù)據(jù)文件關閉。

（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文件中每一個編號對應的一行源程序中的變量及其值，flag表示每一行源程序的編號。

3.單步運行和設置斷點

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

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

● 結論

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