1.1 什么是数据结构

1.1.1 基本概念

（1）数据：信息的载体，是客观事物的符号表示。数据能够被计算机识别、存取和处理，数据也是计算机程序加工和处理的“原料”。例如，实数、字符串、图像和声音等。

（2）数据项：具有独立含义的最小标识单位。例如，字段、域、属性等。

（3）数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。

（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例如，26个英文字母构成的字符集合，一个学校全体学生或教师构成的学生集合或教师集合等。

（5）数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构的形式化定义通常用一个二元组Data_Structure=(D, R)来表示，式中，D是数据元素的有限集（也即数据对象），R是D上关系的有限集。

1.1.2 数据结构的内涵

数据结构一般包含数据的逻辑结构和存储结构及数据运算。数据结构的研究内容包括两方面：一方面是抽象地研究数据集合的结构（抽象数据结构）特点；另一方面是研究如何把抽象数据结构转化为存储组织形式（数据的存储结构）。这两方面的研究既可独立于各个领域的应用来研究，也可结合具体应用领域中的特点来进行研究。例如，专门研究计算机图像识别或定理证明中的数据结构。目前，从抽象数据类型的观点来讨论数据结构已经成为一种新的趋势，并越来越被人们所重视。

1.数据的逻辑结构

数据的逻辑结构是指数据元素以及它们相互之间的逻辑关系，数据的逻辑结构与数据的存储无关。根据数据元素之间关系的不同特性，通常有4 类逻辑结构：① 集合，集合的逻辑结构中所有数据元素都属于同一个集合，所有数据元素杂乱无章地聚集在一起，各个数据元素之间无任何联系；② 线性结构，逻辑结构中的数据元素之间存在着一个对一个的关系，各个数据元素之间通常有严格的先后次序关系；③ 树形结构，逻辑结构中的数据元素之间存在着一个对多个的关系，各个数据元素之间通常有严格的层次关系；④ 图状结构，逻辑结构中的数据元素之间存在着多个对多个的关系，各个数据元素之间均可能存在相互联系。

在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。除了上述4 类逻辑结构之外，根据数据元素（结点）之间的前后相邻关系，数据的逻辑结构还可分为线性结构和非线性结构两大类：① 线性结构的逻辑特征是，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并所有结点都最多只有一个直接前驱结点和一个直接后继结点。线性表是一个典型的线性结构，栈、队列和串等都是线性结构；② 非线性结构的逻辑特征是，一个结点可能有多个直接前驱和直接后继。树和图都是非线性结构。

【例1-1】 怎样描述数据的逻辑结构？

对数据元素之间关系的描述是数据的逻辑结构，它可形式地用一个二元组表示为K=(D, R)，式中，D是由有限个结点所构成的集合，R是由有限个关系所构成的集合。有时为了直观起见，也用以图示法来表示数据的逻辑结构。逻辑结构与使用的计算机无关。例如，一批数据的逻辑结构K=(D, R)，式中，D={d1, d2, …, d9}，R={<d1, d2>,<d1, d3>,<d1, d4>,<d1, d7>,<d1, d8>,<d4, d5>,<d4, d6>,<d8, d9>}，则该批数据的逻辑结构如图1.1所示。对于R中包含有多种关系的情况，也可用类似的方法描述。

2.数据的存储结构

数据的存储结构（物理结构）是指数据在计算机中的存储表示，它包括数据元素的表示和关系的表示。数据的存储结构有以下4种基本存储方法。

① 顺序存储。该存储方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（sequential storage structure）。该方法通常借助于高级程序语言中的数组来描述，且主要应用于线性的数据结构。非线性的数据结构也可通过线性化的方法来实现顺序存储。

② 链接存储。该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（linked storage structure），通常借助于高级程序语言的指针类型来描述。

③ 索引存储。该方法通常在存储结点信息的同时，还要建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（dense index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引（spare index）。索引项的形式一般是（关键字，地址），关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置，稀疏索引中索引项的地址指示一组结点的起始存储位置。

④ 散列存储。该方法根据结点的关键字直接计算出该结点的存储地址。

以上述4 种基本存储方法既可单独使用，也可组合起来对数据结构进行存储映射。同一种逻辑结构采用不同的存储方法，可得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，要视具体的应用要求而定，主要考虑运算方便和算法的时空效率要求。

3.数据的运算

数据的运算是对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。在数据结构中，运算不仅仅是加、减、乘、除等运算，大多数的运算都涉及算法的实现问题，算法的实现与数据的存储结构是密切相关的。

1.1.3 数据类型和抽象数据类型

数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称，通常它可看作是高级程序设计语言中已经实现的数据结构。例如，C语言中的整型变量，其值的集合为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等算术运算。按“值”的不同特性，在高级程序语言中可分为：① 原子类型，其值不可分解，例如，C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型；② 结构类型，其值是由若干个成分按某种结构组成的，故可分解，其成分可以是非结构的，也可以是结构的，例如，数组的值由若干分量组成，每个分量可能是整数，或者是数组。

抽象数据类型（abstract data type，ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，也即，不论其内部结构如何变化，只要它的数学特性不变，都不会影响其外部的使用。抽象数据类型可表示为一个三元组（D, R, P），式中，D是数据对象，R是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象数据类型：

ADT抽象数据类型名{ 数据集合：<数据对象的定义>

数据关系：<数据关系的定义>

数据操作：<数据操作的定义>

} ADT抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：

数据操作名（参数表）

输入：<输入条件描述>

输出：<输出结果描述>

【例1-2】 抽象数据类型（ADT）的定义、特点、实现与数据结构的区别是什么？

ADT是高级程序设计语言中数据类型概念的推广，它是一个数学模型和定义在该模型上操作集合的总称。ADT的实现方法是，将ADT转换成现有高级程序设计语言的说明语句，加上对应于该ADT中每个操作的过程或函数，也即，用现有高级程序设计语言能够支持的适当数据结构来表示ADT中的数学模型，并用一组过程或函数来实现定义在该模型上的各个操作。数据结构则是利用该语言的基本数据类型和复合数据的构造机制来构成的。例如，数组和记录就是C++语言中两种主要的复合数据的构造机制。根据ADT定义，如果在相同的数学模型上定义两个不同的操作集，则认为它们代表两个不同的抽象数据类型。故相同的数学模型以及在其上所定义的操作有可能在不同的ADT中出现。