2.1 数据结构基本知识

计算机已被广泛用于数据处理。所谓数据处理，是指对数据集合中的各元素以各种方式进行运算和分析。在数据处理领域中，人们最感兴趣的是分析数据集合中各数据元素之间的关系，为了提高处理效率，应如何组织它们。这些就形成了数据结构所要研究的基本内容。

2.1.1 数据结构的概念

早期计算机主要是处理数值计算的问题，程序设计者的主要精力集中于程序设计的技巧。随着计算机应用领域的逐渐扩大以及计算机软件、硬件的迅速发展，非数值计算问题就越来越重要了，这就涉及了数据元素之间的关系。数据元素之间的关系一般无法用数学方程式来描述，解决这类问题的方法不再是数学分析和计算方法，而是应用合理的数据结构，才能更好地解决问题。

数据结构广泛地应用于信息学科、系统工程、应用数学以及各种工程领域，它是介于数学，计算机软件、硬件之间的一门计算机科学与技术专业的核心课程。例如，金融管理、文献查找、商业系统、学生信息检索系统、图书馆系统等，都涉及数据结构的问题。所有的计算机系统软件和应用软件不仅仅只是编程，它们都需要用到各种数据结构。因此，数据结构对学习计算机软件有着非常重要的作用，学习数据结构对学习操作系统、数据库、计算机网络、人工智能等其他课程都是十分有益的。

学习数据结构的相关概念，必须把握以下几个概念。

数据（Data）是信息的载体，是可以被计算机识别、存储并加工处理的描述客观事物的信息符号的总称。数据是计算机加工处理的对象，包括数值数据和非数值数据。数值数据包括整数、实数或复数，主要用于科学计算、工程计算和商务处理等；非数值数据包括字符、文字、图像、图形、音频、视频等。

数据元素（Data Element）是数据的基本单位，表现为数据集合中的一个个体。数据元素可以由很多具有不同数据类型的数据项（Data Item）组成，数据项是数据的最小单位。在不同情况下，数据元素又被称为元素、结点、顶点、记录等。例如，在教师信息管理系统中，教师信息表的一个数据元素就是一个教师的记录，一般是由职工号、姓名、年龄、性别、出生年月、开始工作时间等数据项组成。组成数据元素的各个数据项也被称为数据域或字段，能够用来唯一表示一个记录的数据项被称为主关键字。例如，教师信息表中的职工号，可以唯一标识一名教师。在解决实际问题时，通常把一个记录当成一个基本单位进行访问和处理。

数据对象（Data Object）是具有相同属性的数据元素的集合。在面向对象的程序设计中，数据对象可以看作是数据元素类（Data Element Class）。在具体问题中，有同一属性的数据元素称为一个数据对象类，数据元素是数据对象类的一个实例。例如，在计算机网络中，每台计算机都是一个数据元素的类，计算机A和计算机B是该数据元素类的两个实例，其数据元素值为A和B。

数据、数据元素、数据对象之间的关系如图2-1所示。

数据是描述客观事物信息符号的总称，是一个非常广的概念，图2-1为一个数据集合。数据元素是数据的基本单位，在图中表示为数据集合的许多个体。而数据对象是具有相同性质的数据元素的集合，在图中为许多具有同一性质的数据元素的集合。

【例2-1】 学生信息管理系统。通常学生信息管理系统是用顺序文件来存储数据的，在查询的时候需要顺序查询。数据通常存放在数据库中，利用数据库来组织、管理数据，以备查询。表2-1为学生信息数据表。

学生信息数据表中，存储数据的结构就是线性结构。用户可以利用该表对数据进行查询、增加、删除和更新操作，还可以利用一些查找方法对数据进行查找。

【例2-2】 输出n的全排列。例如，输出3的全排列，也就是n＝3，应该如何处理呢？可以利用图2-2所示的结构来输出。

上面的这种结构是属于树结构，可以利用这种结构输出树中某层的全部结点。

【例2-3】 已知某省各县之间的交通图。现要在这个省内建立一所省级医院，问题是这所医院应该建在哪个县，才能使离这个医院最远的县到达该医院的路途最近？

可以把这个问题转化为求一个有向图的中心点，如图2-3所示。

根据有向图中心点的概念，计算出d点为中心点，所以省医院应该建立在d县。这种结构是图结构，本例是有向图结构，对有向图的基本操作主要有生成有向图和求有向图的中心点等。

通过以上例子可以看出，数据结构主要研究诸如线性结构、树结构及图结构等非数值性数学模型在计算机中的表示及操作。数据结构的概念在计算机科学界至今没有标准的定义，很多专家、学者根据各自的理解而有不同的表述方法：

Sartaj Sahni在《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（Data Object）定义为“一个数据对象是实例或值的集合”。

Clifford A.Shaffer在《数据结构与算法分析》一书中对数据结构的定义：“数据结构是抽象数据类型（Abstract Data Type，ADT）的物理实现。”

Lobert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算；数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。

一般认为，数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构有两个要素，一个是数据元素的集合，另一个是建立在数据元素集合之上的关系的集合。我们用集合论的方法来定义数据结构，将之表示成一个二元组，即DS＝（D，R）其中，D是数据元素的集合，R是定义在D上关系的有限集合。这是一个广泛数据结构的定义，是计算机进行数据处理的基础。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据对象，而且要描述数据对象各元素之间的相互关系。

数据结构作为计算机的一门学科，主要研究和讨论以下3个问题：

1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。

2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构，也称物理结构。

3）对各种数据结构进行的运算。

讨论以上各问题的主要目的是为了提高数据处理的效率。主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。

2.1.2 数据的逻辑结构与存储结构

数据的物理结构是数据结构在计算机中的表示（映像），它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。当然，存储结构除了常用的顺序存储结构和链式存储结构外，还有索引存储和散列存储。

根据数据元素之间的逻辑关系，可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时，所有结点之间的存储单元地址可连续也可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。

在数据结构中，数据元素相互之间的关系称为结构。数据结构有4类基本结构：集合结构、线性结构、树结构、图结构（网状结构）。树结构和图结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其他关系。线性结构中元素之间存在一对一关系；树结构中元素之间存在一对多关系；图结构中元素之间存在多对多关系。在图结构中每个结点的前驱结点数和后续结点数可以有多个。

集合是一定范围的、确定的、可以区别的事物，可以当作一个整体来看待，简称集，其中各事物称为集合的元素或简称元。例如，电影中出现的不同汉字，全体英文大写字母等。任何集合都是它自身的子集。在定义中主要是各种元素之间的关系是否属于同一集合。

线性结构是数据元素之间仅存在前后关系，又称为一对一的关系，如图2-4所示。后面讲到的线性表、栈和队列都是属于线性结构。

树结构表示数据元素（结点）之间存在层次关系，又称一对多关系，如图2-5所示。后面所讲到的树就是属于树结构。

图结构（网状结构）是指数据元素（顶点）之间存在邻接关系，又称多对多关系，如图2-6所示。后面讲到的图就属于这种结构。

2.1.3 数据类型与抽象数据类型

数据类型是与数据结构相关的一个概念，在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。数据类型（Data Type）是一个值的集合和定义在这个值集上一组操作的总称，是程序设计语言中允许的变量类型。在高级语言中，数据类型可以分为基本类型和构造类型。基本类型是不可分解的基本数据单位，如C语言中的整型、字符型、浮点型、双精度型等；而构造类型则可以有多个域（字段）按某种结构组成的，是可以分解的，其中的任意域可以是基本数据类型，也可以是其他数据类型。

在数据类型的基础上，又定义了抽象数据类型。抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。

抽象数据类型描述的一般格式：

抽象数据类型可以使人们更容易描述现实世界。例如，用线性表描述学生成绩表，用树或图描述遗传关系等。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

数据类型与抽象数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就可以看作是抽象数据类型，尽管它们在不同处理器上的实现方法不同，但其定义的数学特性，在用户看来是相同的。因此，“抽象”的意义在于数据类型的抽象数学特性。但是，抽象数据类型的范畴更广，它不再局限于已经定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。