線性表動(dòng)態(tài)演示系統(tǒng)的設(shè)計(jì)

陳 宏

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

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

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

1 主菜單設(shè)計(jì)

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

2 線性表定義

功能：描述了線性表的定義和特點(diǎn)。

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

3 順序表

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

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

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

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

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

算法：

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

（2）繪圖算法

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

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

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

算法：

（1）順序表的刪除算法

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

（2）繪圖算法

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

4 單鏈表

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

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

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

2）單鏈表插入操作演示

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

算法描述：

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

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

3）單鏈表刪除操作演示

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

算法：

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

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

基于VC的線性表動(dòng)態(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ā)技巧及實(shí)例剖析[M].北京：清華大學(xué)出版社，1999，2：130.