下载掌阅APP，畅读海量书库
立即打开
数据结构是计算机专业中的一门专业基础必修课，凡是设置计算机专业的院校几乎都开设了此课程。此外，一些常见的数据结构已经渗透到计算机专业的各门课程中，例如“操作系统”课程中涉及“队列”和“树”数据结构的使用，进程调度的原则是从就绪队列中按照某种原则选取一个进程执行；在文件管理中，文件一般按照“树”形结构进行存储和处理。
瑞士著名计算机科学家尼古拉斯·沃斯（N.Wirth）提出了著名公式“程序=算法+数据结构”，表明了数据结构在程序设计中的重要地位。在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、浮点型或布尔型数据，所以程序设计者的主要精力都集中在程序设计技巧上，而无须重视数据结构。随着计算机应用领域的扩大以及软硬件的发展，非数值计算问题显得越来越重要。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式直接描述。数学分析和计算方法在解决此类问题时常显得力不从心，而设计出合适的数据结构才能有效地解决问题。
因此，掌握好数据结构的知识，对于提高解决实际问题的能力将会有很大的帮助。实际上，一个“好”的程序无非是选择一个合理的数据结构和好的算法，而算法的好坏很大程度上又取决于描述实际问题所采用的数据结构是否合理。所以，要编写出好的程序，仅仅学习计算机语言是不够的，必须扎实地掌握数据结构的基本知识和基本技能。
一般而言，利用计算机解决一个具体问题时，大致需要经过如下3个步骤：
①从具体问题抽象出一个合适的数学模型。
②设计一个可解此数学模型的算法。
③编写程序，进行测试、调整，直到问题得以解决。
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。为了说明这个问题，此处首先举一个例子，然后给出明确的含义。
例1-1 对于八皇后问题，不是根据某种确定的计算法则进行处理，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步产生一个新的状态，整个试探过程形成一棵隐含的状态树，如图1-1所示（此处为了描述方便，将八皇后问题简化为四皇后问题）。用回溯法求解的过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。
图1-1 四皇后问题隐含状态树
由例1-1可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而主要是线性表、树、图这类的数据结构。因此，可以说数据结构主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
本小节将给出一些概念和术语的定义，这些概念和术语将多次出现在之后的章节中。
数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机中，它泛指所有能输入计算机中并被计算机程序处理的符号。它是计算机程序加工的原料，文字、表格、声音、图像等都称为数据。
数据元素是数据的基本单位，在程序中通常把数据元素作为一个整体进行考虑和处理。例如，表1-1所示的学生表中，如果把每行当作一个数据元素来处理，此表共包含7个数据元素。一个数据元素可由若干数据项组成，例如表1-1中每一个学生的信息作为数据元素，而学生信息的每一项（如学号、姓名等）都是数据项。数据的最小单位即数据项。
表1-1 学生表
数据结构是指数据及其之间的相互关系，可以看成相互之间存在一种或多种特定关系的数据元素的集合。因此，可以把数据结构看成带结构的数据元素的集合。数据结构包括以下3个方面。
①数据元素之间的逻辑关系，即数据的逻辑结构。
②数据元素及其关系在计算机存储系统中的存储方式，即数据的存储结构，也称为数据的物理结构。
③施加在该数据上的操作，即数据的运算。
为了更准确地描述数据结构，通常采用二元组表示，表示方法为
B = ( D , R )
其中， B 是一种数据结构，它由数据元素的集合 D 和 D 中二元关系的集合 R 组成，即
D = { d i | 1 ≤ i ≤ n , n ≥ 0}
R = { r j | 1 ≤ j ≤ m , m ≥ 0}
其中， d i 表示集合 D 中的第 i 个结点或数据元素， n 为 D 中结点的个数，特别地，若 n =0，则 D 是一个空集，因而 B 也就无结构可言，有时把这种情况认为是具有任意结构。 r j 表示集合 R 中的第 j 个关系， m 为 R 中关系的个数，特别地，若 m =0，则 R 是一个空集，表明集合 D 中的结点间不存在任何关系，彼此是独立的。
R 中的一个关系 r 是序偶的集合，对于 r 中的任一序偶< x , y >( x , y ∈ D )，把 x 叫作序偶的第一结点，把 y 叫作序偶的第二结点，称序偶的第一结点为第二结点的直接前驱，称第二结点为第一结点的直接后继。若某个结点没有直接前驱，则称该结点为开始结点；若某个结点没有直接后继，则称该结点为终端结点。
数据类型是一个值的集合和定义在这个集合上的一组操作的总称。例如，Java语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和模运算等。按“值”的不同特性，高级程序设计语言中的数据类型可分为两种：原子类型和结构类型。原子类型的值是不可分解的，例如Java语言中的基本类型（整型、布尔型等）；结构类型的值是若干成分按照某种结构组成的，因此是可以分解的，其组成成分既可以是结构的，也可以是非结构的。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内的存储形式无关，即不论其内部结构如何变化，只要它的逻辑特性不变，都不影响外部使用。
抽象数据类型的范畴十分广，它不仅包括当前各处理器中已定义并实现的数据类型（固有类型），而且包括用户在设计软件时自定义的数据类型。本书定义抽象数据类型格式如下：
ADT 抽象数据类型名{
数据对象：（数据对象定义）
数据关系：（数据关系定义）
数据操作：（数据操作定义）
}ADT 抽象数据类型名
数据的逻辑结构是从逻辑关系（主要是指相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。在不会产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构主要分为以下几类。
微课1-1 数据的逻辑结构
集合是指数据元素之间除了“同属于一个集合”的关系，别无其他关系。
线性结构是指该结构中的结点之间存在一对一的关系，其特点是开始结点和终端结点都是唯一的。除了开始结点和终端结点，其余结点都有且仅有一个直接前驱，有且仅有一个直接后继。顺序表就是一种典型的线性结构。
树形结构是指该结构中结点之间存在一对多的关系，其特点是每个结点最多只有一个直接前驱，但可以有多个直接后继，可以有多个终端结点。二叉树就是一种典型的树形结构。
图形结构或称为网状结构，是指该结构中的结点之间存在多对多的关系，其特点是每个结点的直接前驱和直接后继的个数都可以是任意的。因此，图形结构可能没有开始结点和终端结点，也可能有多个开始结点和多个终端结点。
树形结构和图形结构统称为非线性结构，该结构中的结点之间存在一对多或多对多的关系。由线性结构、树形结构和图形结构的定义可知，线性结构是树形结构的特殊情况，而树形结构又是图形结构的特殊情况，以上各类结构对应的示例如图1-2所示。
图1-2 4类基本数据结构
例1-2 有数据结构 B 1 =( D , R )，其中：
D = { a , b , c , d , e , f , g , h , i , j }
R = { r }
r = {( a , b ), ( a , c ), ( a , d ), ( b , e ), ( c , f ), ( c , g ), ( d , h ), ( d , i ), ( d , j )}
画出其逻辑结构。
解 对应 B 1 的逻辑结构如图1-3所示。从该例中可以看出，每个结点有且仅有一个直接前驱（除根结点外），但有多个直接后继（叶子结点可看作具有0个直接后继）。这种数据结构的特点是数据元素之间的关系为一对多关系，即层次关系，因此是一种树形结构。
图1-3 对应 B 1 的逻辑结构
例1-3 有数据结构 B 2 =( D , R )，其中：
D = { a , b , c , d , e }
R = { r }
r = {( a , b ), ( a , c ), ( b , c ), ( c , d ), ( c , e ), ( d , e )}
画出其逻辑结构。
解 对应 B 2 的逻辑结构如图1-4所示。从该例中看出，每个结点可以有多个直接前驱和多个直接后继。这种数据结构的特点是数据元素之间的关系为多对多关系，即图形关系，因此是一种图形结构。
图1-4 对应 B 2 的逻辑结构
数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（亦称为映象），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。数据元素之间的关系在计算机中有两种表示方式：顺序映象和非顺序映象。归纳起来，数据的存储结构在计算机中有以下4种。
微课1-2 数据的存储结构
顺序存储结构是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。
顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全部用于存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。采用这种结构时，可实现对结点的随机存取。然而顺序存储结构的主要缺点是不便于修改，在对结点进行插入、删除运算时，可能要移动一系列的结点。
链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的“指针”字段表示的。由此得到的存储结构称为链式存储结构。
链式存储结构的优点是便于修改，在对结点进行插入、删除操作时，仅需要修改相应结点的“指针域”，不必移动结点。但与顺序存储结构相比，链式存储结构的存储空间利用率较低，因为分配给数据的存储单元有一部分被用来存储结点间的逻辑关系了。另外，由于逻辑上相邻的结点在物理位置上并不一定相邻，所以不能对结点进行随机访问操作。
索引存储结构通常在存储结点信息的同时建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是（关键字，地址），关键字唯一标识一个结点，地址作为指向结点的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。
线性结构采用索引存储结构后，可以对结点进行随机访问。在对结点进行插入、删除运算时，只需移动存储在索引表中对应结点的存储地址，而不必移动存放在结点表中结点的数据，所以仍保持较高的数据修改效率。索引存储结构的缺点是增加了索引表及存储空间开销。
哈希存储结构的基本思想是根据结点的关键字通过哈希函数直接计算出一个值，并将这个值作为该结点的存储地址。
哈希存储结构的优点是查找速度快，只要给出待查找结点的关键字，就可以计算出该结点的存储地址。与前3种存储结构不同的是，哈希存储结构只存储结点的数据，不存储结点之间的逻辑关系。哈希存储结构一般适用于要求对数据能够进行查找和插入的场景。