陳 宏

西安歐亞學(xué)院信息工程學(xué)院，陜西西安 710065

數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)硬件、軟件之間的一門核心課程，其任務(wù)是討論現(xiàn)實世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)、在計算機(jī)中的存儲結(jié)構(gòu)以及各種操作的實現(xiàn)等問題。其中，線性表是一種最簡單、最基本，也是最常用的數(shù)據(jù)結(jié)構(gòu)，是學(xué)習(xí)者最先接觸到的一種數(shù)據(jù)結(jié)構(gòu)，但由于初學(xué)者對線性表在內(nèi)存中是如何存儲的，數(shù)據(jù)在計算機(jī)中是如何處理的，都不是很明確，所以剛開始學(xué)習(xí)該課程就產(chǎn)生了畏懼心理。因此，開發(fā)一個線性表的動態(tài)演示系統(tǒng)是有必要的。

線性表動態(tài)演示系統(tǒng)主要包括順序表和單鏈表兩種存儲結(jié)構(gòu)，通過演示為學(xué)生提供了形象生動、內(nèi)容豐富、直觀具體的感性認(rèn)識材料，使學(xué)生不再憑空想象，有利于調(diào)動學(xué)生的學(xué)習(xí)積極性，有利于培養(yǎng)學(xué)生的思維能力及解決問題的能力。本系統(tǒng)在Windows平臺上采用Visual C++可視化編程工具進(jìn)行開發(fā)，具體方法如下。

1 主菜單設(shè)計

線性表動態(tài)演示系統(tǒng)的主菜單包含三個菜單項，分別是“文件”菜單，“目錄”菜單和“幫助”菜單?！拔募辈藛魏幸粋€“退出”子菜單?！澳夸洝辈藛斡腥齻€子菜單，分別是線性表定義子菜單、順序表子菜單和單鏈表子菜單。“幫助”菜單含有一個“用戶使用說明”子菜單。

2 線性表定義

功能：描述了線性表的定義和特點。

繪圖算法：每輸出一行文字，輸出位置的Y軸坐標(biāo)移動固定的值，可以將多行文字顯示在客戶區(qū)。

3 順序表

1）順序表存儲結(jié)構(gòu)

功能：描述了線性表的順序存儲結(jié)構(gòu)并顯示了線性表的順序存儲結(jié)構(gòu)示意圖。

繪圖算法：每輸出一行文字，輸出位置的Y軸坐標(biāo)移動固定的值。

2）順序表插入數(shù)據(jù)演示

功能：將用戶輸入的數(shù)據(jù)元素插入到某個用戶給定數(shù)據(jù)串序列的固定位置上。

算法：

（1）順序表插入算法：順序表的插入位置不能小于0或大于順序表元素的個數(shù)，若插入位置不在此區(qū)間，彈出插入位置錯誤警告。當(dāng)插入位置大于順序表的存儲空間在該程序中就是屏幕能顯示矩形的個數(shù)，彈出錯誤警告。當(dāng)參數(shù)輸入正確時，順序表的插入算法是：首先把存儲單元長度（size）-1（因為順序表的存儲單元是從0開始編號）至插入位置（i）中的存儲單元的數(shù)據(jù)元素依次后移一個存儲單元，然后把數(shù)據(jù)元素x插入到存儲單元i中，最后順序表數(shù)據(jù)元素的個數(shù)加1。

（2）繪圖算法

在繪圖過程中，需要畫一個順序表，在程序中順序表的存儲結(jié)構(gòu)是用矩形表示的。首先獲取用戶輸入的串序列的數(shù)據(jù)個數(shù)（length），然后計算每個存儲單元的長度即矩形的長度（table），最后畫一個長度為100＋table×（length＋2）的矩形，并將其分割成length+2個等份，表示順序表的存儲單元。

3）順序表刪除數(shù)據(jù)演示

功能：將用戶輸入刪除位置上的數(shù)據(jù)從順序表中刪除的過程。

算法：

（1）順序表的刪除算法

刪除位置參數(shù)應(yīng)該滿足大于等于0且小于等于順序表的長度減1，當(dāng)參數(shù)不在此區(qū)間時，彈出參數(shù)輸入錯誤警告。當(dāng)參數(shù)輸入正確時，刪除步驟是：首先把刪除位置對應(yīng)的存儲單元的數(shù)據(jù)元素存放到一個變量中，然后把插入位置對應(yīng)的存儲單元的后一個存儲單元至順序表長度-1存儲單元的數(shù)據(jù)元素依次前移，最后把順序表數(shù)據(jù)元素的個數(shù)-1。

（2）繪圖算法

該模塊的繪圖算法和順序表的插入算法類似，在此就不在獒述。

4 單鏈表

1）單鏈表的存儲結(jié)構(gòu)

功能：描述單鏈表的存儲結(jié)構(gòu)，單鏈表的表示方法，單鏈表的存儲結(jié)構(gòu)示意圖。

繪圖算法：每輸出一行文字，輸出位置的Y軸坐標(biāo)移動固定的值。

2）單鏈表插入操作演示

功能：動態(tài)演示在單鏈表中插入一個數(shù)據(jù)元素的全過程。

算法描述：

（1）向鏈表中插入數(shù)據(jù)元素的算法：要在帶頭結(jié)點的單鏈表數(shù)據(jù)元素ai（i大于等于0且小于鏈表的數(shù)據(jù)元素的個數(shù)）結(jié)點前插入一個存放數(shù)據(jù)元素x的結(jié)點，首先要在單鏈表中尋找到存放數(shù)據(jù)元素ai-1的結(jié)點并由指針p指示，然后動態(tài)申請一個結(jié)點存儲空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點的數(shù)據(jù)元素域，最后修改新結(jié)點的指針域指向數(shù)據(jù)元素ai結(jié)點，并修改數(shù)據(jù)元素ai-1結(jié)點的指針域指向新結(jié)點q。

（2）繪圖算法：在（50，160）的位置畫一個矩形作為頭結(jié)點。以后每隔50個像素畫一個矩形作為鏈表的元素結(jié)點，直到矩形的個數(shù)等于鏈表數(shù)據(jù)元素的個數(shù)。待插結(jié)點的x軸坐標(biāo)是以插入位置結(jié)點x軸坐標(biāo)作為基準(zhǔn)的，y軸坐標(biāo)為260。

3）單鏈表刪除操作演示

功能：用戶輸入要刪除的位置，系統(tǒng)就會將要刪除位置的結(jié)點從鏈表中去掉。

算法：

（1）從鏈表中刪除數(shù)據(jù)元素的算法：要在帶頭結(jié)點的單鏈表中刪除數(shù)據(jù)元素ai所在結(jié)點，首先需要在單鏈表中尋找到存放數(shù)據(jù)元素ai-1的結(jié)點并由指針p指示，然后讓指針s指向被刪結(jié)點，并把數(shù)據(jù)元素ai的值賦予x，最后刪除ai所在結(jié)點，并動態(tài)釋放該結(jié)點的存儲空間。

（2）繪圖算法：從（50，160）的位置每隔50個像素依次繪制一個矩形，直到矩形個數(shù)等于鏈表元素個數(shù)加1，鏈表繪制完成。動態(tài)演示刪除過程時，用紅色筆畫線將待刪元素位置的前一個矩形和待刪元素位置的后一個矩形連接起來，再用白色筆畫線將原來待刪位置與前一矩形之間的連線和待刪位置與后一矩形之間的連線用白色筆重繪。

基于VC的線性表動態(tài)演示系統(tǒng)易用、靈活，具有良好的安全性。由于采用了面向?qū)ο缶幊?，所以易于擴(kuò)充。該系統(tǒng)界面友好、功能完善，生成的算法圖直觀、正確，為教學(xué)提供了有益的參考。

[1]朱站立.數(shù)據(jù)結(jié)構(gòu)[M].西安：西安電子科技大學(xué)出版社，2003，1：256.

[2]齊舒創(chuàng)作室.Visual C++6.0開發(fā)技巧及實例剖析[M].北京：清華大學(xué)出版社，1999，2：130.