早期的计算机主要用于数值计算，现在，计算机主要用于非数值计算，包括处理字符、表格和图像等具有一定结构的数据。这些数据内容存在着某种联系，只有分清楚数据的内在联系，合理地组织数据，才能对它们进行有效的处理，设计出高效的算法。如何合理地组织数据、高效地处理数据，这就是“数据结构”主要研究的问题。本章简要介绍有关数据结构的基本概念和算法分析方法。

1.1 数据结构的研究内容

计算机主要用于数值计算时，一般要经过如下几个步骤：首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。在此过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述，即建立相应的数学方程。

20世纪60年代初期，“数据结构”有关的内容散见于操作系统、编译原理等课程中。目前，数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统都涉及数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以使查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。有关“数据结构”的研究仍不断发展，一方面，面向各专门领域中特殊问题的数据结构正在研究和发展；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越来越被人们所重视。

1.2 基本概念和术语

1.2.1　数据、数据元素、数据项和数据对象

数据（Data）是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用于完整地描述一个对象，如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。

数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N = {0，±1，±2，…}，字母字符数据对象是集合C = {‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可以是一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表）的集合，只要集合内元素的性质均相同，都可称之为一个数据对象。

1.2.2　数据结构

数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 数据结构包括逻辑结构和存储结构两个层次。

1．逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

数据的逻辑结构有两个要素：一是数据元素；二是关系。数据元素的含义如前所述，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构，如图 所示。它们的复杂程度依次递进。

（1）集合结构。数据元素之间除了“属于同一集合”的关系外，别无其他关系。
（2）线性结构。数据元素之间存在一对一的关系。
（3）树结构。数据元素之间存在一对多的关系。
（4）图结构或网状结构。数据元素之间存在多对多的关系。

其中集合结构、树结构和图结构都属于非线性结构。 线性结构包括线性表（典型的线性结构）、栈和队列（具有特殊限制的线性表，数据操作只能在表的一端或两端进行）、字符串（也是特殊的线性表，其特殊性表现在它的数据元素仅由一个字符组成）、数组（是线性表的推广，它的数据元素是一个线性表）、广义表（也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表）。非线性结构包括树（具有多个分支的层次结构）和二叉树（具有两个分支的层次结构）、有向图（一种图结构，边是顶点的有序对）和无向图（另一种图结构，边是顶点的无序对）。这几种逻辑结构可以用一个层次图描述，如图所示。

2．存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

（1）顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
（2）链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

1.2.3　数据类型和抽象数据类型

1．数据类型

数据类型（Data Type）是高级程序设计语言中的一个基本概念，前面提到过顺序存储结构可以借助程序设计语言的数组类型描述，链式存储结构可以借助指针类型描述，所以数据类型和数据结构的概念密切相关。

一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。程序设计语言允许用户直接使用的数据类型由具体语言决定，数据类型反映了程序设计语言的数据描述和处理能力。C语言除了提供整型、实型、字符型等基本类型数据外，还允许用户自定义各种类型数据。

2．抽象数据类型

抽象就是抽取出实际问题的本质。在计算机中使用二进制数来表示数据，在汇编语言中则可给出各种数据的十进制表示，它们是二进制数据的抽象，使用者在编程时可以直接使用，不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等，可以进一步利用这些类型构造出线性表、栈、队列、树、图等复杂的抽象数据类型。

抽象数据类型（Abstract Data Type，ADT）一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

抽象数据类型的定义格式如下：

ADT 抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名

其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式为：

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以“&”打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若初始条件为空，则省略。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

1.3 抽象数据类型的表示与实现

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

抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C++中，我们可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型。因此，C++中实现的类相当于数据的存储结构及其在存储结构上实现的对数据的操作。

抽象数据类型和类的概念实际上反映了程序或软件设计的两层抽象：抽象数据类型相当于在概念层（或称为抽象层）上描述问题，而类相当于在实现层上描述问题。此外，C++中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C++中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看做是应用层。

由此可以看出，最终表示和实现抽象数据类型，最好用面向对象的方法。另外，由于实际问题千变万化，数据模型和算法也形形色色，因此抽象数据类型的设计和实现，就不可能像基本数据类型那样规范和一劳永逸。

1.4 算法和算法分析

数据结构与算法之间存在着本质联系，在某一类型数据结构上，总要涉及其上施加的运算，而只有通过对所定义运算的研究，才能清楚理解数据结构的定义和作用；在涉及运算时，总要联系到该算法处理的对象和结果的数据。在“数据结构”中，将遇到大量的算法问题，因为算法联系着数据在计算过程中的组织方式，为了描述实现某种操作，常常需要设计算法，因而算法是研究数据结构的重要途径。

1.4.1　算法的定义及特性

算法（Algorithm）是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下五个重要特性。

（1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
（2）确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
（3）可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
（4）输入。一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
（5）输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

1.4.2　评价算法优劣的基本标准

一个算法的优劣应该从以下几方面来评价。

（1）正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
（2）可读性。一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。
（3）健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
（4）高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

1.4.3　算法的时间复杂度

算法效率分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间和空间性能上的比较，以便从中挑选出较优算法。

衡量算法效率的方法主要有两类：事后统计法和事前分析估算法。事后统计法需要先将算法实现，然后测算其时间和空间开销。这种方法的缺陷很显然，一是必须把算法转换成可执行的程序，二是时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的优劣。所以我们通常采用事前分析估算法，通过计算算法的渐近复杂度来衡量算法的效率。

1．问题规模和语句频度

不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。问题规模n对不同的问题含义不同，例如，在排序运算中n为参加排序的记录数，在矩阵运算中n为矩阵的阶数，在多项式运算中n为多项式的项数，在集合运算中n为集合中元素的个数，在树的有关运算中n为树的结点个数，在图的有关运算中n为图的顶点数或边数。显然，n越大算法的执行时间越长。

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数称作语句频度（Frequency Count）。

由于语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的。所以，所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。

2．算法的时间复杂度定义

为了客观地反映一个算法的执行时间，可以只用算法中的“基本语句”的执行次数来度量算法的工作量。所谓“基本语句”指的是算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。我们可以给出下述算法时间复杂度的定义。

一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作

T(n) = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度（Time Complexity）。

数学符号“O”的严格定义为：

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n) = O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤Cf(n)。

该定义说明了函数T(n)和f(n)具有相同的增长趋势，并且T(n)的增长至多趋向于函数f(n)的增长。符号“O”用来描述增长率的上限，它表示当问题规模n>n0时，算法的执行时间不会超过f(n)，其直观的含义如图1.6所示。

3．算法的时间复杂度分析举例

分析算法时间复杂度的基本方法为：找出所有语句中语句频度最大的那条语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)，取其数量级用符号“O”表示即可。具体计算数量级时，可以遵循以下定理。

定理1.1　若f(n)=amnm+am-1nm-1+¼+a1n+a0是一个m次多项式，则T(n)=O(nm)。

定理1.1说明，在计算算法时间复杂度时，可以忽略所有低次幂项和最高次幂的系数，这样可以简化算法分析，也体现出了增长率的含义。

若算法可用递归方法描述，则算法的时间复杂度通常可使用递归方程表示，此时将涉及递归方程求解问题。

常见的时间复杂度按数量级递增排列依次为：常量阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……、k次方阶O(nk)、指数阶O(2n)等。

4．最好、最坏和平均时间复杂度

算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。

称算法在最好情况下的时间复杂度为最好时间复杂度，指的是算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，指的是算法计算量可能达到的最大值；算法的平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

对算法时间复杂度的度量，人们更关心的是最坏情况下和平均情况下的时间复杂度。然而在很多情况下，算法的平均时间复杂度难于确定。因此，通常只讨论算法在最坏情况下的时间复杂度，即分析在最坏情况下，算法执行时间的上界。在本书后面内容中讨论的时间复杂度，除特别指明外，均指最坏情况下的时间复杂度。

1.4.4　算法的空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐近空间复杂度（Space Complexity）作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模n的函数，记作：

S(n) = O(f (n))
一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)，本节中前面的示例都是如此。有的算法需要占用临时的工作单元数与问题规模n有关，如第8章介绍的归并排序算法就属于这种情况。

1.5 小 结

本章介绍了数据结构的基本概念和术语，以及算法和算法时间复杂度的分析方法。主要内容如下。

（1）数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作的学科。
（2）数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。
① 逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。根据数据元素之间关系的不同特性，通常有四类基本逻辑结构：集合结构、线性结构、树形结构和图状结构。
② 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：顺序存储结构和链式存储结构。
（3）抽象数据类型是指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合，以及对数据对象的基本操作的集合。
（4）算法是为了解决某类问题而规定的一个有限长的操作序列。算法具有五个特性：有穷性、确定性、可行性、输入和输出。一个算法的优劣应该从以下四方面来评价：正确性、可读性、健壮性和高效性。
（5）算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐近时间复杂度，T(n) = O(f(n))，它表示随着问题规模 n 的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。

学完本章后，要求掌握数据结构相关的基本概念，包括数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构等；重点掌握数据结构所含两个层次的具体含义及其相互关系；了解抽象数据类型的定义、表示与实现方法；了解算法的特性和评价标准；重点掌握算法时间复杂度的分析方法。