2.1　数据结构概述

数据结构是计算机中对数据的一种存储和组织方式，同时也泛指相互之间存在一种或多种特定关系的数据的集合。数据结构是计算机艺术的一种体现，合理的数据结构能够提高算法的执行效率，还可以提高数据的存储效率。

2.1.1　什么是数据结构

什么是数据结构，数据结构的具体定义又是什么呢？数据结构是计算机程序设计的产物，其实，到现在为止，计算机技术领域中还没有一个统一的数据结构的定义。不同的专家往往对数据结构有不同的描述，以下就是几种典型的定义。

“数据结构是数据对象、存在于该对象的实例以及组成实例的数据元素之间的各种关系，并且这种关系可以通过定义相关的函数来给出。”这是Sartaj Sahni在其经典著作《数据结构、算法与应用》一书中提出的，他将数据对象定义为一个实例或值的集合。

“数据结构是抽象数据类型ADT的物理实现。”这是Clifford A.Shaffer在其《数据结构与算法分析》一书中定义的。其中抽象数据类型的英文全称为Abstract Data Type，简称为ADT。抽象数据类型ADT的概念将在后面讲到。

Lobert L.Kruse也给出了数据结构设计过程的概念，他认为一个数据结构的设计过程可以分为抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，即ADT层，主要讨论数据的逻辑结构及其运算；数据结构层讨论一个数据结构的表示；实现层讨论一个数据结构在计算机内的存储细节及运算的实现。

虽然没有一个统一的定义，但是这些定义都具有相同的含义。在这里读者只需了解数据结构的基本含义，并能够使用其解决问题即可。可以这样简单地理解数据结构，一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构。由于数据必须在计算机内存储，数据的存储结构是其在计算机内的表示，也就是数据结构的实现形式。另外，讨论一个数据结构，必须涉及在该类数据上执行的运算。

数据结构是一切算法的基础，不仅如此，数据结构可以说是程序设计语言的基础。正是由于对数据结构的深入理解，才导致多种多样的程序设计语言的诞生，如Java、C++、C#等。其中，面向对象的程序设计语言就是完善处理对象类型数据结构的范例，这在某些方面可以方便地描述和解决实际问题。

2.1.2　数据结构中的基本概念

深入了解数据结构之前，读者需要简单掌握数据结构中涉及的一些基本概念，主要包括如下内容。

・数据（Data）：数据是信息的载体，其能够被计算机识别、存储和加工处理，是计算机程序加工的“原材料”。数据包括的类型非常广，如基本的整数、字符、字符串、实数等，此外，图像和声音等也都可以认为是一种数据。

・数据元素（Data Element）：数据元素是数据的基本单位，也称为元素、结点、顶点、记录等。一般来说，一个数据元素可以由若干数据项组成，数据项是具有独立含义的最小标识单位。数据项也可称为字段、域、属性等。

・数据结构（Data Structure）：数据结构指的是数据之间的相互关系，即数据的组织形式。这就是本章所要讨论的主要内容。

2.1.3　数据结构的内容

一般来说，数据结构包括三方面的内容，数据的逻辑结构、数据的存储结构和数据的运算。下面就将分析这三方面的内容。

・数据的逻辑结构（Logical Structure）：即数据元素（Data Element）之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据的，与数据在计算机中如何存储无关，也就是独立于计算机的抽象概念。从数学分析的角度来看，数据的逻辑结构可以看作从具体问题抽象出来的数学模型。

・数据的存储结构（Storage Structure）：即数据元素（Data Element）及其逻辑关系在计算机存储器中的表示形式。数据的存储结构依赖于计算机语言，是逻辑结构用计算机语言的实现。一般来说，只有在高级语言的层次上才会讨论存储结构，在低级的机器语言中，存储结构是具体的。

・数据的运算：即能够对数据施加的操作。数据的运算的基础为数据的逻辑结构，每种逻辑结构都可以归纳为一个运算的集合。在数据结构范畴内，最常用的运算包括检索、插入、删除、更新、排序等。

1）数据结构的例子

为了便于读者理解，下面举一个例子来分析有关数据结构的概念和内容。表2-1所示为某班级学生成绩表，这里显示的是其中一部分。

在表2-1中，每一行可以看作一个数据元素（Data Element），也可以称为记录或者结点。这个数据元素由学号、姓名、数学成绩、物理成绩、英语成绩和语文成绩等数据项构成。

通过这个表首先来看一下数据元素之间的逻辑关系。下面用数据结构的语言来描述这些逻辑关系。

・对于表中任意一个结点，直接前趋（Immediate Predecessor）结点最多只有一个。直接前趋结点即与它相邻且在它前面的结点。

・对于表中任意一个结点，直接后继（Immediate Successor）结点最多只有一个。直接后继结点即与它相邻且在它后面的结点。

・表中只有第一个结点没有直接前趋，即开始结点。

・表中只有最后一个结点没有直接后继，即终端结点。

例如，表中“张三”所在的结点就是开始结点，“马七”所在的结点就是终端结点。表中间的“陈九”所在结点的直接前趋结点是“李四”所在的结点，表中间的“陈九”所在结点的直接后继结点是“王一”所在的结点。这些结点关系就构成了某班级学生成绩表的逻辑结构。

然后再来看一下数据的存储结构。数据的存储结构是数据元素及其逻辑关系在计算机存储器中的表示形式。这就需要采用计算机语言来进行描述，例如，是每个结点按照顺序依次存储在一片连续的存储单元中呢，还是存储在分散的空间而使用引用将这些结点链接起来呢？这方面的内容将在后面进行详述。

最后，再来分析数据的运算。当拿到这个表之后，应进行哪些操作呢？一般来说，主要包括如下操作。

・查找某个学生的成绩。

・对于新入学的学生，在表中增加一个结点来存放。

・对于退学的学生，将其结点从表中删除。

当然，还包括计算每个学生的总成绩、平均成绩、整个班级的平均成绩等，不过这些内容就不属于数据结构的范畴了。上述三种操作就是最基本的数据结构的运算，即数据结点的查找、插入和删除。

这样，结合这个简单的例子读者便能够理解数据结构的基本概念和内容。

2）数据结构是一个有机的整体

其实，数据的逻辑结构、数据的存储结构和数据的运算是一个整体，孤立地去理解这三者中的任何一个都是不全面的。这主要表现在如下方面。

・同一个逻辑结构可以有不同的存储结构。逻辑结构和存储结构是两个概念，同一个逻辑结构可以有不同的存储结构。例如，线性表是最简单的一种逻辑结构，如果线性表采用顺序方式存储，这种数据结构就是顺序表；如果线性表采用链式方式存储，这种数据结构就是链表；如果线性表采用散列方式存储，这种数据结构就是散列表。

・同一种逻辑结构也可以有不同的数据运算集合。数据的运算是数据结构中十分重要的内容。一个相同的数据逻辑结构和存储结构采用不同的运算集合及运算性质，将导致全新的数据结构。例如，如果将线性表的插入运算限制在表的一端，而删除操作限制在表的另一端，那么这种数据结构就是队列；如果将线性表的插入和删除操作都限制在表的同一端，那么这种数据结构就是栈。

数据结构中的这三方面是一个有机的整体，缺一不可。数据的逻辑结构、数据的存储结构和数据的运算任何一个发生变化都将导致一个全新的数据结构出现。

2.1.4　数据结构的分类

数据结构有很多种，一般来说，按照数据的逻辑结构来对其进行简单地分类，可分为线性结构和非线性结构两类。

1）线性结构

简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述的话，线性结构应该包括如下内容：

・线性结构是非空集；

・线性结构有且仅有一个开始结点和一个终端结点；

・线性结构所有结点最多只有一个直接前趋结点和一个直接后继结点。

前面提到的线性表就是典型的线性结构，还有栈、队列和串等都是线性结构。

2）非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下内容：

・非线性结构是非空集；

・非线性结构的一个结点可能有多个直接前趋结点和直接后继结点。

在实际应用中，数组、广义表、树结构和图结构等数据结构都是非线性结构。

2.1.5　数据结构的几种存储方式

数据的存储结构是数据结构的一个重要内容。在计算机中，数据的存储结构可以采用如下4种方法来实现。

1）顺序存储方式

简单地说，顺序存储方式就是在一块连续的存储区域一个接着一个地存放数据。顺序存储方式把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构（Sequential Storage Structure），一般采用数组或者结构数组来描述。

线性存储方式主要用于线性逻辑结构的数据存放，而对于图和树等非线性逻辑结构则不适用。

2）链接存储方式

链接存储方式比较灵活，其不要求逻辑上相邻的结点在物理位置上相邻，结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指向下一个结点的存放位置。

链接存储方式也称为链式存储结构（Linked Storage Structure），一般在原数据项中增加引用类型来表示结点之间的位置关系。

3）索引存储方式

索引存储方式是采用附加的索引表的方式来存储结点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为：（关键字、地址）。其中，关键字是能够唯一标识一个结点的数据项。

索引存储方式还可以细分为如下两类。

・稠密索引（Dense Index）：这种方式中每个结点在索引表中都有一个索引项，其中，索引项的地址指示结点所在的存储位置；

・稀疏索引（Spare Index）：这种方式中一组结点在索引表中只对应一个索引项。其中，索引项的地址指示一组结点的起始存储位置。

4）散列存储方式

散列存储方式是根据结点的关键字直接计算出该结点的存储地址的一种存储方式。

在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。而且这4种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储描述。

2.1.6　数据类型

几乎每一种程序设计语言都会讲到数据类型的概念。简单地说，数据类型就是一个值的集合及在这些值上定义的一系列操作的总称。例如，对于C语言的整数类型，其有一定的取值范围，对于整数类型还定义了加法、减法、乘法、除法和取模运算等操作。

按照数据类型的值是否可以分解，数据类型可以分为基本数据类型和聚合数据类型。

・基本数据类型：其值不能进一步分解，一般是程序设计语言自身定义的一些数据类型，如C语言中的整型、字符型、浮点型等。

・聚合数据类型：其值可以进一步分解为若干分量，一般是用户自定义的数据类型，如C语言中的结构、数组等。

上述数据类型的概念在一般的程序设计语言中都会讲到。在这里将重点看一下另外一个概念，抽象数据类型（Abstract Type，简称为ADT）。

抽象数据类型ADT指的是数据的组织及其相关的操作。ADT可以看作数据的逻辑结构及其在逻辑结构上定义的操作。一个抽象数据类型ADT可以定义为如下形式：

抽象数据类型ADT一般具有如下两个重要特征。

・数据抽象：使用抽象数据类型ADT时，其强调的是实体的本质特征，所能够完成的功能，以及与外部用户的接口。

・数据封装：用于将实体的外部特性和其内部实现细节进行分离，并且对外部用户隐藏其内部实现细节。

抽象数据类型ADT可以看作描述问题的模型，它独立于具体实现。ADT的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在Java语言中是使用接口来表示抽象数据类型ADT，用接口的实现类来实现ADT的。

抽象数据类型ADT和接口的概念其实很好地表现了程序设计中的两层抽象。抽象数据类型ADT是概念层上的抽象，而接口则属于实现层上的抽象。

2.1.7　常用的数据结构

在计算机科学的发展过程中，数据结构也在随着发展。目前，程序设计中常用的数据结构包括如下内容。

1）数组（Array）

数组是一种聚合数据类型，是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、对象数组等。数组还可以有一维、二维及多维等表现形式。

2）栈（Stack）

栈是一种特殊的线性表，其只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈低，最后插入的数据在栈顶，读出数据时，从栈顶开式逐个读出。栈在汇编语言程序中经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

3）队列（Queue）

队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。

4）链表（Linked List）

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构在物理上具有非连续的特点。链表由一系列数据结点构成，每个数据节点包括数据域和引用域两部分。其中，引用域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的引用链接次序来实现的。

5）树（Tree）

树是典型的非线性结构，其是包括n个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有m个后继结点，m≥0。

6）图（Graph）

图是另外一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

7）堆（Heap）

堆是一种特殊的树型数据结构，一般讨论的堆都是二叉堆。堆的特点是其根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

8）散列表（Hash）

散列表源自于散列函数（Hash function），其思想是如果在结构中存在关键字和T相等的记录，那么必定在F（T）的存储位置可以找到该记录，这样就可以不用进行比较而直接取得所查记录。

2.1.8　选择合适的数据结构解决实际问题

计算机给程序员带来了很大的方便。计算机能够处理的问题一般可以分为两类：数值计算问题和非数值计算问题。

数值计算问题在早期的计算机发展中占据了很大的比例。例如，线性方程的求解、矩阵的计算等。这类问题一般需要程序设计的技巧和相应的数学知识，而数据结构方面涉及的内容比较少。

随着计算机应用范围的扩大，一些非数值计算问题越来越突出，成为计算机解决的焦点问题。目前来说，非数值计算问题大约占据了80％的计算机工作时间。高效解决这类问题不仅需要数学知识，而且还需要设计合理的数据结构。例如，在一个包含大量数据的电话号码簿中查找指定号码的问题，运动比赛的赛程时间安排问题等。这些问题往往不能简单地用数学公式来表示，还需要合理地选择数据结构来处理。

在本书中，对于数值计算问题和非数值计算问题都会涉及。数值计算相关的问题主要是一些数学和工程中的计算算法，包括多项式求解、矩阵计算、微分、积分等算法。非数值计算问题主要是本章的数据结构及后面章节中的数据结构问题。