“数据结构”的实践性教学探讨

摘要：《数据结构》是计算机科学与技术专业的一门重要的专业基础课，课程具有极强的逻辑性、抽象性和实践性。文章结合自身教学实践对课程的实践性教学进行了探讨，从教与学两方面，对数据结构的理论教学与实践能力、实践能力与程序设计能力的培养之间的关系进行了研究分析。对数据结构在游戏开发中的应用进行了分析，说明了应用性教学的重要性。

关键词：数据结构；实践性教学；程序设计能力

中图分类号：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

else if(d>=30)&&(d

else if(d>=10)&&(d

else if(d

else state=逃跑;

■

图3 哈夫曼树

3.5 图

路径搜索是图的主要应用中，应用示例较多，特别是在AI游戏算法设计中都有着广泛的应用。在情节脚本中，可以用图描述各个情节之间的关系，在这些分支情节之间，存在着一定的先决条件约束，即有些分支情节必须在其它分支情节完成后方可开始发展，而有些分支情节没有这样的约束。可以用有向图中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格式阅读原文