何谓数据结构

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。

数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

数据结构主要研究什么？

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

什么是数据结构？什么是逻辑结构和物理结构？

数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：

DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)

这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D×...}，称之为元素的逻辑结构。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。

数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：

P:(D,S) --> M

存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。

P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。

因此，我们至少可以得到4×4种可能的物理数据结构：

（并不是所有的可能组合都合理）

数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。

DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为ADT。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的操作的子集。

对于DATs的高级操作可以被设计为（不封装的）算法，利用基本操作对DS进行处理。

好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。

树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。

表的性质

从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。

注意：表和数组的区别

从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构。关于抽象数据类型和数据结构的区别，请参见算法表达中的抽象机制。

从数学性质上来看，表是一个二元关系R，<x,y>∈R 当且仅当x是y的前驱；如果将该二元关系用关系图（将每一个元素用一个点来表示，若x与y有关系则从x到y连一条有向线段）来表示，则得到的是一条单链a₁→a₂→…→a_n ，因此表也可以看成是特殊的图或特殊的树（每个节点有且仅有一个子节点）；而数组是从1..n的自然数集合到数组元素集合的一一映射，其中n是数组的长度，1..n中每一个自然数唯一地对应着一个数组元素，反之亦然。所以数组可以用来实现映射。

从物理性质来看，数组中相邻的元素是连续地存储在内存中的，或者对于程序员来说可以认为它们是连续地存储在内存中的（比如动态增长的数组实际上并不存储在连续的内存中，但程序员可以认为它存储在连续的内存中），数组的存取对程序员来说是透明的；表只是一个抽象的数学结构，并不具有具体的物理形式，表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于表，只能根据当前元素找到其前驱或后继，因此要存取第i个位置上的元素，一般不能在一个操作内实现，除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通过对p进行处理（可能是从事某种函数运算计算出该元素在内存中的位置，也可能从表头开始，依次寻找当前元素的后继，重复i次找到第i个位置的元素）可以得到表中元素在内存中的物理位置，因此不能简单地将位置p理解为类似数组下标的自然数，实际上p可以是各种类型的变量，在数学上可将p定义为一个偏序集上的变量。在具体实现表及其运算时，应区分p与p所表示的位置，以及该位置上的元素三者之间的不同含义。

数据结构、数据类型和抽象数据类型

数据结构、数据类型和抽象数据类型，这三个术语在字面上既不同又相近，反映出它们在含义上既有区别又有联系。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。Pascal语言所定义的数据类型的种类如图1-8所示。

其中，简单数据类型对应于简单的数据结构;构造数据类型对应于复杂的数据结构;在复杂的数据结构里，允许成分数据本身具有复杂的数据结构，因而，构造数据类型允许复合嵌套;指针类型对应于数据结构中成分数据之间的关系，表面上属简单数据类型，实际上都指向复杂的成分数据即构造数据类型中的数据，因此这里没有把它划入简单数据类型，也没有划入构造数据类型，而单独划出一类。

数据结构反映数据内部的构成方式，它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。

由于指针数据的引入，使构造各种复杂的数据结构成为可能。按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。 由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。

最常用的数据结构是数组结构和记录结构。数组结构的特点是：

1. 成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。
2. 每一个成分数据具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。
3. 所有的成分数据被依序安排在一片连续的存储单元中。

概括起来，数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这种结构有这些良好的特性，所以最常被人们所采用。在高级语言中，与数组结构相对应的数据类型是数组类型，即数组结构的数据变量必须说明为array [i] of T₀ ，其中i是数组结构的下标类型，而T₀是数组结构的基类型。

记录结构是另一种常用的数据结构。它的特点是:

1. 与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。
2. 不同的域允许有不同的结构，因而允许属于不同的数据类型。
3. 与数组结构一样，它们可以随机访问，但访问的途径靠的是域名。

在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。