6.1 概述

6.1 概述

实际应用中所处理的数据经常是“大量同类型数据的集合”，例如一次物理实验获得的 大量实验数据、一篇文章中的所有单词、一幅画布上的所有图形等等，这几个例子分别展示 了大量数值的集合、大量字符串的集合和大量对象的集合。为了表示和处理大量数据，编程 语言提供了集合体数据类型，如 Python 中的列表（list）、元组（tuple）、字典（dict）、集合（set）和文件（file）等。 一个问题中的大量数据通常是“相关的”，即数据之间存在特定的逻辑联系。表示相关的大量数据时，必须将它们之间的逻辑联系也表示出来。在程序设计中，为了方便、高效地 处理大量相关数据，常将各数据按照某种合适的存储结构组织在一起，以便反映各数据之间 的逻辑联系。数据结构（data structure）是计算机科学的一个分支，专门研究如何将大量相 关数据按特定的逻辑结构组织起来，以及如何高效地处理这些数据。

下面以字符串数据为例来说明上面这段话的含义。夸张一点说，字符串数据——如 "HELLO"——也是复杂数据，因为它是由一些更简单的数据项（5 个字符"H"、"E"、"L"、 "L"和"O"）组成的。为了在程序中能够方便、高效地处理字符串"HELLO"，我们将这 5 个字符视为以“连续存储的序列结构”组织在一起，因为这种存储结构最恰当地反映了 5 个字符之间的逻辑关系，从而最有利于数据处理的实现。反之，如果将 5 个字符东一个西一个地分散存储，比如用几个独立的变量来分别存储这 5 个字符：

c1 = "H"
c2 = "E"
c3 = "L"
c4 = "L"
c5 = "O"

那么就没有表示出这 5 个字符的逻辑关系（即按特定次序组成的一个单词）。尽管这种存储 方式也实现了数据的存储，但它很难支持方便、高效的数据处理。例如，为了输出"HELLO"， 程序必须分别找到 c1 到 c5 这几个存储位置，并取出其中字符组合成输出，显然非常麻烦。 而在“连续存储的序列结构”方式下，程序只需找到一个存储位置即可。

存储数据的目的是为了将来处理数据，故存储结构一定要适应将来的数据处理。对字符 串数据而言，将相关的一组字符存储为一个连续序列就是合适的，因为这种序列结构非常适 合取字符、取子串、合并等字符串操作。因此，编程语言通常都以“连续存储序列”的逻辑 结构来组织多个字符组成的数据，并将字符串作为基本类型提供给程序员使用。这样，程序 员就不必再去费心考虑该用什么逻辑结构来组织多字符数据了。当然，字符串实在算不得复 杂数据，说它是简单数据也无不可，但以上讨论完全适用于真正复杂的数据。

总之，我们得到的教训是：如果不将组成复杂数据的大量数据项按照合适的逻辑关系组 织起来，那么就无法对复杂数据进行方便、高效的处理。换句话说，合适的数据结构往往是设计有效算法的关键。初学编程者通常以为算法才是程序设计的关键，其实不然。计算机科 学家 N. Wirth①提出过一个公式：算法 + 数据结构 ＝ 程序 这足以说明数据结构的重要性。

由于现实世界中构成复杂数据的逻辑关系多种多样，编程语言不可能对每一种逻辑结构 都像对字符串那样提供现成的数据类型和处理方法。另外，即使是同一个复杂数据，随着处 理需求的不同，也会导致采用不同的逻辑结构。因此，编程语言一般不会提供现成的数据结 构给我们使用，我们需要根据待解决的实际问题，自行设计复杂数据的数据结构。

本章介绍用于表示和处理大量数据的集合体数据类型和几种常用的数据结构。