摘要：《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，課程具有極強(qiáng)的邏輯性、抽象性和實(shí)踐性。文章結(jié)合自身教學(xué)實(shí)踐對課程的實(shí)踐性教學(xué)進(jìn)行了探討，從教與學(xué)兩方面，對數(shù)據(jù)結(jié)構(gòu)的理論教學(xué)與實(shí)踐能力、實(shí)踐能力與程序設(shè)計(jì)能力的培養(yǎng)之間的關(guān)系進(jìn)行了研究分析。對數(shù)據(jù)結(jié)構(gòu)在游戲開發(fā)中的應(yīng)用進(jìn)行了分析，說明了應(yīng)用性教學(xué)的重要性。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；實(shí)踐性教學(xué)；程序設(shè)計(jì)能力

中圖分類號：G642文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)19-30099-03

The Research in Teaching for Data Structure Courses

YAN Yu-bao， XU Shou-kun， LI Ning

(Jiangsu Polytechnic University， Changzhou 213164， China)

Abstract: Data Structure is an important basic courses for profession of computer technology. It is much more logical， abstract and practical. The paper discusses courses for teaching of practice from author's teaching， and giving the relation between teaching of theory and ability of practice， ability of practice and ability of programming. For example， Data Structure's role in the game programming is discussed. So practice is very important in the teaching.

Key words: Data Structure; Teaching of practice; Ability of programming

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)中的一門重要的綜合性專業(yè)基礎(chǔ)課，它不僅是大學(xué)計(jì)算機(jī)專業(yè)的核心課程之一，也是非計(jì)算機(jī)專業(yè)的主要選修課程之一，主要任務(wù)是討論各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及有關(guān)操作的算法。目的是使學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時(shí)間分析和空間分析技術(shù)[1]。另一方面，通過對本課程算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力，進(jìn)一步提高軟件設(shè)計(jì)水平。

1 理論教學(xué)與實(shí)踐教學(xué)并重

該課程涉及大量概念、模型及操作算法，理論性強(qiáng)，抽象，深?yuàn)W。因此，在教學(xué)過程中有必要對課程結(jié)構(gòu)及內(nèi)容條理化、形象化，從而降低知識要點(diǎn)本身長的難度，使學(xué)生易于掌握，并激發(fā)學(xué)生學(xué)習(xí)的積極性；另一方面數(shù)據(jù)結(jié)構(gòu)提供了許多算法，使學(xué)生在掌握知識的同時(shí)，可以提高其編程的能力，并能將理論知識真正轉(zhuǎn)變?yōu)樽约旱闹R，提高自己的實(shí)際動(dòng)手能力。因此對這門課的了解、理解、掌握和應(yīng)用，將對一個(gè)人的編程能力有著極深的影響。

從多年的教學(xué)實(shí)踐來看，學(xué)生對數(shù)據(jù)結(jié)構(gòu)各知識點(diǎn)的理解、掌握難度不大，效果也比較好，使學(xué)生感到困難的是實(shí)際的應(yīng)用實(shí)踐。因此，在數(shù)據(jù)結(jié)構(gòu)的教學(xué)過程中，不能僅僅停留在結(jié)構(gòu)、算法等概念的理論教學(xué)上，必須加入大量的應(yīng)用實(shí)踐性的教學(xué)。各知識應(yīng)用本身是一個(gè)面很廣的問題，如何通過實(shí)際應(yīng)用來學(xué)習(xí)掌握數(shù)據(jù)結(jié)構(gòu)，提高學(xué)生軟件設(shè)計(jì)能力，在當(dāng)今教學(xué)中顯得十分重要。實(shí)際應(yīng)用不僅可以提高學(xué)生的積極性，而且可以讓學(xué)生懂得學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性。經(jīng)驗(yàn)證明，沒有堅(jiān)強(qiáng)的理論基礎(chǔ)，就沒有深刻地實(shí)踐活動(dòng)；沒有活潑的應(yīng)用實(shí)踐，就不會(huì)獲得滿意的教學(xué)效果。

2 應(yīng)用實(shí)例要推陳出新，突出新穎性、層次性

正因?yàn)楦髦R點(diǎn)應(yīng)用面很廣，所以選擇應(yīng)用實(shí)例要典型、新穎。例如，眾所周知的“走迷宮”這個(gè)經(jīng)典的問題[1]，其核心問題是搜索算法，需用數(shù)組表示迷宮，用棧處理搜索問題，問題就可解決；對于棧的表示，可用順序存儲(chǔ)、單鏈?zhǔn)酱鎯?chǔ)、雙鏈存儲(chǔ)等多種形式；可進(jìn)一步把迷宮用圖片表示、搜索過程可視化處理（如圖1），以及最優(yōu)路徑的探求等；使問題更新穎，設(shè)計(jì)不同的難度層次要求更能激發(fā)學(xué)生探求問題的激情。

3 應(yīng)用以培養(yǎng)軟件設(shè)計(jì)能力為目的

應(yīng)用的前提不僅要求學(xué)生具有用數(shù)據(jù)結(jié)構(gòu)表達(dá)問題的能力，而且要熟練一門計(jì)算機(jī)高級語言，如C/C++語言。這里也為學(xué)生提供了一個(gè)對學(xué)過的程序設(shè)計(jì)語言應(yīng)用的場所，是學(xué)生培養(yǎng)程序設(shè)計(jì)能力的一個(gè)良好時(shí)機(jī)。選擇好應(yīng)用實(shí)例十分重要，我認(rèn)為，圍繞簡單的游戲設(shè)計(jì)問題進(jìn)行應(yīng)用訓(xùn)練是行之有效的選擇，一方面，在游戲的編寫中應(yīng)用數(shù)據(jù)結(jié)構(gòu)的地方很多，有些簡單的游戲，只是由幾個(gè)數(shù)據(jù)結(jié)構(gòu)的組合；另一方面，在當(dāng)前動(dòng)漫游戲開發(fā)熱潮下，學(xué)生對游戲設(shè)計(jì)具有濃厚的興趣。因此，在教學(xué)中，以游戲開發(fā)設(shè)計(jì)的應(yīng)用問題為載體，把數(shù)據(jù)結(jié)構(gòu)各重要結(jié)構(gòu)、算法進(jìn)行應(yīng)用分析，會(huì)收到較好的教學(xué)效果。下面對順序表、鏈表、棧、隊(duì)列、二叉樹及圖等在游戲中的應(yīng)用進(jìn)行簡單分析。

3.1 順序表

在可視化走迷宮中，我們已使用順序表來實(shí)現(xiàn)迷宮地圖。在RPG游戲地圖系統(tǒng)中[2]，主要使用數(shù)據(jù)結(jié)構(gòu)中的順序表。例如，一個(gè)最簡單的磚塊地圖系統(tǒng)，視角為俯視90度，并由許多個(gè)順序連接的圖塊拼成，早期RPG的地圖系統(tǒng)大多是這樣。定義每個(gè)圖塊：

typedef struct TILE// 定義圖塊結(jié)構(gòu)

{

int m_iPass;// 表示此圖塊是否可以通過

……

} TILE;

當(dāng)m_iPass=0，表示此圖塊不可通過，為1表示能通過。

如：TILEMapTile[10][5];

■

圖2 TILE地圖

地圖結(jié)構(gòu)如圖2所示。從上圖看到這個(gè)地圖用順序表表示非常直接，當(dāng)我們控制人物在其中走動(dòng)時(shí)，把人物將要走到的下一個(gè)圖塊進(jìn)行判斷，看其是否能通過。比如，當(dāng)人物要走到(1，0)這個(gè)圖塊，我們用如下代碼判斷這個(gè)圖塊是否能通過：

int IsPass(x，y){return MapTile[x，y].m_iPass;}

通過順序表，可以表示更復(fù)雜的地圖，現(xiàn)在流行的整幅地圖中也要用到大量的順序表，在整幅中進(jìn)行分塊[2]。

3.2 鏈表

鏈表在射擊游戲中有著廣泛的應(yīng)用。例如在飛機(jī)游戲中，鏈表主要應(yīng)用在發(fā)彈模塊上。首先，飛機(jī)的子彈頻繁地發(fā)射、消逝，其個(gè)數(shù)難以預(yù)料。利用鏈表靈活地插入、刪除操作的優(yōu)點(diǎn)就可以方便地實(shí)現(xiàn)。

首先，定義位置坐標(biāo)結(jié)構(gòu)和子彈鏈表結(jié)點(diǎn)[3]。

typedef struct CPoint{//點(diǎn)坐標(biāo)

int x，y;

} CPoint;

typedef struct BULLET

{

CPoint bulletpos;// 子彈的位置

int m_ispeed;// 子彈的速度

struct BULLET* next;// 指向下一個(gè)子彈

} BULLET;

然后定義飛機(jī)類，在其中使用子彈。

class CMYPLANE

{

public:

void AddBullet();// 添加子彈

void RefreshBullet();// 刷新子彈

privated:

BULLET *st_LinkBullet;// 聲明飛機(jī)的子彈鏈表

};

在void AddBullet()中，將一個(gè)結(jié)點(diǎn)插入鏈表中，并且每隔一段時(shí)間加入，就會(huì)產(chǎn)生連續(xù)發(fā)彈的效果。函數(shù)void RefreshBullet()中，將鏈表歷遍一次就行，將子彈的各種數(shù)據(jù)更新。經(jīng)過上面的分析，在游戲中，鏈表主要應(yīng)用在有大規(guī)模刪除，添加的應(yīng)用上。不過，它也有相應(yīng)的缺點(diǎn)，就是查詢是順序查找，比較耗費(fèi)時(shí)間，并且存儲(chǔ)密度較小，對空間的需求較大。

3.3 棧和隊(duì)列

棧和隊(duì)列是兩種特殊的線性結(jié)構(gòu)，在游戲當(dāng)中，一般應(yīng)用在腳本引擎，搜索算法等之中。如在設(shè)置腳本文件的時(shí)候，通常會(huì)規(guī)定一些基本語法，這就需要一個(gè)解讀語法的編譯程序。如一個(gè)語法檢查函數(shù)，主要功能是檢查“()”是否配對，可以使用棧來設(shè)計(jì)（大多教材中有運(yùn)算符匹配的例子）。游戲中的AI搜索算法得到廣泛應(yīng)用，在此不再舉例。

3.4 二叉樹

樹的應(yīng)用極其廣泛，二叉樹是樹中的一個(gè)重要類型。如在描述分類過程和處理判定優(yōu)化等方面上的判定樹，在三維視景管理中的BSP樹[4]等，都是較好的應(yīng)用示例。

例如：設(shè)主角的生命值d，在省略其他條件后，有這樣的條件判定：當(dāng)怪物碰到主角后，怪物的反應(yīng)遵從以下規(guī)則：

表1

■

分析主角生命值通常的特點(diǎn)，即預(yù)測出每種條件占總條件的百分比，將這些比值作為權(quán)值來構(gòu)造最優(yōu)二叉樹（哈夫曼樹），作為判定樹來設(shè)定算法。

表2

■

構(gòu)造好的哈夫曼樹為圖3所示。對應(yīng)算法如下：

if(d>=20)(d<30) state=魔法;

else if(d>=30)(d<50) state=求助;

else if(d>=10)(d<20) state=戰(zhàn)斗;

else if(d<10) state=嘲笑;

else state=逃跑;

■

圖3 哈夫曼樹

3.5 圖

路徑搜索是圖的主要應(yīng)用中，應(yīng)用示例較多，特別是在AI游戲算法設(shè)計(jì)中都有著廣泛的應(yīng)用。在情節(jié)腳本中，可以用圖描述各個(gè)情節(jié)之間的關(guān)系，在這些分支情節(jié)之間，存在著一定的先決條件約束，即有些分支情節(jié)必須在其它分支情節(jié)完成后方可開始發(fā)展，而有些分支情節(jié)沒有這樣的約束?？梢杂糜邢驁D中AOV網(wǎng)來描述這些分支情節(jié)之間的先后關(guān)系。假如如下的情節(jié)：

■

圖4 情節(jié)及其圖

用鄰接矩陣表示此有向圖，將給出的情節(jié)表示成鄰接矩陣（圖5所示）。

代碼如下：

typedef struct MGRAPH

{

nt Vexs[MaxVex];// 頂點(diǎn)信息

int Arcs[MaxLen][MaxLen];// 鄰接矩陣

……

} MGRAPH;

■

圖5 鄰接矩陣

各個(gè)情節(jié)之間有先后關(guān)系，但沒有被玩家發(fā)展的，用表1示。當(dāng)情節(jié)被發(fā)展的話，就用表2示，比如，我們已經(jīng)發(fā)展了遭遇強(qiáng)盜的情節(jié)，那么，C1與C2頂點(diǎn)之間的關(guān)系就可以用表2示，注意，并不表示C2已經(jīng)發(fā)展，只是表示C2可以被發(fā)展了。

請看下面的代碼：

class CRelation{

public:

CRelation(char *filename);// 構(gòu)造函數(shù)，將情節(jié)信息文件讀入到緩存中

void SetRelation(int ActionRelation);// 設(shè)定此情節(jié)已經(jīng)發(fā)展

（下轉(zhuǎn)第110頁）

（上接第101頁）

BOOL SearchRelation(int ActionRelation);// 尋找此情節(jié)是否已發(fā)展

BOOL SaveBuf(char *filename);// 保存緩存到文件中

……

privated:

char* buf;// 鄰接矩陣的內(nèi)存緩沖

……

};

在這里，我們將表示情節(jié)先后關(guān)系的鄰接矩陣放到緩沖內(nèi)，通過接口函數(shù)進(jìn)行情節(jié)關(guān)系的修改，在BOOL SearchRelation(int ActionRelation)函數(shù)中，可以利用廣度優(yōu)先搜索方法進(jìn)行搜索。

4 結(jié)束語

“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)要堅(jiān)持理論與實(shí)踐并重，理論教學(xué)要深入簡出，準(zhǔn)確、系統(tǒng)；實(shí)踐教學(xué)要推陳出新，以新穎示例啟發(fā)學(xué)生的學(xué)習(xí)熱情。當(dāng)然，新穎示例需要教師花費(fèi)大量的精力去挖掘、開發(fā)，去了解市場對人才的需求。以需求促學(xué)習(xí)的教學(xué)方法，培養(yǎng)和提高所需的應(yīng)用型人才的素質(zhì)。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京: 清華大學(xué)出版社，2005:1-20.

[2] (美)Michael Morrison. 游戲編程入門[M]. 北京: 人民郵電出版社，2006:105-180.

[3] (美)David Conger. C++游戲開發(fā)[M]. 北京: 機(jī)械工業(yè)出版社，2006:23-68.

[4] (美)David Brackeen 著，邱仲潘 譯. JAVA游戲編程[M]. 北京: 科學(xué)出版社，2004:60-120.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文