“數據結構”的實踐性教學探討

摘要：《數據結構》是計算機科學與技術專業的一門重要的專業基礎課，課程具有極強的邏輯性、抽象性和實踐性。文章結合自身教學實踐對課程的實踐性教學進行了探討，從教與學兩方面，對數據結構的理論教學與實踐能力、實踐能力與程序設計能力的培養之間的關系進行了研究分析。對數據結構在游戲開發中的應用進行了分析，說明了應用性教學的重要性。

關鍵詞：數據結構；實踐性教學；程序設計能力

中圖分類號：G642文獻標識碼：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

《數據結構》是計算機科學與技術專業中的一門重要的綜合性專業基礎課，它不僅是大學計算機專業的核心課程之一，也是非計算機專業的主要選修課程之一，主要任務是討論各種數據結構的邏輯結構，存儲結構及有關操作的算法。目的是使學生學會分析研究計算機加工的數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法，并初步了解對算法的時間分析和空間分析技術[1]。另一方面，通過對本課程算法設計和上機實踐的訓練，還應培養學生的數據抽象能力和程序設計的能力，進一步提高軟件設計水平。

1 理論教學與實踐教學并重

該課程涉及大量概念、模型及操作算法，理論性強，抽象，深奧。因此，在教學過程中有必要對課程結構及內容條理化、形象化，從而降低知識要點本身長的難度，使學生易于掌握，并激發學生學習的積極性；另一方面數據結構提供了許多算法，使學生在掌握知識的同時，可以提高其編程的能力，并能將理論知識真正轉變為自己的知識，提高自己的實際動手能力。因此對這門課的了解、理解、掌握和應用，將對一個人的編程能力有著極深的影響。

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

2 應用實例要推陳出新，突出新穎性、層次性

正因為各知識點應用面很廣，所以選擇應用實例要典型、新穎。例如，眾所周知的“走迷宮”這個經典的問題[1]，其核心問題是搜索算法，需用數組表示迷宮，用棧處理搜索問題，問題就可解決；對于棧的表示，可用順序存儲、單鏈式存儲、雙鏈存儲等多種形式；可進一步把迷宮用圖片表示、搜索過程可視化處理（如圖1），以及最優路徑的探求等；使問題更新穎，設計不同的難度層次要求更能激發學生探求問題的激情。

3 應用以培養軟件設計能力為目的

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

3.1 順序表

在可視化走迷宮中，我們已使用順序表來實現迷宮地圖。在RPG游戲地圖系統中[2]，主要使用數據結構中的順序表。例如，一個最簡單的磚塊地圖系統，視角為俯視90度，并由許多個順序連接的圖塊拼成，早期RPG的地圖系統大多是這樣。定義每個圖塊：

typedef struct TILE// 定義圖塊結構

{

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

……

} TILE;

當m_iPass=0，表示此圖塊不可通過，為1表示能通過。

如：TILEMapTile[10][5];

■

圖2 TILE地圖

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

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

通過順序表，可以表示更復雜的地圖，現在流行的整幅地圖中也要用到大量的順序表，在整幅中進行分塊[2]。

3.2 鏈表

鏈表在射擊游戲中有著廣泛的應用。例如在飛機游戲中，鏈表主要應用在發彈模塊上。首先，飛機的子彈頻繁地發射、消逝，其個數難以預料。利用鏈表靈活地插入、刪除操作的優點就可以方便地實現。

首先，定義位置坐標結構和子彈鏈表結點[3]。

typedef struct CPoint{//點坐標

int x，y;

} CPoint;

typedef struct BULLET

{

CPoint bulletpos;// 子彈的位置

int m_ispeed;// 子彈的速度

struct BULLET* next;// 指向下一個子彈

} BULLET;

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

class CMYPLANE

{

public:

void AddBullet();// 添加子彈

void RefreshBullet();// 刷新子彈

privated:

BULLET *st_LinkBullet;// 聲明飛機的子彈鏈表

};

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

3.3 棧和隊列

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

3.4 二叉樹

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

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

表1

■

分析主角生命值通常的特點，即預測出每種條件占總條件的百分比，將這些比值作為權值來構造最優二叉樹（哈夫曼樹），作為判定樹來設定算法。

表2

■

構造好的哈夫曼樹為圖3所示。對應算法如下：

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

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

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

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

else state=逃跑;

■

圖3 哈夫曼樹

3.5 圖

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

■

圖4 情節及其圖

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

代碼如下：

typedef struct MGRAPH

{

nt Vexs[MaxVex];// 頂點信息

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

……

} MGRAPH;

■

圖5 鄰接矩陣

各個情節之間有先后關系，但沒有被玩家發展的，用表1示。當情節被發展的話，就用表2示，比如，我們已經發展了遭遇強盜的情節，那么，C1與C2頂點之間的關系就可以用表2示，注意，并不表示C2已經發展，只是表示C2可以被發展了。

請看下面的代碼：

class CRelation{

public:

CRelation(char *filename);// 構造函數，將情節信息文件讀入到緩存中

void SetRelation(int ActionRelation);// 設定此情節已經發展

（下轉第110頁）

（上接第101頁）

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

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

……

privated:

char* buf;// 鄰接矩陣的內存緩沖

……

};

在這里，我們將表示情節先后關系的鄰接矩陣放到緩沖內，通過接口函數進行情節關系的修改，在BOOL SearchRelation(int ActionRelation)函數中，可以利用廣度優先搜索方法進行搜索。

4 結束語

“數據結構”的教學要堅持理論與實踐并重，理論教學要深入簡出，準確、系統；實踐教學要推陳出新，以新穎示例啟發學生的學習熱情。當然，新穎示例需要教師花費大量的精力去挖掘、開發，去了解市場對人才的需求。以需求促學習的教學方法，培養和提高所需的應用型人才的素質。

參考文獻：

[1] 嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京: 清華大學出版社，2005:1-20.

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

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

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

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