第1章 绪论

• 早期的计算机主要用于数值计算，现在，计算机主要用于非数值计算，包括处理字符、表格和图像等具有一定结构的数据。
• 如何合理地组织数据、高效地处理数据，这就是 “数据结构” 主要研究的问题。

1.1 数据结构的研究内容

• 计算机主要用千数值计算时，一般要经过如下几个步骤:首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。
• 数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型。
• 非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
• 人们普遍认为程序设计的实质就是对所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好的算法，著名科学家Wirth教授的《算法喽戏§ 结构=程序》正是这种观点的集中体现。

1.2 基本概念和术语

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

• 数据 (Data)是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本 编辑中用到的字符串，多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。
• 数据元素 (Data Element) 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。数据元素用千完整地描述一个对象，如前一节示例中的一名学生记录，树中棋盘的一个格局(状态)，以及图中的一个顶点等。
• 数据项 (Data Item) 是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
• 数据对象 (Data Object) 是性质相同的数据元素的集合，是数据的一个子集。例如:整数数据对象是集合N= {O,士1' 士2,...},字母字符数据对象是集合C= {'A','B',...，'Z','a','b', ...，'z'}, 学生基本信息表也可以是一个数据对象。

1.2.2 数据结构

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

1. 逻辑结构

• 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。可以看作是从具体问题抽象出来的数学模型。
• 逻辑结构有两个要素: 一是数据元素;二是关系。关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构：集合结构、线性结构、树结构、图结构，它们的复杂程度依次递进。
• 其中集合结构、树结构和图结构都属于非线性结构。
• 线性结构包括线性表(典型的线性结构，如例1.1中的学生基本信息表)、栈和队列(具有特殊限制的线性表，数据操作只能在表的一端或两端进行)、字符串(也是特殊的线性表，其特殊性表现在它的数据元素仅由一个字符组成)、数组(是线性表的推广，它的数据元素是一个线性表)、广义表(也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是单元素，或者是线性表)。
• 非线性结构包括树(具有多个分支的层次结构)和二叉树(具有两个分支的层次结构)、有向图(一种图结构，边是顶点的有序对)和无向图(另一种图结构，边是顶点的无序对)。这几种逻辑结构可以用一个层次图描述，如下图所示：

2. 存储结构

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

  1. 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助 程序设计语言的数组类型来描述。对于前面的 “学生基本信息表”， 假定每个结点(学生记录) 占用 50 个存储单元，数据从 0 号单元开始由低地址向高地址方向存储，对应的顺序存储结构如下图所示：

     
     

  2. 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用千存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
     假定给前面的 “学生基本信息表” 中的每个结点附加一个 “下一个结点地址"，即后继指针字段，用于存放后继结点的首地址，则可得到如表1.3所示的链式存储结构。从表中可以看出，每个结点占用两个连续的存储单元，一个存放结点的信息，另一个存放后继结点的首地址。

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

1. 数据类型

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

2. 抽象数据类型

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

ADT抽象数据类型名(
    数据对象:(数据对象的定义〉 
    数据关系:(数据关系的定义〉
    基本操作:(基本操作的定义〉
IADT抽象数据类型名

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

• 最终表示和实现抽象数据类型，最好用面向对象的方法，比如用 C++语言的 类描述比较方便、有效

1.4 算法和算法分析

1.4.1 算法的定义及特性

• 算法 (Algorithm) 是为了解决某类问题而规定的一个有限长的操作序列。
• 一个算法必须满足以下五个重要特性。
  • 有穷性。一个算法必须总是在执行有穷步后结束
  • 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性
  • 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
  • 输入。一个算法有零个或多个输入。
  • 输出。一个算法有一个或多个输出

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

• 一个算法的优劣应该从以下几方面来评价。
  • 正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
  • 可读性。一个好的算法，首先应便千人们理解和相互交流，其次才是机器可执行性。
  • 健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
  • 高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量;空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

1.4.3 算法的时间复杂度

• 衡量算法效率的方法主要有两类:事后统计一法和事前分析估算法。事后统计法需要先将算法实现，然后测算其时间和空间开销。我们通常采用事前分析估算法，通过计算算法的渐近复杂度来衡量算法的效率。

  1. 问题规模和语句频度

     • 不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题规模 是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。问题规模n对不 同的问题含义 不同，例如，在排序运算中n为参加排序的记录数，在树的有关运算中n为树的结点个数，在图的有关运算中n为图的顶点数或边数。显然，n越大算法的执行时间越长。
     • 一个算法的执行时间大致上等千其所有语句执行时间的总和， 而语句的执行时间则为该条语 句的重复执行次数 和执行一次所需时间的乘积。
     • 一条语句的重复执行次数称作语句频度(FrequencyCount)。
     • 由千语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行， 因此语句执行一次实际所需的具体时间是与机器的软、 硬件环境(如机器速度、 编译程序质量等)密切相 关的。 所以，所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计， 从中得到算法执行时间的信息。
     • 设每条语句执行一次所需的时间均是单位时间， 则一个算法的执行时间可用该算法中所有语句频度之和来度量。

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

     • 对于较简单的算法， 可以直接计算出算法中所有语句的频度，但对于稍微复杂一 些的算法， 则通常是 比较困难的，因此， 为了客观 地反映一个算法的执行时间， 可以只用算法中的 “基本语句" 的执行次数来度量算法的工作量。所谓 “ 基本语句 ” 指的是算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。 通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。 这种情况下， 我们只需要考虑当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶。如例1.4矩阵的乘积算法，当n趋向无穷大时，显然有
     
     • 即当n充分大时，j(n)和n³之比是一个不等千零的常数。 即j(n)和n³ 是同阶的， 或者说j(n)和n³ 的数量级(O rder ofMagnitude)相同。在这里，我们用"O"来表示数量级，记作T(n) = 0(f(n)) = O(n³)。由此我们可以给出下述算法时间复杂度的定义。
     • 一般情况下， 算法中基本语句重复执行的次数是问题规模n的某个函数j(n), 算法的时间量度记作：T(n)= O(f(n))
     • 它 表示随问题规模n的增大， 算法执行时间的增长率 和 f(n) 增长率相同， 称做算法的渐近时间复杂度， 简称时间复杂度(Time Complexity)。
     • 数学符号"O" 的严格定义为:若T(n)和f(n) 是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n₀,使得当n>=n₀。时，都满足0<=T(n)<=Cj(n)。
     • 该定义说明了函数T(n)和j(n)具有相同的增长趋势，并且T(n)的增长至多趋向于函数j(n)的增长。号"O"用来描述增长率的上限，它表示当问题规模n>n。时，算法的执行时间不会超过j(n)，其直观的含义如图16. 所示。
     

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

     • 分析算法时间复杂度的基本方法为:找出所有语句中语句频度最大的那条语句作为基本语句， 计算基本语句的频度得到问题规模n的某个函数j(n), 取其数量级用符号"O"表示即可。具体计算数量级时， 可以遵循以下定理。
       • 定理 1.1 若f(n)=a_mn^m+a_m-1n^m-1+...+a₁n+a₀是一个m次多项式， 则T(n)=O(n^m)。
       • 定理 1.1说明， 在计算算法时间复杂度时， 可以忽略所有低次幕项和最高次幕的系数， 这样
         可以简化算法分析， 也体现出了增长率的含义。
       • 如果算法的执行时间不随问题规模n的增加而增长，算法中语句频度就是某个常数。即使这个常数再大，算法的时间复杂度都是 0(1)。例如， 上面的程序作如下改动: for(i=O;i<lOOOO;i++) {x++;s=0;}，算法的时间复杂度仍然为 O(1)。
       • 多数情况下， 当有若干个循环语句时，算法的时间复杂度是由最深层循环内的基本语句的频度f(n)决定的。
       • 常见的时间复杂度按数量级递增排列依次为:常量阶O(1) 、对数阶O(log₂n) 、线性阶O(n) 、线性对数阶O(nlog₂n)、平方阶O(n²)、立方阶O(n³)、......、 K次方阶 O(n^k) 、指数阶 0(2ⁿ)等。应该尽可能选择使用多项式阶O(n^k)的算法，而避免使用指数阶的算法。
     • 称算法在最好情况下的时间复杂度为最好时间复杂度，指的是算法计算量可能达到的最小值; 称算法在最坏情况下的时间复杂度为最坏时间复杂度，指的是算法计算量可能达到的最大值;算 法的平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的
       加权平均值。

1.4.4 算法的空间复杂度

• 关千算法的存储空间需求，类似千算法的时间复杂度，我们采用渐近空间复杂度(Space Complexity)作为算法所需存储空间的扯度，简称空间复杂度，它也是问题规模n的函数，记作:S(n)=O(f(n))。
• 一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对千输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。若算法执行时所需要的辅助空间相对千输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)，本节中前面的示例都是如此。有的算法需要占用临时的工作单元数与问题规模n有关，如第8章介绍的归并排序算法就属于这种情况。
• 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间，即可能会使空间复杂度的性能变差，反之亦然。不过，通常情况下，鉴于运算空间较为充足，人们都以算法的时间复杂度作为算法优劣的衡址指标。