概述

  • 程序开发过程要求我们做到两点：
    • 高效的数据描述
    • 步骤合理，可用程序实现的算法设计
  • 要做到第一点，必须具备数据结构领域的专门知识
  • 要做到第二点，必须具备算法设计领域的专门知识

第一张 C++回顾

第二章 程序性能分析

概述

  • 程序最重要的属性是正确性。一个程序，如果不能正确的实现算法，他就没有什么用处。
  • 我们用程序性能(program performance)来指一个程序对内存和时间的需求。要对数据结构和算法设计方法给予应用的评价，就必须能够计算程序性能。
  • 我们用操作数和执行步数来估计程序的运行时间。用符号法来分别描述程序在最好，最坏和平均情况下的运行时间。
  • 本章开发了很多应用程序，这些程序在以后的章节中是很有用处的，他们是
    • 数组元素的查找
    • 数组元素的排序：排列排序，选择排序，冒泡排序和插入排序
  • 基于霍纳法则的多项式计算
  • 矩阵加法，转置和乘法

什么是程序性能

  • 所谓程序性能(performance of a program)是指运行这个程序所需要的内存和时间的多少。我们用两种方法来确定一个程序的性能，一个是分析方法，另一个是实验方法。在性能分析(performance analysis)时，采用分析方法，而在性能测量(performance measurement)时，使用实验方法。

  • 所谓一个程序的空间复杂度(space complexity)是指该程序的运行所需内存的大小。我们对程序的空间复杂度感兴趣的主要原因如下
    • 如果一个程序要运行在一个多用户计算机系统中，那么我们需要指明该程序所需要内存的大小
    • 在任何一个计算机系统上运行程序，都需要知道是否有足够的内存可以用来运行该程序
    • 一个问题可能有若干个解决方案，他们对内存的需求各不相同
    • 利用空间复杂度，我们可以估算一个程序所能解决的问题最大可以是什么规模。
  • 所谓程序的时间复杂度(time complexity)是指运行程序所需要的时间。我们对程序的时间复杂度感兴趣的主要原因如下
    • 有些计算机需要用户提供程序运行时间的上限，一旦达到了这个上限，程序将被强制结束。
    • 正在开发的程序可能需要一个令人满意的实时响应。
    • 如果一个问题有多种解决方案，那么具体采用哪一种方案，主要根据这些方案的性能差异。对于各种方案的时间和空间性能，我们将采用加权测量方式进行评价。

空间复杂度

  • 程序所需要的空间主要由以下部分构成
    • 指令空间(instruction space), 是指编译之后的程序所需要的存储空间
    • 数据空间(data space), 是指所有常量和变量所需要的存储空间。它有两个部分构成
      • 常量和简单变量所需要的存储空间
      • 动态数组和动态类实例等动态对象所需要的空间
    • 环境栈空间(environment stack space)，是用来保存暂停的函数和方法在恢复运行时所需要的信息。
  • 指令空间的数量取决于如下因素
    • 把程序转换成机器代码的编译器
    • 在编译时的编译器选项
    • 目标计算机
  • 在决定最终代码需要多少空间的时候，编译器是一个最重要的因素。
  • 即使采用相同的编译器，编译后的程序代码也可能不同。因为一个编译器可能具备优化选项。

  • 编译器的覆盖选项也可以显著的减少程序空间。在覆盖模式下，空间仅分配给当前正在执行的程序模块。调用一个新模块需要从磁盘或者其他设备中读取，新模块代码将覆盖原模块的代码。因此，程序所需要的空间便是最大模块所需要的空间，而不是所有模块所需要的空间之和。

  • 对各种数据类型，C++语言并没有指定他们的空间大小，只是大多数C++编译器有相应的空间分配。
  • 一个结构变量的空间大小是每个结构成员所需要的空间大小之和。类似的，一个数组的空间大小是数组的长度乘以一个数组元素的空间大小。

  • 当计算分配给一个数组的空间时，我们只关心分配给数组元素的空间。数组a的空间是100个double类型元素所占用的空间。若每个元素空间是8字节，则数组a的空间是800字节。数组maze有rows*cols个int类型的元素，占用的空间是4 * rows * cols字节。

  • 在开始性能分析时，人们通常会忽略环境栈所需要的空间，因为他们不理解函数(特别是递归函数)是如何被调用的以及在函数调用结束时会发生什么。每当一个函数被调用时，下面的数据将被保存在环境栈中
    • 返回地址
    • 正在调用的函数的所有局部变量的值以及形式参数的值(仅对递归函数而言)

  • 值得注意的是，有些编译器，不论对递归函数还是非递归函数，在函数调用时，都会保留局部变量和形参的值，而有些编译器仅对递归函数才会如此。因此实际使用的编译器将影响环境栈所需空间的大小。

  • 程序要处理的问题实例都有一些特征，这些特征都包含着可以决定程序空间大小的因素(例如，输入和输出的数量或相关数的大小)。例如，对n个元素排序的程序，它所需要的空间大小是n的函数，n为其实例特征；将两个n x n矩阵累加的程序，n为其实例特征；把两个m x n矩阵相加的程序，m和n为其实例特征。
  • 相对来说，指令空间的大小受实例特征的影响不大。
  • 可以把一个程序所需要的空间分为两部分
    • 固定部分。它独立于实例特征。这一部分通常包括指令空间(即代码空间)，简单变量空间和常量空间等
    • 可变部分。它由动态分配空间构成和递归栈空间构成。前者在某种程度上依赖实例特征，而后者主要依赖实例特征。
  • 任意程序P所需要的空间可以表示为： c + Sp(实例特征)
    • 其中c是一个常量，表示空间需要的固定部分，Sp表示空间需求的可变部分。
  • 在分析一个程序的空间复杂度时，我们将集中计算Sp对任意给定的问题，我们首先要确定哪些实例特征可以用来估算空间需求。选择实例特征是一个很具体的问题，我们需要求助于实际的例子来说明各种可能的情况。一般来说，我们的选择仅限于程序输入和输出的规模。有时我们也会对数据项之间的关系进行复杂的估算。

时间复杂度

  • 用分析方法确定一个程序的运行时间是复杂的，因此只能估算运行时间。而且有两个比较容易控制的方法
    • 找出一个或多个关键操作，确定他们的执行时间
    • 确定程序总的步数
  • 估算一个程序或函数的时间复杂度，一种方法是选择一种或者多种关键操作，例如加，乘，比较等，然后 确定每一种操作的执行次数。使用这种方法成功与否取决于是否能够找到耗时最大的操作。

第三章 渐近记法

第四章 性能测量

引言

  • 性能测量(performance measurement)，关注的是一个程序实际需要的空间和时间。
  • C++函数 clock() 来测量时间，它用 滴答 数来计时。在头文件 time.h 中定义了常数 CLOCK_PER_SEC，它记录每秒流逝的 滴答 数，并转换成秒。CLOCK_PER_SEC=1000，滴答一次等于一毫秒。

第五章 线性表-数组描述

  • 从本章开始研究数据结构，一直到第16章为止。第5章和第6章集中研究线性表，但主要是介绍数据的描述方法，即数据在计算机内存和磁盘上的存储方式。在随后的章节中，我们研究其他常用的数据结构描述方法。这些数据结构有矩阵，栈，队列，字典，优先级队列，竞赛树，搜索树和图。
  • C++程序常用的数据描述方法是数组描述和链式描述。线性表可以用来说明这两种方法。

  • STL容器(vector和list)大致相当于线性表描述方法和链式描述方法。STL的类还有很多其他的方法。在建立线性表的数组描述和链式描述中，我们使用的函数名和签名与STL代码所使用的相同。

  • 数组描述方法将元素存储在一个数组中，用一个数学公式来确定每个元素存储的位置，即在数组中的索引。这是最简单的一种存储方式，所有元素依次存储在一片连续的存储空间中，这就是通常所说的顺序表。
  • 本章引用的数据结构的概念如下
    • 抽象数据类型和相应的C++抽象类
    • 线性表
    • 变长数组和数组容量倍增
    • 数组描述
    • 数据结构迭代器
  • 本章新增的C++概念
    • 抽象类
    • 迭代器

数据对象和数据结构

  • 数据对象(data object)是一组实例或者值，例如 
    1
2

    boolean = {false, true};
digit = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  • boolean, digit都是数据对象，true和false是boolean的实例，而0，1—9是digit的实例。
  • 数据对象的一个实例，要么是一个不可再分的原子，要么是由另一个数据对象的实例作为成员复合而成。对后一种情形，用元素(element)来表示这些成员。

  • 数据对象的实例以及构成实例的元素通常都有某种相关性。例如，自然数0是最小的自然数，1是仅比0大的自然数。在串good中，g是第一个字母，o是第二个和第三个字母，而d是最后一个字母。

  • 数据结构(data structure)是一个数据对象，同时这个对象的实例以及构成实例的元素都存在着联系，而且这些联系由相关的函数来规定。
  • 研究数据结构，关心的是数据对象(实际上是实例)的描述以及相关函数的具体实现。数据对象描述的好，函数的实现就会高效。

线性表数据结构

  • 线性表(linear list)也称有序表(ordered list)，它的每一个实例都是元素的一个有序集合。

  • 一个线性表可以用一个抽象数据类型(abstract data type, ADT)来说明，既说明它的实例，也说明对他的操作。抽象数据类型的说明独立于任何程序语言的描述。所有对抽象数据类型的语言描述必须满足抽象数据类型的说明，抽象数据类型的说明保证了程序语言描述的有效性。另外，所有满足抽象数据类型说明的语言描述，都可以在应用中替换使用。

数组描述

  • 在数组描述(array representation)中，用数组来存储线性表的元素。虽然可以用一个数组存储若干个线性表的实例，但是用不同数组存储每个实例更加容易一些。我们可以用一个数学公式来确定一个线性表的元素在数组中的位置。
  • 假定使用一个一维数组element来存储线性表的元素。数组element的位置有 element[0] — element[arrayLength - 1]，其中arrayLength是数组长度或者容量。数组的每一个位置都可以存储线性表的一个元素。我们需要一个映射，使线性表的一个元素对应数组的一个位置。线性表的第0个元素在数组的什么位置？线性表的最后一个元素在数组的什么位置？这种映射可以用下面的一个公式来表示
    • location(i) = i
  • 一维数组a，线性表元素存储在a[0:n-1]中，要增加或者减少这个数组的长度，首先要建立一个具有新长度的数组，然后把数组a的元素复制到这个新数组，最后改变数组a的值，使它能够引用到新数组。
  • 当数组满而需要加大数组长度时，数组长度常常是要加倍的。这个过程称为数组倍增(array doubling)。数组倍增的时间，从渐近意义上考量，不会大于元素插入的总时间。

  • 为什么数组长度不是增加1或2，而是要加倍呢？数组长度每次增加1或2，虽然不影响插入操作的最坏时间复杂度，但是影响连续插入时的渐近时间复杂度。

  • 定理：如果我们总是按一个乘法因子来增加数组长度，那么实施一系列线性表的操作所需要的时间与不用改变数组长度时相比，至多增加一个常数因子。

C++ 迭代器

  • 一个迭代器(iterator)是一个指针，指向对象的一个元素(例如，一个指向数组元素的指针)。顾名思义，一个迭代器可以用来逐个访问对象的所有元素。

  • 迭代器是编写C++通用算法的基础概念。STL的copy函数便是用来复制任何具有迭代器的对象的元素。

  • 为了简化迭代器的开发和基于迭代器的通用算法的分类，C++的STL定义了5中迭代器：
    • 输入，输出，向前，双向和随机访问
  • 所有迭代器都具备操作符 == ， != 和解引用操作符 *
  • 另外，输入迭代器还提供了对其指向元素的只读操作以及前++和后++操作符。输出迭代器提供了对其指向元素的写操作和++操作符。向前迭代器具有++操作符，而双向迭代器既具有++操作符也具有–操作符。随机访问迭代器是最一般的迭代器，它既可以随意的实现跳跃移动，也可以通过指针算术运算来实现跳跃移动。

vector的描述

  • STL提供了一个基于数组的类 vector。

第六章 链式描述

  • 用数组描述线性表是很自然的，因此你可能以为没有其他的描述方法了。
  • 在链式描述中，线性表的元素在内存中的存储位置是随即的。每个元素都有一个明确的指针或链(指针和链是一个意思)指向线性表的下一个元素的位置(即地址)
  • 在基于数组的描述中，元素的地质是由数学公式决定的。而在链式描述中，元素的地址是随即分布的。
  • STL的容器类list使用带有头节点的双向循环链表来描述实例。它的方法与vector的方法具有相同的签名和操作。因此，他的erase和insert的签名和抽象类型linearList的要求不同，然而和vector一样，它可以用来设计从抽象类linearList的方法具有相同的签名和操作。

单向链表

  • 描述
    • 在链式描述中，数据对象实例的每一个元素都用一个单元或节点来描述。节点不必是数组成员，因此不是用公式来确定元素的位置。取而代之的是，每一个节点都明确包含另一个相关节点的位置信息，这个信息称为链(link)或指针(pointer)
    • 在对这个线性表的一个可能的链式描述中，每个元素都在一个单独的节点中描述，每一个节点都有一个链域，它的值是线性表的下一个元素的位置，即地址。
    • 一般来说，为了找到索引为theIndex的元素，需要从firstNode开始，跟踪theIndex个指针才能找到。

  • 每一个节点只有一个链，这种结构称为单向链表(singly linked list)。链表从左到右，每一个节点(最后一个节点除外)都链接着下一个节点，最后一个节点的链阈值为NULL。这样的结构也称为链条(chain)

  • 结构chainNode
    • 为了用链表描述线性表，我们要定义一个结构chainNode和一个类chain。
  • 类chain
    • 类chain用单向链表实现了线性表，其中最后一个节点的指针域为NULL，即它用单向链接的一组节点实现线性表。

循环链表和头节点

  • 两条措施，可以使链表的应用代码简洁和高效
    • 把线性表描述成一个单向循环链表(singly linked circular list)(简称循环链表)，而不是单向链表
    • 在链表的前面增加一个节点，称为头节点(header node)。只要将单向链表的尾节点与头节点链接起来，单向链表就成为循环链表。

双向链表

  • 对于线性表的大多数应用来说，采用链表和/或循环链表已经足够了。然而，对于有些应用，如果每个元素节点既有一个指向后继的指针，又有一个指向前驱的指针，就会更加方便。
  • 双向链表(doubly linked list)便是这样一个有序的节点序列，其中每个节点都有两个指针nest和previous。
    • next指针指向右边节点(如果存在)
    • previous指针指向左边节点(如果存在)

第七章 数组和矩阵

  • 在实际应用中，数据通常以表的形式出现。尽管用数组来描述表是最自然的方式，但为了减少程序所需的时间和空间，经常采用自定义的描述方式。
  • 本章首先检查了多维数组的行主描述方式和列主描述方式。这些描述方式把多维数组映射成一维数组。
  • 矩阵经常用二维数组来表示。然后，矩阵的索引通过从1开始，而C++的二维数组是从0开始。矩阵的操作有加法，减法和转置，但是C++的二维数组不支持这些操作。因此我们开发了类matrix，它与矩阵的关系密切
  • 我们还要考察具有特殊结构的矩阵，例如对角矩阵，三对角矩阵，三角矩阵和对陈矩阵。关于这些矩阵的描述方法，自定义数组与二维数组相比，不仅大大减少了存储空间安，也减少了大多数矩阵操作的运行时间。

数组

  • 抽象数据类型
  • 一个数组的每一个实例都是形如(索引，值)的数对集合，其中任意两个数对的索引(index)都不相同。有关数组的操作如下
    • 取值： 对一个给定的索引，取对应数对中的值
    • 存值： 把一个新数对加到数对集合中。如果已存在一个索引相同的数对，就用新数对覆盖
  • 这两个操作定义了抽象数据类型array

行主映射和列主映射

  • 数组的应用需要我们把数组元素序列化，即按一维顺序排列。例如，数组元素只能一次输出或输入一个。因此，我们必须确定一个输入或输出的顺序。
  • 从第一行开始，依次对每一行的索引从左至右连续编号。它把二维数组的索引映射为 [0, n-1]中的数，这种映射方式称为行主映射(row major mapping)。索引对应的数称为行主次序
  • 另一种映射方式，称为列主映射(column major mapping)。在列主映射中，对索引的编号从最左列开始，依次对每一列的索引从上到下连续编号。

矩阵

  • 一个m * n的矩阵(matrix)是一个m行，n列的表，m和n是矩阵的维数(dimension)
  • 矩阵通常用来组织数据。
  • 矩阵最常见的操作是矩阵转置，矩阵相加，矩阵相乘。
  • 两个矩阵仅当维数相同时(即它们的行数和列数都分别相等)才可以相加。两个m * n的矩阵A和B相加之后是一个m * n的矩阵C

  • 一个m * n的矩阵A和一个q * p的矩阵B，只有当A的列数等于B的行数(即n=q)时，才可以相乘AB。AB的结果是一个m * p的矩阵C

  • 特殊矩阵
    • 方阵(square matrix)是行数和列数相同的矩阵。一些常用的特殊方阵如下
    • 对角矩阵(diagonal)
    • 三对角矩阵(tridiagonal)
    • 下三角矩阵(lower triangular)
    • 上三角矩阵(upper triangular)
    • 对陈矩阵(symmetric)
  • 一个m * n的矩阵，如果大多数元素都是0,则称为稀疏矩阵(spare matrix)。一个矩阵如果不是稀疏的，就成为稠密矩阵(dense matrix)

第八章 栈

  • 栈和队列很可能是应用频率最高的数据结构。在第五章和第六章曾经广泛研究了线性表和有序表数据结构，而栈和队列是它们的限制版。

  • 栈和队列的应用广泛，以至于C++的标准类模板库STL都提供了用数组实现的栈和队列。

  • 把线性表的插入和删除操作限制在同一端进行，就得到栈数据结构。因此，栈是一个后进先出(last-in-first-out, FIFO)的数据结构。因为栈是一种特殊的线性表，所以从相应的线性表类派生出栈类是很自然的事情。

定义和应用

  • 栈(stack)是一种特殊的线性表，其插入(也称入栈或压栈)和删除(也称出栈或弹栈)操作都在表的同一端进行。这一端称为栈顶(top),另一端称为栈底(bottom)

  • 计算机是如何执行递归函数？
    • 使用递归工作栈(recursion stack)。当一个函数被调用时，一个返回地址(即被调函数一旦执行完，接下去要执行的程序指令的地址)和被调函数的局部变量和形参的值都要存储在递归工作栈中。当执行一次返回时，被调函数的局部变量和形参的值被恢复为调用之前的值(这些值存储在递归工作栈的顶部)，而且程序从返回地址处继续执行，这个返回地址也存储在递归工作栈的顶部。
  • 抽象数据类型 
    1
2
3
4
5
6
7
8
9
10
11

    template<class T>
class stack
{
public:
  virtual ~stack();
  virtual bool empty() const = 0; // 返回true，当且仅当栈为空
  virtual int size() const = 0;  // 返回栈中元素个数
  virtual T& top() = 0;  // 返回栈顶元素的引用
  virtual void pop() = 0;  // 删除栈顶元素
  virtual void push(const T& theElement) = 0;  // 将元素theElement压入栈顶
};