“软件技术基础”中数据结构教学方法研究

郭秀清

(同济大学电子与信息工程学院，上海201804)

“软件技术基础”是我校电气类公共平台课程面向非计算机专业本科生。课程的内容包括算法、数据结构、操作系统、数据库技术及软件工程等，其中数据结构是该课程的重要组成部分。学习数据结构的目标是使学生了解计算机处理数据的结构特性，为应用涉及的数据设计合理的逻辑结构、存储结构及其相应算法，并能对算法的时间和空间复杂度作定量估算。由于数据结构具有逻辑结构和物理存储结构两重属性，导致其基本运算种类和形式繁多。

笔者基于对“软件技术基础”课程教学方法的探索和教学经验的积累，针对数据结构及其运算的教学内容，提出了一种简单有效的教学方法。其核心是教学四步骤和基于典型案例的算法执行法。

1 数据结构与算法的关系

数据结构和算法这两个知识点关系紧密，互相依存。但限于课时，在“软件技术基础”教学过程中，通常不单独讲算法，而是把算法贯穿于数据结构的运算中。借助不同数据结构的不同运算介绍算法的特性(如能行性、确定性和有穷性等)、设计方法(如列举法、递归法和回溯法等)及其评估方法(包括时间和空间复杂度评估)等，同时也介绍了算法描述语言，即伪码。

2 四步骤教学方法

2.1 数据结构分类

数据逻辑结构(简称数据结构)是指相互有关联的数据元素的集合。数据结构的分类方法有很多。本文基于集合中元素之间的关联关系，把数据结构分成四类:集合、线性结构、树结构和图结构。

所谓集合是指数据元素之间除了同属于一个集合的关系外，再没有其它关系。比如街上许多行人组成的人群为一集合。线性结构是指集合中数据元素之间存在一对一(记作1:1)的关系。如班长和班级，假定一个班级只有一个班长，且一个人只能担任一个班级的班长。树结构是指集合中数据元素之间存在一对多(记作1:n)的关系。如父母和孩子，一对父母可以拥有多个孩子，但任何一个孩子只有唯一的父母。图结构是指集合中数据元素之间存在多对多(记作n:m)的关系。如教师和学生，教师可给多名学生上课，而学生也可选修多名教师的课。

可见，数据结构包含两个要素:①数据元素的信息;②数据元素之间的前后件关系。即指数据集合中相邻两个元素存在的关系。

2.2 数据的存储结构

数据的存储结构是研究集合中数据元素在计算机的物理空间中存储方式，是数据逻辑结构在计算机中的映像，即实现。常用的存储结构有顺序存储和链式存储两种，其中顺序存储是指用一组地址连续的存储单元依次存放集合中的数据元素。其特点是逻辑关系上相邻的两个元素在物理存储位置上也相邻，它的优点是随机存取，缺点是对于某些操作需要移动大量元素，如插入和删除操作。链式存储结构是指用一组任意的存储单元(这组存储单元不要求连续)存放集合中的数据元素。其特点是逻辑关系上相邻的两个元素在物理存储位置上不一定相邻，且数据元素之间的前后件关系在逻辑结构和存储结构上可能不一致，即可能存在前件元素的存储单元地址大，后件元素的存储单元地址小这种情况。其缺点是不能随机存取，只能顺序存取。也正因为不能随机存取，链式存储克服了顺序存储的缺点，即插入和删除操作时不需要移动大量元素，改善了时间复杂度指标T(n)。

2.3 数据结构的常用运算

计算机对数据的操作(运算)主要有访问和更新两类，访问即查找集合中某元素或遍历集合中所有元素，更新包括插入、删除和修改，通常简称增、删和改。其中插入、删除和遍历是最常用的操作，几乎涉及各种数据结构的各种存储结构。如二叉树遍历、图的遍历、顺序表和链表的插入及删除运算、顺序栈和链栈的入栈及出栈、顺序队和链队的入队及出队、二叉排序树的生成和删除二叉排序树的结点以及哈夫曼树的构造等。

2.4 四步骤教学方法

本文提出一种数据结构教学方法，称为四步骤教学法。该教学法贯穿于所有常用数据结构及其运算(操作)的教学过程中，易于操作，行之有效。

(1)数据结构和存储结构

每一种数据结构的教学始于它的逻辑结构和存储结构，先介绍数据的逻辑结构，即二元组定义，在此基础上学习其存储结构。这样得出如顺序表、链表、顺序栈和链栈等。

如问题描述为一元多项式相加，多项式在逻辑上可以用线性结构描述，因多项式相加会改变多项式系数和指数，且可能存在多项式的次数很高但又有大量零系数项，所以采用链式存储结构。只有当计算机要处理数据的逻辑结构和存储结构确定后，才可以设计相应的算法。

(2)算法思想

算法是解决某一特定类型问题的有限运算序列。如背包问题、最佳判定问题和旅行商问题等。在已知问题描述后，学习或设计算法的难点和重点是首先学习或设计其运算规则(即算法思想)。具体的算法是其运算规则的体现和实现，只要有相应的语言基础，阅读或编写算法代码并不困难。因此，教学过程中应将重点放在算法思想上。如表达式求值、皇后问题和哈夫曼树构造等算法思想。

(3)基于案例执行法

在掌握算法思想的基础上，学习算法或检查自己编写的算法的行之有效的方法是基于典型案例执行算法。所谓典型案例需精心设计和选择，可借鉴软件测试中的用例设计。典型案例要满足两个条件:①简单—是指案例执行时间短;②覆盖面广—指案例能覆盖算法的分支数多，最好一个案例能覆盖全部分支。符合这两个条件的案例是一个好的案例，因为执行这样的案例相当于遍历了一次算法，具有全覆盖且无重复特性。

(4)上机验证

数据结构的教学内容具有很强的实践性，学生只有通过自己动手将各种典型算法翻译成某种编程语言程序，并上机调试后，才能对该算法所涉及的数据的逻辑结构、存储结构及算法思想有深刻了解。

3 典型案例

本文介绍的案例驱动的“软件技术基础”教学方法，与笔者之前撰写的参考文献［1] 、［2] 的案例，无论从内涵还是外延上都有所不同。本文案例是指小案例，其外延是所有案例针对“软件技术基础”课程中数据结构这一知识点的。单一案例对应某个具体的算法，案例和算法之间的对应关系为多对一(大多数为一对一)关系，即一个案例服务于一个算法。文献［1] 、［2] 的案例是指大案例，其外延是“软件技术基础”课程的各个知识点，如数据结构、数据库和软件工程等。它适用于课程后期的应用设计和开发。如为解决某一领域工程问题，从需求分析开始，经过数据结构设计，数据库建立，直至应用程序设计和实现等全过程。所以，文献［1] 、［2] 的案例和知识点(而非算法)存在对应关系，且是一对多的关系，即一个大案例覆盖多个知识点。

3.1 案例设计

案例设计的任务是设计某一算法的典型输入，要求该输入具有全覆盖无重复特性，以实现遍历算法。限于篇幅，本文仅以一元多项式相加和二叉排序树结点删除两算法为例说明典型案例的设计方法。其他算法的案例在设计方法和要求上与此一样，目前笔者正在收集各种算法的典型案例设计工作，目标是构建一个案例库，供数据结构教学使用。

(1)一元多项式相加案例

问题描述:C(x)=A(x)+B(x)。A(x)和B(x)为两个一元多项式，C(x)为结果多项式。

算法思想:将A(x)和B(x)中指数相同的项对应系数相加，若和不为零，则构成C(x)中该指数的一项;A(x)和B(x)中所有指数不相同的项均复抄到C(x)中。

算法结构:依据上述算法思想设计的算法结构是典型的分支结构，局部流程图如图1所示。

典型案例:要求设计的案例遍历上述所有分支，且无重复。据此可使用下列案例:A(x)=1+2x+3x2+5x4，B(x)=2－2x+4x3－6x5+7x10。

(2)二叉排序树结点删除案例

问题描述:删除二叉排序树上一个结点，要求删除一个结点后仍是一棵二叉排序树。

图1 多项式相加流程图局部

算法思想［3]:根据被删除结点在二叉排序树中的位置不同，算法规则分四种情形:①被删除结点是叶子结点，因删除后不会影响整棵二叉树的结构，故只要修改其双亲结点的指针;②被删除结点只有左子树或右子树，这时只要将其左子树或右子树作为它双亲结点的左或右子树(取决于被删除结点是其双亲结点的左孩子还是右孩子)即可;③被删除结点的左右子树均非空，这时要循着P(表示被删除结点)的左子树的根结点C，向右一直找到结点S，要求S的右子树为空。然后将S的左子树改为其双亲结点Q的右子树，把S的数据域值取代P的数据域值;④被删除结点为根结点，则删除后应修改根结点指针。

典型案例:为满足全覆盖无重复特性，图2可作为该算法的典型案例。同时，依据上述算法，被删除结点P对应地分别设定编号为11、13、10和5(被删除结点左右子树均非空的两种情形)及12结点。

图2 二叉排序树结点删除典型案例

3.2 案例库

本文提出的基于案例执行法是一种数据结构教学方法，其操作简单方便，该方法的有效性取决于案例。类似于软件测试中的用例设计，设计各种数据结构的各种运算的典型案例，然后经过合理组织和存放，形成案例库，供教学使用。正如前节案例设计中所述，这里的难点和重点是案例库中的案例要具有全覆盖且无重复特性。基于这样的案例执行算法就是遍历算法，执行时间短，效果好。

4 执行法

所谓基于案例执行法是指以典型案例作为某算法的输入，通过执行算法，学生可以理解算法思想(即运算规则)是如何实现的。如果设计或选择的案例足够典型，即具备全覆盖且无重复特性，则以这样的案例作为输入执行算法，相当于遍历一次算法(伪码描述或编程语言实现)，达到既节省算法执行时间(无重复)，又遍历了算法结构的所有分支(全覆盖)，充分且完整地体现了算法的设计思想。

算法执行方法可以分两种:①手工执行法;②机器辅助法。

手工执行法就是教师采用传统教学手段，在已知算法的输入(某典型案例)条件下，借助手写板书给出算法执行过程中输入经过怎样的状态转换、转换的步骤是什么以及最后的输出是什么等全过程。即用板书呈现输入中间状态1中间状态n输出的全过程。如算法实现使用了堆栈或/和队列，那么，执行过程中也要给出堆栈或/和队列的入栈或/和入队过程以及出栈或/和出队过程，如背包问题。

机器辅助法是指利用Flash工具呈现算法的执行过程，即算法输入的状态转换过程，以及堆栈或/和队列的操作过程等(如算法涉及)。这样省去了教师写板书的时间，提高了教学效率。目前，笔者正在设计和完善机器辅助法。

［1] 郭秀清.基于案例组织的软件技术基础教学方法研究［J] .南京:电气电子教学学报，2006，28(5):23～26.

［2] 郭秀清.软件技术基础教学方法研究［J] .北京:计算机教育，2008，14(7):128～132.

［3] 沈被娜等.计算机软件技术基础［M] .北京:清华大学出版社，2003.