1.1.1. 引言¶

在得克萨斯州达拉斯市 500 英里范围内，有多少人口超过 25 万的 城市？ 我的公司里有多少人年薪超过 10 万美元？ 我们能否用不到 1000 英里的电缆连接所有电话客户？ 要回答这类问题，仅仅拥有必要的信息是不够的。 我们必须以某种方式组织这些信息，使我们能够及时找到答案以满足 需求。

信息的表示是计算机科学的基础。 大多数计算机程序的首要目的不是执行计算，而是存储和检索信息—通常要越快越好。 因此，研究数据结构以及操作它们的算法，正处于计算机科学的 核心。 这也正是本书的主题—帮助你理解如何组织信息以支持高效的 处理。

任何数据结构与算法课程都会试图教你三件事：

1. 介绍一组常用的数据结构和算法。 它们构成程序员的基本"工具箱"。 对许多问题而言，工具箱中的某个数据结构或算法就能提供良好 的解法。 我们关注的是那些经过时间检验、被证明最有用的数据结构和 算法。

2. 引入权衡（tradeoff）的思想，强化"每种数据结构或算法都有 代价和收益"的概念。 做法是：对每种数据结构，描述其典型操作所需的空间和时间。 对每个算法，我们考察关键输入类型所需的时间。

3. 教你如何度量数据结构或算法的有效性。 只有通过这种度量，你才能判断工具箱中哪个数据结构最适合 新问题。 这里介绍的技术也能让你评价你或他人可能发明的新数据结构的 优劣。

解决一个问题的方法往往不止一种。 我们如何在它们之间选择？ 计算机程序设计的核心是两个（有时相互冲突的）目标：

1. 设计易于理解、编码和调试的算法。

2. 设计能高效利用计算机资源的算法。

理想情况下，最终程序对两个目标都成立。 我们可以说这样的程序"优雅"。 本书给出的算法和程序代码示例力求在这种意义上优雅，但本书的 目的并不是明确处理与目标 (1) 相关的问题。 那主要是软件工程学科的关切。 我们主要聚焦于与目标 (2) 相关的问题。

如何度量效率？ 我们评价算法或计算机程序效率的方法称为 渐近分析。 渐近分析还提供了一种定义问题固有难度的方法。 全书将用渐近分析技术估计书中给出的每个算法的时间代价。 这让你能看到，就效率而言，每个算法与解同一问题的其他算法 相比处于什么位置。

1.1.2. 数据结构的哲学¶

你也许会想：随着计算机越来越强大，程序效率正变得不那么 重要。 毕竟，处理器速度和内存容量仍在持续提升。 今天的效率问题难道不会被明天的硬件解决吗？

随着我们开发出更强大的计算机，迄今为止的历史一直是：我们用 新增的计算能力去应对更复杂的问题，无论是更复杂的用户界面、 更大的问题规模，还是以前被认为计算上不可行的新问题。 更复杂的问题需要更多计算，这使得对高效程序的需求更甚。 不幸的是，任务越复杂，就越不像我们的日常经验。 因此，今天的计算机科学家必须接受训练，透彻理解高效程序设计 背后的原则，因为在设计计算机程序时，他们的日常生活经验往往 并不适用。

在最一般的意义上， 数据结构 是任何数据表示及其相关操作。即使是存储在计算机上的整数或浮点数也可以被视为一种简单的数据结构。更常见的是，人们使用术语“数据结构”来指代数据项集合的组织或结构化方式。存储在数组中的已排序整数列表就是这种结构化的一个例子。这些概念将在关于 Abstract Data Types 的讨论中进一步探讨。

只要有足够的空间存储一组 数据项， 就总是可以在集合中查找指定项、按任意期望的顺序打印或以 其他方式处理数据项，或修改任何特定数据项的值。 最直观的例子是包含全部数据项的无序数组。 对无序数组可以执行所有必要的操作。 然而，选用合适的数据结构，可能决定了一个程序是几秒钟跑完 还是需要好几天。 例如，在 散列表 中查找给定记录比在无序数组中 查找快得多。

如果一个解法能在要求的 资源约束 之内 解决问题，就称它是 高效 的。 资源约束的例子包括：可用于存储数据的总空间—可能分成 主存和磁盘两类约束—，以及完成每个子任务所允许的时间。 有时，只要一个解法比已知的替代方案消耗更少资源，无论是否 满足任何特定要求，也称它是高效的。 一个解法的 成本 是它消耗的资源量。 大多数情况下，代价以某一种关键资源（如时间）来度量，隐含 假定解法满足其他资源约束。

1.1.3. 选择数据结构¶

不言而喻，人们写程序是为了解决问题。 然而，程序员有时会忘记这一点。 所以，在选择解决特定 问题 的 data structure 时，牢记这条常识至关重要。 只有先分析问题、确定必须达到的性能目标，才有希望为这项工作 选出正确的数据结构。 糟糕的程序设计者跳过这一分析步骤，套用自己熟悉但并不适合 该问题的数据结构。 结果通常是一个缓慢的程序。 反过来，如果一个程序用更简单的设计实现就能满足性能目标， 那么为了"改进"它而采用复杂的表示毫无意义。

为解决问题选择数据结构时，应当遵循以下步骤。

1. 分析你的问题，确定必须支持的 基本操作。 基本操作的例子包括：向数据结构插入一个数据项、从数据 结构删除一个数据项、查找指定的数据项。

2. 量化每种操作的资源约束。

3. 选择最能满足这些要求的数据结构。

这种三步选型方法把以数据为中心的设计观落到了实处。 首先关心的是数据以及要对数据执行的操作，其次关心这些数据 的表示，最后关心该表示的实现。

某些关键操作（如查找、插入数据记录、删除数据记录）的资源 约束通常主导数据结构的选型过程。 以下三个问题涉及这些操作相对重要性的诸多方面，每当你必须 选择数据结构时，都应当问问自己。

1. 所有数据项是在一开始就全部插入，还是插入与其他操作 交错进行？ 静态应用（数据在开始时装入且从不改变）通常用较简单的 数据结构就能高效实现，而动态应用往往需要更复杂的东西。

2. 数据项可以被删除吗？ 如果可以，实现多半会更复杂。

3. 所有数据项是否都按某种明确定义的顺序处理，还是允许查找 特定数据项？ "随机访问"式查找通常需要更复杂的数据结构。

每种数据结构都有相应的代价和收益。 实践中，一种数据结构在所有情形下都优于另一种的情况几乎 不存在。 如果一种数据结构或算法在所有方面都优于另一种，逊色的那种 通常早就被遗忘了。 本书介绍的几乎每种数据结构和算法，你都会看到它是最佳选择 的例子。 其中一些例子可能出人意料。

数据结构需要为每个存储的数据项占用一定的空间，执行单个基本操作需要一定的时间，并需要一定的编程工作量。每个问题都对可用空间和时间存在约束。问题的每个解决方案都会以某种相对比例使用基本操作，而数据结构的选择过程必须考虑这一点。只有仔细分析问题的特征后，才能确定最适合该任务的数据结构。

1.1.4. 引言小结题¶