1.1　数据结构

首先，我们需要使用一种统一的方式来描述并评估算法。

一种非常标准的描述方式如下：算法会根据所接收的输入以及所提供的输出进行描述。算法的具体细节可以用伪代码（忽略编程语言的实现细节）或者实际代码加以说明。

数据结构虽然与算法类似，但稍有不同，因为在其中还必须描述对数据结构所能执行的操作。通常来说，每个操作都会像算法那样，通过输入和输出进行描述。除此之外，对于数据结构来说，这些操作的副作用也需要描述，因为这些操作可能会对数据结构本身进行修改。

要彻底了解为什么会有副作用产生，你首先需要正确地对数据结构进行定义。

1.1.1　定义数据结构

数据结构（data structure）是一种对数据进行组织的特定解决方案，不仅可以为元素提供存储空间，还提供了存放和获取这些元素的功能[1]。

[1]　具体来说，至少会有一个将新元素添加到数据结构的方法，以及另一个可以获取特定元素或者查询数据结构的方法。

最简单的数据结构就是数组。比如，字符数组可以为有限数量的字符提供存储空间，并且提供了根据位置来获取字符数组中各个字符的方法。图1.1展示了array = ['C', 'A', 'R']是如何存储的。对于存放了字符'C'、'A'和'R'的字符数组来说，array[1]对应的值就是'A'。

图1.1　数组的（简化的）内部表示。数组中的每个元素都对应着内存[2]中的一个字节。位于这些元素下方的是内存地址，位于其上方的则是对应的索引。数组是通过连续的内存块进行存储的，因此可以通过元素在数组里的索引并加上数组中第一个元素的偏移量来得到其地址。例如，数组中第4个字符（array[3]，图中为空）的地址就是0xFF00 + 3 = 0xFF03

[2]　在现代架构或编程语言中，数组元素可能会对应内存中的一个字（word）而不是一个字节（byte）。但是为了简便，这里假设字符数组被存放在一系列的字节中。

数据结构既可以是抽象的，也可以是具体的。

●　抽象数据类型（Abstract Data Type，ADT）会指定对某些数据可以执行的操作以及这些操作的计算复杂度，但不会提供有关如何存储数据或者如何使用物理内存的详细信息。

●　数据结构是基于抽象数据类型所提供的规范而得到的具体实现。

什么是抽象数据类型？

抽象数据类型可以理解为蓝图，而数据结构则会把其中的规范转换为真实代码。

抽象数据类型是从使用者的角度定义的，因此其行为会使用可能的值、可能的操作以及与这些操作对应的输出和副作用加以描述。

如果要更正式地来描述抽象数据类型，那么应该是“由一组类型、这组类型的指定类型、一组功能以及一组公理构成的合集”。

对于数据的具体表示——数据结构来说，数据结构则是从实现者而非使用者的角度描述的。

对于上面这个数组来说，一种可能的静态数组的抽象数据类型如下：“数组是一个可以存储固定数量元素的容器，其中的每个元素都有一个与之对应的索引（数组中元素的位置），可通过元素的位置来访问任何元素（随机访问）”。

要实现静态数组，还需要注意以下细节。

●　数组的大小在数组创建之后是固定不变的，还是可以修改的？

●　数组使用的内存是静态分配的，还是动态分配的？

●　数组只能包含单一类型的元素，还是可以包含多种类型的元素？

●　数组会实现为原始的内存块，还是实现为对象？如果实现为对象的话，数组会有哪些属性？

即使对于像数组这样的简单数据结构，不同的编程语言也会对上面的问题做出不同的选择。但是，所有的编程语言都会确保对数组的实现能够满足上面对数组的抽象数据类型所做的描述。

堆栈是另一个可以用来了解抽象数据类型和数据结构之间差异的好例子。我们将在附录C和附录D中对堆栈进行描述。当然，你应该听说过堆栈这种数据结构。

堆栈的抽象数据类型可以描述如下：“一个可以存储无限数量元素的容器，并且可以按照与插入顺序相反的顺序从最新的元素开始依次删除元素”。

进一步来讲，通过分解容器上可执行的操作可以得到堆栈的另一种描述：“堆栈是一个支持如下两种主要方法的容器”。

●　插入元素。

●　删除元素。如果堆栈不为空，那么最后插入的元素将从堆栈中被删除并返回。

尽管以上描述还是不那么通俗易懂，但是要比前一种描述更清晰，也更模块化。

这两种描述都足够抽象，也都具有一般性，足以让你在不同的编程语言、范式和系统[3]中实现堆栈。

[3]　原则上，系统并不是必须和计算机科学相关。例如，你可以把一堆需要检查的文件描述为系统。另外，洗一堆盘子这个经常在计算机科学课堂上见到的例子也可以视为一个系统。

不过在某些时候，我们还是得对数据结构进行具体的实现，这时就需要讨论下面这些细节了。

●　元素用什么方式来存储？

❏　数组？

❏　链表？

❏　磁盘上的B树？

●　如何记录插入的顺序？（与上一个问题相关）

●　堆栈的最大尺寸是已知并且保持不变的吗？

●　堆栈是否可以包含多种类型的元素，还是所有元素都必须属于同一类型？

●　如果想在空的堆栈上执行删除操作，应该怎么办？（例如，应该返回null还是抛出错误呢？）

诸如这样的问题数不胜数，这里列举的问题仅为让你有个大致的了解。

1.1.2　描述数据结构

定义抽象数据类型的关键在于列出其允许的一系列操作。这就相当于定义了一套API[4]，也可以说是与客户端的契约。

[4]　应用程序接口（Application Programming Interface）。

在需要对数据结构进行描述时，我们可以遵循一些简单的步骤，以确保提供的规范是全面且明确的。

●　指定数据结构的API ，并且确定方法的输入与输出。

●　描述数据结构的高阶行为。

●　详细描述具体实现的行为。

●　对数据结构的方法进行性能分析。

在本书中，我们都会先描述实际使用各种数据结构的具体情况，然后按照相同的流程来介绍它们。

在介绍第一种数据结构时（见第2章开头），我们还会对API描述的约定作进一步的详细解释。

1.1.3　算法与数据结构有区别吗

算法和数据结构并不是同一件事。严格来说，它们并不是等效的。但是，我们通常在使用的时候会互换这两个术语。为了简便，后文我们会用数据结构这个术语来指代“数据结构及其所有相关的方法”。

有很多方法可以用来说明这两个术语之间的区别，但是笔者特别喜欢下面这个比喻：数据结构好比名词，而算法好比动词。

笔者之所以喜欢这个比喻，是因为这个比喻不仅表明了它们的不同行为，还暗示了它们之间的依赖性。例如，要在英语中构建一个有意义的短语，就需要同时包含名词和动词，还需要给出主语（或宾语）以及将要执行（或承受）的动作。

数据结构和算法是相互联系的，就好比一张纸的正反两面。

●　数据结构是基础，是一种通过组织内存区域来表示数据的方法。

●　算法是过程，是用来对数据进行转换的一系列指令。

如果没有用来对数据进行转换的算法，数据结构就只是存放在内存芯片里的一堆二进制数；而如果没有可以操作的数据结构，则大多数算法甚至不会出现。

除此之外，每种数据结构还隐式地定义了其中可以执行的算法。例如，用来向数据结构中添加元素的方法以及从中获取或删除元素的方法。

实际上，一些数据结构的定义就是为了能让某些算法更高效地运行而出现的，例如哈希表以及按键进行搜索的算法[5]。

[5]　你可以在附录C里找到有关这个主题的更多信息。

因此，我们可以把算法和数据结构当作同义词来使用，毕竟在这个上下文中提到其中一个时总会暗示另一个。例如，在描述数据结构时，如果要让描述是有意义且准确的，就必须同时描述数据结构的方法（算法）。

上一章目录下一章