抽象数据类型视角下的《数据结构》教学

作者简介: 谢勰(新浪微博: @算海无涯-X), 著有《面向算法设计的数据结构(C++语言版)》(这本书正是基于抽象数据类型视角进行数据结构教学的新产品, 欢迎尝鲜♥♥♥), 致力于推广高效使用标准模板库(STL)简洁明快地解决算法问题, 现为西安邮电大学副教授. GitHub: https://github.com/xiexiexx/.

本文根据《重新审视数据结构》(之前发表在《计算机教育》上)、《面向算法设计的数据结构(C++语言版)》前言和近期微博文字合并而来. 感谢 www.52cs.org 邀请发文, 我根据当前发展对旧有文字进行了修改更新.

=================================================================

提起数据结构, 大多数人都认为它是一门基础性课程. 从某种角度看, 数据结构有点像高等数学, 一是二者内容大多早已成熟, 二是它们都积累了大量习题可供学生练习. 这样一来, 应试倾向的数据结构课程应运而生, 无论是在教学和学习中, 这种倾向性都非常明显. 比如在链表这部分内容的讲授中, 教师一般会给出各种不同的链表变种作为习题: 单向/双向、不带头结点/带头结点、非循环/循环等等. 又比如在讨论二叉树遍历时, 学生要花费大量精力去学习各种遍历的非递归形式. 当然, 学习这些内容虽然提高了逻辑思维能力, 但学习数据结构的目的是为程序设计、更是为算法设计而服务, 因此其重点应放在如何挑选或设计合适的数据结构, 而不是把大量精力花在这些不太实用的细节问题上.

另一方面, 数据结构还有许多值得研究的问题. 许多数据结构不但性能优越, 而且构造精巧, 不逊于任何一件艺术品, 比如不相交集、二项堆和Fibonacci堆. 而发展成熟的数据结构很快便可应用于工业界, 如STL中的vector容器, 又如红黑树实现的set容器. 研究人员不但需要设计新的数据结构以榨取其性能, 并且还要对它们进行细致的分析以了解其性能极限（即下界问题）. 此外, 目前有若干专门的学术会议致力于数据结构的设计与分析, 如交替举办的WADS会议(Algorithms and Data Structures Symposium, 以前名为The Workshop on Algorithms and Data Structures)和SWAT会议(The Scandinavian Workshop on Algorithm Theory). 第一次WADS是1989年举办, 距今已经快有三十年历史, 这充分说明了数据结构这个经典的主题依然有着蓬勃的生命力.

因此, 在数据结构的教学过程中, 我们需要将重心放在学习到如何使用和挑选数据结构, 对于要求较高的同学可考虑深入了解数据结构的设计与分析.

范文澜曾云“板凳要坐十年冷”, Peter Norvig也写过一篇异曲同工的Teach Yourself Programming in Ten Years妙文. 尽管一般人不可能用十年去培养非常专业的功底, 但我们希望在有限的课程时间内培养出学生的基本技能, 并为他们打开程序设计这扇神奇之窗. 那么如何尽快学会搭建程序呢? 乐高积木为我们提供了一种很好的思路, 学生只需使用基本的“积木式”组件便可迅速完成程序设计. 抽象数据类型正是这样的积木, 以C++语言为例, 标准模板库(STL)已为我们准备好了, 其他语言也有相应的库. 在学会组建程序的基础上, 我们要求从算法角度分析效率, 而抽象数据类型的简约性更利于我们在宏观上尽快给出优良的方案设计. 因此, 我们将数据结构课程教学的主线定为抽象数据类型的选择、使用和组合. 我们特别强调在抽象数据类型选用时必须以算法分析为导向, 以算法效率为准绳. 对于以不同抽象数据类型为要素的实现方案, 其选择标准是完成整个方案所需的时空开销. 此外, 我们还会关注同一抽象数据类型在不同数据结构实现下的性能差异. 只有这样, 学生才能尽快学会高效使用抽象数据类型, 最终为后续的算法设计课程打下坚实的基础.

我们应该掌握哪些抽象数据类型呢? Robert E. Tarjan在其名作《数据结构与网络算法》（Data structures and network algorithms)中给出了非常精辟的总结:

1. 区间: 包括数组/向量, 其特点是以O(1)时间访问元素. 注意区间的下标可以双向延伸, 也即这里可能存在负数下标.
2. 列表: 包含链、栈和队列. 这三种看似简单的抽象数据类型在图算法中的应用可谓是精彩纷呈.
3. 集合: 不一定有序关系, 以查找为主, 可用散列实现. 《算法导论》上称此为字典.
4. 映射: 定义于全序集, 有最小和最大元素, 可用查找树实现. 此外映射还可引出优先级队列.

=================================================================