为什么会有“数据结构”？

近一年来，由于参与一套高中信息科技教材的编写，回过头来思考了一些关于算法和数据结构的认识问题，其中就包括本文的标题。

记得40年前上大学的时候，上郭福顺老师教的数据结构课，对“数据结构”这个术语是感到完全新奇的。因为“数据结构”不像“高等数学”，至少以前还听说过“数学”，于是“高等数学”也就不陌生（尽管其内容和原来知道的数学很不一样）。由此我联想到，在给中学生介绍数据结构相关知识的时候，是不是首先得回答一下“为什么会有‘数据结构’”这个问题，说说“数据结构”这样一个概念在计算机科学中的意义。

为此，首先翻书，国内的国外的，在相关的资料遍历之后发现，不少作者也都感觉需要在一开始就谈谈“数据结构”的重要性，于是常常会有几句相关的话放在绪论甚至前言中。概括起来大致有这样几种情况。其一，不回答为什么会有“数据结构”，只是讲“数据结构”作为一门课程在计算机专业课程中的基础地位；其二，引用Niklaus Wirth的经典观点：程序=算法+数据结构，佐证学习“数据结构”概念的重要性；其三，一开始只是讲“什么是数据结构”，而让对“为什么会有‘数据结构’”的认识隐含在其中。例如，维基百科上关于“Data Structure”的描述就是后者的一个代表：

In computer science, a data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

翻译过来就是：

计算机科学中的数据结构，是数据组织、管理和存储的形态，以支持对数据的高效访问和修改。更准确地讲，一个数据结构是由若干数据、它们之间的关系，以及能在其上施行的操作构成的一个集合。

其中的“以支持对数据的高效访问和修改”应该就是关于数据结构的目的性或意义的隐含了。这段话一句句读来应该找不出错。我的看法在于它描绘了一种“重心”偏离的意境，容易对回答“为什么会有‘数据结构’？”这样的问题产生误导，所以愿在此和有兴趣的同仁商榷。

首先，关键问题是这里提到的“数据”指的是什么？是计算机应用层的数据还是计算机程序在运行时“看到的”任何0或1串？我认为大多数人的理解会是前者（在一些教材的描述中明显是这个意思），尤其对刚开始接触计算机科学知识的人更是如此（恰恰是他们应该作为这些描述的读者对象！）。于是，这里给出的画面就是，数据结构就是将计算机应用数据按照某种方式组织起来的结构，以便对它们进行高效处理。

需不需要这么做？当然需要，但我以为那不是“数据结构”的主要意义。

尽管数据结构的采用在许多情况下就是应用数据的一种组织，例如工程计算中用的数组，每个元素就对应一个现实中的物理量；社会网络分析中的图，每一个节点就对应一个人的有关属性参数。但在我看来，计算机程序用数据结构，本质上是为了支持算法逻辑，而不是应用层数据的组织。常常，一个数据结构的采用与应用层数据并没有直接的关系，而是旨在对计算过程的有效引导。

稍微考虑一下就能想到许多例子。例如为了实现广度优先搜索，典型做法是用一个队列（一种数据结构）来控制搜索的过程，而不是把被搜索的数据组织成队列结构；再例如二叉树的采用，常常就是因为算法逻辑的需要，树中非叶节点包含的，就不是输入的应用层数据，而是程序运行中产生的中间数据或控制数据。也许我们可以说，数据结构更多地是为了“控制”，而不是为了“数据”。为了“提高效率”没错，但要认识到既包括执行效率，也包括编程效率。

因此，显式或隐含强调数据结构是应用问题数据的组织形态，在我看来，是学理重心的偏离。如果要强调数据，则应该指明是程序“看见的”、编程人员体会得到的数据含义会更有教益。那样的数据除了程序的输入数据外，还包含中间结果数据和控制数据。

简言之，在数据结构课程（和教材）中，我们应该开宗明义地讲数据结构是为算法逻辑服务的（而不讲是应用数据之间关系的表达），从而让学生从一开始就试图体会、并在后续学习过程中不断磨砺一种更有价值的观念，这种磨砺包括认识到是计算机存储器线性编址的简单性，与程序逻辑的复杂性之间的鸿沟，导致了数据结构的必要性，等等。我想，这也是对Niklaus Wirth的“程序=算法+数据结构”的一种恰当解释。

* 注：此文发表在《计算机教育》2019.1