【例1-1】学生信息检索系统。

当系统需要查某个学生的有关情况时，或者想查询某个专业或年级的学生的有关情况时，只要建立相关的数据结构，按照某种算法编写相关的程序，就可以实现计算机自动检索。为此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和若干张分别按姓名、专业、年级顺序排列的索引表，如表1-1～表1-4所示。由这4张表构成的文件便是学生信息检索的数学模型。

表1-1　学生基本信息表

表1-2　姓名索引表

表1-3　专业索引表

表1-4　年级检索表

诸如此类的还有电话号码查询问题，考试成绩查询问题，企业进、销、存管理问题等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系，这类数学模型可称为线性的数据结构。

【例1-2】计算机系统组成结构，如图1-2所示。

计算机系统是由硬件系统和软件系统这两大系统组成，硬件系统由CPU、存储器、输入/输出设备、外设组成，而软件系统由系统软件和应用软件组成。如果把它们视为数据元素，这些元素之间所呈现的是一种层次关系，从上到下按层进行展开，形成“一棵倒立的树”，最上层是“树根”，依层向下展出“节点”和“树叶”。

树结构还有一个单位的组织机构、国家行政区域规划、书籍目录等。在这类问题中，计算机处理的对象是树结构，元素之间是一种一对多的层次关系，这类数学模型称为树的数据结构。

图1-1　计算机系统组成结构图

【例1-3】最短路径问题。

从城市A到城市B有多条线路可达，但每条线路的交通成本不同，那么怎样选择一条线路，使得从城市A出发到达城市B所花费的费用最低呢？解决问题的方法是，可以将这类问题抽象为图的最短路径问题。如图1-2所示，图中的顶点代表城市，有向边代表两个城市之间的通路，边上的权值代表两个城市之间的交通费。求解A到B的最低费用，就是要在有向图中，从A点到B点的多条路径中，寻找一条各边权值之和最小的路径，即为该图的最短路径。

图1-2　最短路径问题

图结构还有网络工程图问题、教学计划编排问题、比赛编排问题等，在这类问题中，元素之间是多对多的网状关系，这类数学模型称为图的数据结构。

由以上3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

“数据结构”最早是1968年在美国被确定为一门独立的课程的。同年，著名的美国计算机科学家D.E.Knuth教授所著《计算机程序设计技巧》的第一卷《基本算法》，是第一本系统地阐述数据的逻辑结构以及运算的著作。从20世纪60年代末到70年代初出现了大型程序，程序与数据相对独立，结构化程序设计成为程序设计方法学的主要内容，人们越来越感到数据结构的重要性，认为程序设计的实质就是针对所处理问题选择一种好的数据结构，并加之一种好的算法。

数据结构在计算机科学中是一门综合性的专业基础课，是操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛地应用于信息科学、系统工程、应用数学以及各种工程技术领域。数据结构的研究涉及的知识面十分广，可以认为它是介于数学、计算机硬件和软件之间的一门核心课程。

图1-3　数据结构与其他课程的关系

学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。对于计算机专业的学生，不学习数据结构是不行的，因为几乎所有的程序和软件都要使用某种或某些数据结构。例如，在面向对象的程序设计中，每一个对象在严格意义上来说就是一个数据结构，而哪个程序不使用对象呢？可以这样说，不懂数据结构，就编不出什么像样的程序和软件。

此外，数据结构在软件工程和计算机学科的其他领域也发挥着重要甚至关键的作用。例如，对大型数据库的管理，为互联网提供索引服务、云计算、云存储都需要广泛使用数据结构。在软件工程领域，数据结构被单独提取出来作为软件设计与实现过程的一个阶段。

 

基本概念和术语

在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的含义。

数据（Data）：是信息的载体，能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序可以处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。

数据元素（Data Element）：是数据的基本单位。在不同的条件下，数据元素又可称为元素、节点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、计算机系统组成结构中状态树的一个状态、最短路径问题中的一个顶点等，都被称为一个数据元素。

有时，一个数据元素可由若干个数据项组成。例如，学生信息检索系统中学生信息表的每一个数据元素就是一个学生记录，它包括学生的学号、姓名、性别、专业和年级等数据项。这些数据项可以分为两种：一种叫作初等数据项，如学生的性别、年级等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫作组合数据项，如学生的成绩，它可以再划分为由各门不同的课程所组成的更小项。

数据项（Data Item）：是组成数据元素的、有独立含义的、不可分割的最小单位，如表1-1的学号、年级等都是数据项。数据项有名和值之分，数据项名是一个数据项的标识，用变量定义，而数据项值是它的一个可能取值，表1-1中的2011010001是数据项“学号”的一个取值。数据项具有一定的类型，依数据项的取值类型而定。

数据对象（Data Object）：是相同性质的数据元素的集合，是数据集合的一个子集。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象，数据元素是数据元素类的一个实例。例如，在最短路径问题中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。

数据结构（Data Structure）：是指互相之间存在着一种或多种特定关系的数据元素的集合。在计算机中，数据元素都不会是孤立的，它们之间存在着这样或那样的关系，这种数据元素之间的关系称为数据结构。一个数据结构包含两个要素：一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。

数据结构的形式定义为一个二元组：

式中，D是数据元素的有限集，R是D上关系的有限集。

数据结构包括数据逻辑结构和数据存储结构。

1.数据逻辑结构

数据逻辑结构可以看作是从具体问题抽象出来的数学模型，其与数据的存储无关。根据数据元素间关系的不同特性，通常有下面四类基本的逻辑结构，如图1-4所示。

图1-4　四类基本的逻辑结构示意图

（1）集合结构。结构中的数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。

（2）线性结构。结构中的数据元素之间存在着一对一的线性关系。

（3）树结构。结构中的数据元素之间存在着一对多的层次关系。

（4）图结构或网状结构。结构中的数据元素之间存在着多对多的任意关系。

【例1-4】

有一数据结构采用二元组描述为D_S=(D,R)，其中：

根据已知条件，对应D_S的逻辑结构示意图如图1-5所示。

图1-5　对应D_S的逻辑结构示意图

从上例看出，每个数据元素有且仅有一个前驱（除第一个节点外），有且仅有一个后继（除最后一个节点外）。数据元素之间为一对一的关系，即线性关系。这种数据结构就是线性结构。

由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。故数据的四类基本逻辑结构可概括如下：

2.数据存储结构

研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称为映像）称为数据存储结构（或称物理结构）。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素之间关系的表示。数据存储结构可采用顺序存储结构或链式存储结构。

（1）顺序存储结构。把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。

（2）链式存储结构。对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过复数的指针字段来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针来实现。

除了通常采用的顺序存储结构和链式存储结构外，有时为了查找方便还采用索引存储结构和散列存储结构。

3.数据运算

讨论数据结构的目的是为了在计算机中实现操作运算，为了有效地处理数据，提高数据运算的执行效率，应按一定的逻辑结构把数据组织起来，并选择适当的存储方法将数据存储到计算机内，然后对其进行运算。

数据的运算是定义在数据的逻辑结构之上的，每一种逻辑结构都有一个运算的集合，如插入、删除、修改等。这些运算实际上是在数据元素上施加一系列抽象的操作，抽象的操作是指只知道这些操作要求做什么，而无须考虑如何做，只有在确定了存储结构后，才能具体实现这些运算。

数据的运算主要有修改、插入、删除、查找、排序等，其中查找运算是一个很重要的运算过程，修改、插入、删除、排序中都包含着查找运算，排序本身就是元素之间通过查找相互比较的过程，修改、插入、删除则要通过查找来确定其操作的位置。

数据结构课程的内容

数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构技术也广泛应用于信息科学、系统工程、应用数学及各种工程技术领域。

数据结构课程集中讨论软件开发过程中的设计阶段，同时涉及编码和分析阶段的若干基本问题，此外，为了构造出好的数据结构并实现它，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容可归纳为三个部分：逻辑结构、存储结构和数据运算。简言之，按某种逻辑关系组织起来的一批数据，按一定的存储方式将其存入计算机的存储器中，并在这些数据上定义一个运算集，是数据结构课程的基本内容，如表1-5所示。

表1-5　数据结构课程的基本内容

数据结构主要研究怎样合理地组织数据，建立合适的结构，提高执行程序所用的时空效率。

数据结构的核心技术是分解与抽象。通过对问题的抽象，舍弃数据元素的具体内容，从而得到逻辑结构；同样，通过分解将数据划分成各种功能实现，再通过抽象舍弃实现细节，就得到了数据运算的定义。由此可将许多具体问题转换为数据结构，这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务，这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。

数据结构课程不仅讲授数据信息在计算机中的组织和表示方法，同时也重在培养学习者高效解决复杂问题的能力。不同的数据结构适用于不同的应用，例如，B树就特别适用于数据库和文件系统，而哈希表则常常在编译器中使用等。

 

数据类型和抽象数据类型

运用抽象数据类型描述数据结构，有助于在设计一个软件系统时，不必首先考虑其中包含的数据对象，以及操作在不同处理器中的表示和实现细节，而是在构成软件系统的每个相对独立的模块上定义一组数据和相应的操作，把这些数据的表示和操作细节留在模块内部解决，在更高的层次上进行软件的分析和设计，从而提高软件的整体性能和利用率。

数据结构是一种抽象，它将数据的个体属性去除，只考虑数据元素之间的关系。

通过步步抽象，不断地突出“做什么”，而将“怎么做”隐藏起来，即将一切用户不必了解的细节封装起来，从而简化了问题。所以，抽象是程序设计最基本的思想方法。

 

数据类型

数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围及该类型中可允许使用的一组运算。

数据类型是和数据结构密切相关的一个概念。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。数据类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。

在高级程序设计语言中，数据类型可分为两类：一类是原子类型，另一类则是结构类型。原子类型的值是不可分解的，例如，C语言中的整型、字符型、浮点型、双精度型等基本类型，分别用关键字int、char、float、double标识；而结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是原子的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是一种数据类型，而数据类型则可以看成是由一种数据结构和定义在其上的一组操作组成的。

 

抽象数据类型

抽象就是抽取出实际问题的本质。将无限多的关系种类里面的非关键属性去除，只取其中的共性来设计数据结构。例如，对于数据元素A、B、C而言，它们之间的关系可以是A在B的前面，B在C的前面；也可以是C在B的前面，B在A的前面。显然，对于个体的数据元素而言，这是两种不同的结构。但抛开个体数据元素就会发现，这两种结构实际上是一种数据结构类型：线性结构。

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。

抽象数据类型和数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，所以在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。

但在另一方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对