数据结构笔记

《数据结构（C语言版）》（严蔚敏，清华大学出版社）笔记

具体算法参见数据结构实验。

第1章 绪论

1. 计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为编写出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。
2. 数据的存储结构分为：
   • 顺序存储（如数组）
   • 链式存储（如链表）
   • 索引存储
   • 散列存储（如哈希表）
3. 数据的逻辑结构分为：
   • 线性结构
     • 一般线性表
       • 顺序表
       • 链表
     • 栈（受限线性表）
       • 顺序栈
       • 链栈
     • 队列（受限线性表）
       • 循环队列
       • 链队列
     • 串（受限线性表）
     • 数组（线性表推广）
     • 广义表（线性表推广）
   • 非线性结构
     • 集合
     • 树
       • 一般树
       • 二叉树
     • 图
       • 有向图
       • 无向图
4. 算法定义在逻辑结构上，实现在存储结构上。

1.1 什么是数据结构

1. 一般来说，用计算机解决一个具体问题时，首先需要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到最终解答。

2. 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些对象之间含有的关系，然后用数学语言加以描述，数学语言包括线性方程组、微分方程等。

3. 但更多的非数值计算问题无法用数学方程加以描述，如图书馆的书目检索系统自动化问题（线性结构、表）、计算机和人对弈问题（非线性结构、树）、多叉路口交通灯的管理问题（图）等。

4. 可以看出描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

   

5. 在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他应用程序和大型应用程序的重要基础。

1.2 基本概念和术语

1. 数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，包括图像、声音等。它是计算机程序加工的“原料”。

2. 数据元素（data element）是数据的基本单位，可由若干个数据项（data item）组成。数据项是数据的不可分割的最小单位。

3. 数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。

4. 数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合，可以分为4类基本结构：集合（同类）、线性结构（一对一）、树形结构（一对多）和图状结构（网状结构，多对多）。

5. 数据结构的形式定义为：数据结构是一个二元组Data Structure=(D,S)，D是数据元素的有限集，S是D上关系的有限集。

6. 上面提到的“关系”都是数据元素之间的逻辑关系，又称为数据的逻辑结构。然而还需要研究这种结构在计算机中是如何实现的，即其物理结构（存储结构）。

7. 在计算机中，可以用若干位的串表示一个数据元素（如8位二进制表示一个字符），称这个位串为元素（element）或结点（node）。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域（data field）。

8. 数据元素之间的关系在计算机中可表示为顺序映像和非顺序映像，对应顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，非顺序映像的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。

9. 数据的逻辑结构和物理结构密切相关，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的逻辑（物理）结构。

10. 将C语言看成是一个执行C指令和C数据类型的虚拟处理器，后续讨论的存储结构就是数据结构在C虚拟处理器中的表示，不妨称之为虚拟存储结构。

11. 数据类型（data type）和数据结构密切相关，是一个值的集合和定义在这个值集上的一组操作的总称。

12. 按照“值”的不同特性，高级程序语言中的数据类型可分为两类：

    • 一类是非结构的原子类型，不可分解，如C中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。
    • 另一类是结构类型，由若干成分按某种结构组成，可以分解，并且其成分可以是结构的，也可以是非结构的。如数组的每个分量可以是整数，也可以是数组等。

    在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。

13. 实际上，在计算机中，数据类型的概念并非局限于高级语言中，每个处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）都提供了一组原子类型或结构类型。

14. 引入“数据类型”，将用户不必了解的细节都封装在类型中，实现了信息的隐蔽。

15. 抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在该模型上的一组操作。

16. 为了提高软件的复用率，近代程序设计方法学指出，一个软件系统的框架应建立在数据之上，而不是建立在操作之上。即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作的细节，而在模块外部使用的只是抽象的数据和抽象的操作。

    显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。

17. 一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。

18. 抽象数据类型的值可以分为：

    • 原子类型（atomic data type）：属原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般已有的固有数据类型足以满足需求。
    • 固定聚合类型（fixed-aggregate data type）：属此类型的变量，其值由确定数目的成分按某种结构组成。如复数是由两个实数依确定的次序关系构成。
    • 可变聚合类型（variable-aggregate data type）：“可变”是指其值的成分的数目不确定。如一个有序整数序列的抽象数据类型中，序列的长度是可变的。

    后两种类型可统称为结构类型。

19. 和数据结构的形式定义相对应，抽象数据类型可用三元组(D,S,P)表示。其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

20. 多形数据类型（polymorphic data type）是指其值的成分不确定的数据类型。

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

1. 抽象数据类型可以通过固有数据类型来表示和实现。

2. 后续使用类C语言描述，精选了C语言的一个核心子集，同时做了若干扩充修改：

   • 预定义常量和类型：

     #define TRUE 1
     #define FALSE 0
     #define OK 1
     #define ERROR 0
     #define INFEASIBLE -1
     #define OVERFLOW -2
     typedef int Status

   • 数据结构的表示（存储结构）用类型定义typedef描述；

   • 当函数返回值为函数结果状态代码时，函数定义为Status类型；

   • exit(异常代码)为异常结束语句；

1.4 算法和算法分析

1.4.1 算法

算法（algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，有下列5个重要特性：

• 有穷性：对任何合法的输入值，在执行有穷步后结束、每一步都可在有穷时间内完成；
• 确定性：每一条指令必须有确切含义，且只有唯一的一条执行路径，对相同的输入只能得出相同的输出；
• 可行性：算法中的操作都是可以通过已经实现的基本运算执行有限次来实现的；
• 输入：有零个或多个的输入；
• 输出：有一个或多个的输出。

1.4.2 算法设计的要求

• 正确性（correctness）：不含语法错误、对于几组输入数据得到满足要求的结果、对于典型苛刻刁难的几组输入数据得到满足要求的结果、对于一切合法的输入数据得到满足要求的结果；
• 可读性（readability）；
• 健壮性（robustness）：对输入的非法数据能适当做出反应或进行处理，不会产生莫名其妙的输出结果；
• 效率与低存储量需求：执行时间短、存储空间小。

1.4.3 算法效率的度量

1. 度量一个程序的执行时间：

   • 事后统计；
   • 事前分析估算，取决于：
     • 算法选用的策略；
     • 问题的规模；
     • 程序语言（语言级别越高，执行效率越低）；
     • 编译产生的机器代码的质量；
     • 机器执行指令的速度。

2. 撇开其他因素，认为算法的“运行工作量”的大小只依赖于问题的规模（用整数量n表示），即是问题规模的函数。

3. 一个算法是由控制结构（顺序、分支和循环）和原操作构成的，所以选取一种原操作，以该操作重复执行的次数作为算法的时间量度。

4. 形式定义：若$f(n)$是正整数$n$的一个函数，则$x_{n}=O(f(n))$表示存在一个正的常数$M$，使得当$n\ge n_{0}$时都满足$|x_{n}|\le M|f(n)|$。

5. 一般情况下，算法中基本操作重复执行的次数是问题规模$n$的某个函数$f(n)$，算法的时间量度记作$$T(n)=O(f(n))$$它表示随问题规模$n$的增大，算法执行时间的增长率和$f(n)$的增长率相同，称做算法的渐近时间复杂度（asymptotic time complexity），简称时间复杂度。

6. 算法原操作的执行次数和包含它的语句的频度（语句重复执行的次数）相同。

7. O(1)、O(n)、O($n^2$)分别被称为常量阶、线性阶和平方阶。下图是常见函数的增长率：

   

8. 一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同操作赋予不同权值。

9. 若难以精确计算基本操作执行次数（或语句频度），则只需求出它关于$n$的增长率或阶即可（增长最快的项）。

10. 若基本操作重复执行的次数随问题的输入数据集不同而不同，则计算它的平均值（期望值），或计算算法在最坏情况下的时间复杂度（上界）。默认计算最坏情况。

11. 算法的时间复杂度取决于问题的规模和待处理数据的状态。

12. 数据的（不可分割的）最小单位是数据项。

13. 算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。这种说法是错误的，因为程序不等同于算法，而是数据结构和算法的结合。

14. 某算法的时间复杂度为O($n^2$)，表明该算法的执行时间与$n^{2}$成正比。

1.4.4 算法的存储空间需求

1. 空间复杂度（space complexity）为算法所需存储空间的量度，记作$$S(n)=O(f(n))$$其中$n$为问题的规模（大小）。
2. 程序除了存储自身的空间外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
3. 若额外空间相对于输入数据量来说是常数，则称此算法为原地工作，如某些排序算法。

第2章 线性表

第2章～第4章讨论线性结构，其特点是：在数据元素的非空有限集中，

• 存在唯一的一个被称作“第一个”的数据元素；
• 存在唯一的一个被称作“最后一个”的数据元素；
• 除第一个外，集合中的每个数据元素均只有一个前驱；
• 除最后一个之外，集合中每个数据元素均只有一个后继。

2.1 线性表的类型定义

1. 线性表（linear list）是最常用且最简单的一种数据结构，是n个数据元素的有限序列，其中的数据元素可以由若干个数据项（item）组成。数据元素常被称为记录（record），含有大量记录的线性表又被称为文件（file）。
2. 同一线性表中的元素必定具有相同的特性，即属同一数据对象，相邻数据元素之间存在着序偶关系（直接前驱、直接后继）。
3. 线性表中元素的个数定义为线性表的长度（为零时称为空表），下标称为数据元素在线性表中的位序。

2.2 线性表的顺序表示和实现

1. 线性表的顺序表示就是用一组地址连续的存储单元依次存储线性表中的数据元素。
2. 不要认为顺序表就是数组。数组是一种顺序表。
3. 注意存储位置的计算。
4. 线性表的这种机内表示称做线性表的顺序存储结构或顺序映像（sequential mapping），以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。
5. 只要确定了存储线性表的起始位置，线性表中任意数据元素都可随机存取，所以线性表的存储结构是一种随机存取的结构。
6. 通常用数组描述数据结构中的顺序存储结构，长度可变时可用动态分配的一维数组。
7. 顺序存储的线性表的插入和删除操作的时间主要耗费在移动元素上（基本操作），移动元素的个数取决于插入或删除元素的位置。
8. 长度为n的顺序表，插入的位置有n+1种，删除的位置有n种。
9. 假设顺序表所有位置的插入和删除是等概率的，则插入和删除的平均移动次数分别为$\frac {n}{2}$和$\frac {n-1}{2}$。
10. 表长为n时，插入和删除表元素的时间复杂度为O(n)，求表长和取某一数据元素的时间复杂度均为O(1)。
11. 若以线性表表示集合并进行集合的各种运算，应先对表中元素进行排序。

2.3 线性表的链式表示和实现

顺序表的优点是可以随机存取表中任一元素，缺点是插入或删除元素时需要移动大量元素。

2.3.1 线性链表

1. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（可连续，也可不连续）。

2. 链表中每个数据元素与其直接后继元素之间的逻辑关系需要单独表示，故每个数据元素需要存储本身的信息，还需要存储一个指示其直接后继的存储位置的信息，这两部分信息组成每一个数据元素的存储映像，称为结点（node）。

3. 结点包括两个域：

   • 数据域：存储数据元素的信息；
   • 指针域：存储直接后继存储位置的信息（称为指针或链）。

4. 若干个结点链结成一个链表，由于每个结点只包含一个指针域，又称线性链表或单链表。

5. 单链表的存取必须从头指针开始进行，最后一个结点的指针为“空”。

6. 线性链表的数据元素之间的逻辑关系由结点中的指针指示，即指针为数据元素之间的逻辑关系的映像。这种存储结构为非顺序映像或链式映像。

7. typedef struct LNode{}LNode, *LinkList;包含两步操作：struct LNode{};和LNode *LinkList;。

8. 有时在单链表的第一个结点之前附设一个结点，称之为头结点。其数据域可以不存储任何信息，也可以存储一些附加信息（如表的长度）；其指针域存储指向第一个结点的指针。

9. 单链表是非随机存取的存储结构。

10. 单链表的插入操作：

    s->next = p->next;
    p->next = s;

    单链表的删除操作：

    p->next = p->next->next;

    仅需修改指针，无需移动元素。首先需要找到插入或删除的位置，故时间复杂度为O(n)。

11. 单链表和顺序表不同，是一种动态结构（malloc分配、free回收）。

12. 归并链表时空间复杂度比顺序表的小，因为无需另建新表的结点空间，只需修改指针以链接成一个链表即可。

13. 也可用一维数组来描述线性链表，此时指针域为int型，即为数组下标。缺点是仍需预先分配一个较大的空间，但仍保留了插入和删除的主要优点。这就是静态链表。

14. 静态链表中，为了辨明数组中哪些分量未被使用，可以将所有未被使用过以及被删除的分量用游标链成一个备用的链表。

2.3.2 循环链表

1. 循环链表（circular linked list）是另一种形式的链式存储结构，特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，从表中任一结点出发均可找到表中其他结点。
2. 循环条件为判断p或p->next是否等于头指针，也可不设头指针，只设尾指针，此时将两个线性表合并成一个线性表时仅需改变两个指针值，时间复杂度为O(1)。

2.3.3 双向链表

1. 单链表的缺点是寻查结点的直接前驱的时间复杂度为O(n)。
2. 双向链表（double linked list）的结点中有两个指针域，分别指向直接后继和直接前驱，也可以有循环表。
3. 双向链表在插入和删除结点时需要修改两个方向上的指针，时间复杂度均为O(n)。
4. 由于链表的空间利用合理，插入和删除时不需要移动等优点，是线性表的首选存储结构。
5. 链表的缺点是求长度时不如顺序表、结点之间的关系用指针表示导致数据元素在线性表中的“位序”的概念已淡化。

2.4 一元多项式的表示及相加

1. 符号多项式的操作已经成为表处理的典型用例：将一元n次多项式按升幂排列时，由n+1个系数唯一确定，它们便构成了一个线性表。
2. 也可以让每个数据元素有两个数据项：系数项和指数项，虽然可能会比上一种方案多存储一倍的数据，但对于次数很高且变化很大的多项式来说，这种表示将大大节省空间。
3. 若只对多项式进行求值等不改变多项式系数和指数的运算，则采用顺序表；否则应采用链表。

第3章 栈和队列

从数据结构角度看，栈和队列是操作受限的线性表，其基本操作是线性表操作的子集，可称为限定性的数据结构。

从数据类型角度看，栈和队列是和线性表大不相同的两类重要的抽象数据类型，广泛应用在各种软件系统中。在面向对象的程序设计中，它们是多型数据类型。

3.1 栈

3.1.1 抽象数据类型栈的定义

1. 栈（stack）是限定仅在表尾进行插入或删除操作的线性表。
2. 表尾端称为栈顶（top），表头端称为栈底（bottom），不含元素的空表称为空栈。
3. 栈的修改是按后进先出的原则进行的，故将栈称为后进先出（last in first out）的线性表，简称LIFO结构。
4. 插入元素的操作称为入栈，删除栈顶元素的操作称为出栈。

3.1.2 栈的表示和实现

1. 和线性表类似，栈也有顺序栈和链栈两种存储表示方法。
2. 顺序栈中栈顶指针为int型，
3. 初始化顺序栈时，可以先分配一个基本容量，再realloc逐段扩大。
4. 链栈的操作是线性表操作的特例，易于实现。

3.2 栈的应用举例

栈结构的后进先出的固有特性使得栈成为程序设计中的有用工具。

3.2.1 数制转换

对于输入的任意一个非负十进制数，打印输出与其等值的八进制数：

void conversion() {
  InitStack(S);
  scanf("%d", N);
  while (N) {
    Push(S, N % 8);
    N /= 8;
  }
  while (!StackEmpty(S)) {
    Pop(S, e);
    printf("%d", e);
  }
}

使用栈而不使用数组的优点是：栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小；用数组不仅掩盖了问题的本质，还会分散精力去考虑数组下标增减等细节问题。

3.2.2 括号匹配的检验

可以用“期待的急迫程度”来描述：当计算机接受了第一个括号后，它期待着与其匹配的括号的出现，不断接受括号，对它们的匹配括号的期待急迫程度也不断改变。

即左括号则入栈，右括号则出栈，最终栈空则说明匹配。

3.2.3 行编辑程序

方便用户在编辑一行文本时实现撤销操作。

3.2.4 迷宫求解

保证在迷宫的任何位置上都能沿原路返回。

3.2.5 表达式求值

“算符优先法”：根据运算优先关系的规定来实现对表达式的编译或解释执行。

任意表达式的组成：

• 操作数（operand）：常数、变量或常量标识符
• 运算符（operator）：算术运算符、关系运算符、逻辑运算符
• 界限符（delimiter）：左右括号、表达式结束符

运算符和界限符统称为算符，构成集合OP（$𝜽_{1}$和$𝜽_{2}$是任意两个相继出现的算符，<、=和>表示优先关系）：

可以用OPTR工作栈寄存运算符，用OPND工作栈寄存操作数和运算结果：

• 首先置操作数栈为空栈，表达式起始符#为运算符栈的栈底元素；
• 依次读入表达式中每个字符，操作数则进OPND栈，运算符则和OPTR栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（OPTR栈的栈顶元素和当前读入的字符均为#）。

相应操作：

• 若读入的运算符比栈顶运算符优先权高，则直接入栈；
• 若读入的运算符比栈顶运算符优先权低，则栈顶运算符出栈；
• 若读入的运算符和栈中运算符优先权相等，则全部出栈。

3.3 栈与递归的实现

1. 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
2. 递归是程序设计中一个强有力的工具：
   • 阶乘函数、2阶Fibonacci数列和Ackerman函数等很多数学函数是递归定义的；
   • 二叉树、广义表等数据结构本身固有的递归特性使得它们的操作可以递归地描述；
   • 八皇后问题、Hanoi塔问题等问题虽然没有明显的递归结构，但用递归求解比迭代求解更简单。
3. 当多个函数构成嵌套调用时，则按照“后调用先返回”的原则，即通过栈来实现。
4. 一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。
5. 为保证递归函数正常运行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区，每一层递归所需信息构成一个“工作记录”。
6. 递归函数结构清晰、程序易读、正确性易证明，给用户编制程序和调试程序带来很大方便。

3.4 队列

3.4.1 抽象数据类型队列的定义

1. 和栈相反，队列（queue）是一种先进先出（first in first out，FIFO）的线性表。

2. 队列只允许在表的一端进行插入，而在另一端删除元素。

3. 队列中允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。

4. 除栈和队列之外，还有一种限定性数据结构是双端队列（deque），限定插入和删除操作在表的两端进行。还可以有输出受限的双端队列和输入受限的双端队列等。

   双端队列实际上在应用程序中远不及栈和队列有用，不做详细讨论。

3.4.2 链队列——队列的链式表示和实现

1. 和线性表类似，队列也有链队列和循环队列两种存储表示。
2. 链队列需要两个指针，分别指向队头和队尾，称为头指针和尾指针。
3. 为便于操作，给链队列添加一个头结点。
4. 一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删时，需对队尾指针重新赋值（指向头结点）。

3.4.3 循环队列——队列的顺序表示和实现

1. 和顺序栈类似，在队列的顺序存储结构中，还需两个指针front和rear（int型）分别指示队头元素和队尾元素的位置。
2. 初始化建空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针增1；每当删除队头元素时，头指针增1。则在非空队列中，头指针始终指向队头元素，尾指针始终指向队尾元素的下一个位置。
3. 由于可以从另一边删除元素，顺序队列和顺序栈的不同之处是：当队尾指针最大时，队列的实际可用空间并未占满。所以可以将顺序队列想象成环状空间，称为循环队列。
4. 可以有两种方法判断队列是否已满：
   • 另设一标志位以区别队列是空还是满；
   • 少用一个存储空间，约定以“队头指针在队尾指针的下一位置上”作为队列呈满状态的标志。
5. C语言中不能动态分配一维数组来实现循环队列，必须设定一个最大队列长度。若不能满足的话，则宜采用链队列。

3.5 离散事件模拟

银行业务的模拟程序。

第4章 串

计算机上的非数值处理的对象基本上是字符串数据。

字符串一般简称为串。

4.1 串类型的定义

1. 串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为$$s=’a_{1}a_{2}…a_{n}(n\ge 0)’$$其中s是串的名，单引号括起来的字符序列是串的值（可以是字母、数字或其他字符），字符的数目称为串的长度（零个字符的串称为空串（null string））。单引号本身不属于串。
2. 串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。
3. 字符在序列中的序号为该字符在串中的位置，子串在主串中的位置是子串的第一个字符在主串中的位置。
4. 只有当两个串的长度相等，且各对应位置的字符都相等时，这两个串才相等。
5. 空格是串的字符集合中的一个元素，由若干个空格组成的串称为空格串（blank string，不是空串），长度为空格的个数。
6. 串的逻辑结构类似于线性表，只不过串的数据对象约束为字符集。
7. 串的操作通常以整体作为操作对象，而不是像线性表一样操作单个元素。

4.2 串的表示和实现

串有3种机内表示方法，如下。

4.2.1 定长顺序存储表示

1. 类似于线性表的顺序存储结构，用一组连续的存储单元存储串值的字符序列。

2. 对串长有两种表示方法：

   • 以下标为0的数组分量存放串的实际长度；

   • 在串值后面加一个不计入串长的结束标记字符（如'\0'）。

     此时串长为隐含值，不便于操作。

3. 串的这种顺序存储结构的操作基于字符序列的复制，时间复杂度基于复制的字符序列的长度。

   而且由于长度受限，可能发生截断，解决办法只有不限定最大长度或动态分配存储空间。

4.2.2 堆分配存储表示

1. 仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配的。

2. C语言中存在一个称之为“堆”的自由存储区，由malloc()和free()函数来管理。

3. 为处理方便，约定串长也作为存储结构的一部分。

4. 串的堆分配存储表示：

   typedef struct {
     char *ch;
     int length;
   }HString;

5. 操作仍基于字符序列的复制，但首先进行内存分配操作。

6. 由于堆分配存储结构的串既有顺序存储结构的优点（处理方便），操作中又对串长没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。

4.2.3 串的块链存储表示

1. 和线性表的链表类似，也可以采用链表方式存储串值。

2. 每个结点可以存放一个字符，也可以存放多个字符（此时结点中包含一个数组）（此时无法占满时补上#或其他的非串值字符）。

3. 为便于联结操作，以链表存储串值时，除头指针外还可附设尾指针指向最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构。不必建立双向链表。

4. 串的存储密度=串值所占的存储位/实际分配的存储位。

   结点大小为1时，存储密度小，运算处理方便，但存储占用量大。

5. 串的链式存储结构对联接等操作有一定方便之处，但因为占用存储量大且操作复杂而不如另外两种存储结构灵活。

4.3 串的模式匹配算法

4.3.1 求子串位置的定位函数Index(S, T, pos)

1. 子串的定位操作通常称做串的模式匹配（其中T称为模式串）。

2. 若用最简单的思路进行定位，则从pos开始比较，若对应位置二者相等则二者指针均后移，若不等则T指针后退至1，S指针后退至本次开始匹配的位置（i-(j-1)）的下一个位置（i-(j-1)+1），继续匹配。

3. 一般情况下，上述算法的时间复杂度为O(n+m)，n和m分别为主串和模式串的长度。

4. 但在某种特殊情况下，如主串为00000000000000000000000000000000000000000000000000001，模式串为00000001时，会发生不断回溯的情况，可以看出算法在最坏情况下的时间复杂度为O(n*m)。

   而且这种情况十分常见，如在只有0、1两种字符的文本串的处理中。

4.3.2 模式匹配的一种改进算法

串的第0位存储长度值，故从1开始计数。

1. 这种改进算法是D.E.Knuth与J.H.Morris和V.R.Pratt同时发现的，故被称为克努特-莫里斯-普拉特操作，简称KMP算法。

2. 此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

3. 改进的思路是：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较：

   

4. 该算法的关键在于，当发生失配时，模式串“向右滑动”可行的距离有多远，即下一次主串的失配字符应与模式串中哪个字符再比较？

5. 假设下一次主串的失配字符应与模式串的第k个字符相比。

   此时主串匹配到i、模式串匹配到j，可知k不会超过j，而且k越小则滑得越远。

   由失配可知主串从i-j+1～i-1和模式串的1～j-1是完全相同的，当然也满足主串的i-k+1～i-1和模式串的j-k+1～j-1是完全相同的。

   既然下一次是i与k相比，那么一定有主串的i-k+1～i-1和模式串的1～k-1完全相同，而且对一切大于k的k'都不满足。正是这个原因才使我们不用比较中间这些字符。

   由这两个角度分析可知，k应满足的条件是：模式串的j-k+1～j-1和1～k-1完全相同，即模式串的头k-1个字符和尾k-1个字符完全相同。

   可以看出，k的取值与主串无关。

6. 由此可知，模式串的每一个j都一一对应这一个k，记next[j]=k，得到模式串的next函数定义：

   • 当j=1时，next[j]=0；
   • 设A={k|1<k<j且1～k-1=j-k+1～j-1}，当集合A不空时，next[j]=max(A)；
   • 其他情况，next[j]=1。

   可以看出，j>1时，第j位的next值为前j-1位长的字符串的前缀和后缀的最大重叠字符个数+1，不存在则为1。

7. 有了next函数，每次若匹配则i和j均增1，失配时则i不变而j退到next[j]位置（若next[j]为零，则i前移1位）。

8. KMP算法如下：

   int Index_KMP(SString S, SString T, int pos) {
     i = pos;
     j = 1;
     while (i <= S[0] && j <= T[0]) {
       if (j == 0 || S[i] == T[j]) {
         ++i;
         ++j;
       } else
         j = next[j];
     }
     if (j > T[0])
       return i - T[0];
     else
       return 0;
   }

9. KMP算法是在已知模式串的next函数值的基础上执行的，那么，如何求得模式串的next函数值呢？

   1. 当j=1时，next[1]=0。

   2. 当j>1时，设next[j]=k（即模式串1～k-1和j-k+1～j-1完全相同）：

      • 此时若第k位和第j位也相同，说明next[j+1]=k+1，代入得next[j+1]=next[j]+1；

      • 此时若第k位和第j位不相同，说明当模式串和自己进行匹配时，在i=j、j=k时出现了失配。此时的“模式串”应退到next[k]处和第j个字符比较：

        • 若比较成功，则说明1～next[k]和j-next[k]+1～j完全相同，即next[j+1]=next[k]+1；

        • 若比较失败，则“模式串”退到next[next[k]]位置和第j个字符比较……（禁止套娃）

          最终直到比较成功（next[j+1]=next[...next[k]...]+1）或无法找到（next[...next[k]...]=0即next[j+1]=1）为止。

   经分析知，只需让模式串和自己进行匹配，若匹配则next[i]=j+1同时i和j均后移；若失配则让第i位和next[j]再进行比较，直到next[j]=0结束套娃：

   void get_next(SString T, int next[]) {
     i = 1;
     next[1] = 0;
     j = 0;
     while (i < T[0]) {
       if (j == 0 || T[i] == T[j]) {
         ++i;
         ++j;
         next[i] = j;
       } else
         j = next[j];
     }
   }

10. 此算法的时间复杂度为O(m)，通常m作为模式串的长度较小，因此对整个匹配算法来说，所增加的这点时间是值得的。

11. 虽然4.3.1节的算法时间复杂度是O(n*m)，但一般情况下实际的执行时间近似于O(n+m)，因此仍被采用。

    KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得更快。而且由于主串的指针不需回溯，所以对输入的庞大的文件很有效，可以边读入边匹配。

12. 上述获得next函数的算法在某些情况下尚有缺陷。因为定义的是每次失配则退到next[j]处，可是如果next[j]处的字符仍和j处的字符相等，我们本可以跳过和next[j]的比较，直接和next[next[j]]比较。即next函数可以做的改进是让next[j]直接等于next[next[j]]（如果仍相等则继续向前）。

    这就是nextval函数：

    void get_nextval(SString T, int next_val[]) {
      i = 1;
      nextval[1] = 0;
      j = 0;
      while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
          ++i;
          ++j;
          if (T[i] != T[j])
            nextval[i] = j;
          else
            nextval[i] = nextval[j];
        } else
          j = nextval[j];
      }
    }

4.4 串操作应用举例

4.4.1 文本编辑

1. 文本编辑的实质是修改字符数据的形式和格式，一般包括串的查找、插入和删除等基本操作。

2. 可以把文本看成一个字符串，称为文本串，页则是文本串的子串，行又是页的子串。

3. 为管理文本串的页和行，编辑程序为文本串建立了相应的页表和行表，即建立了各子串的存储映像。

   页表的每一项给出了页号和该页的起始行号，而行表的每一项则指示每一行的行号、起始地址和该行子串的长度。

4. 文本编辑程序中设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。

4.4.2 建立词索引表

1. 信息检索的主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息，为了提高查找效率，一个重要的问题是建立一个好的索引系统。
2. 按书名检索并不方便，更好的办法是按书名关键词索引。为了便于查询，可设定此索引表为按词典有序的线性表。
3. 设定数据结构：
   • 词表存放关键词，数量有限，故采用顺序表；
   • 索引表为有序表，主要为查找用，为提高查找效率，宜采用顺序表；
   • 索引表中每个索引项包含关键词和书号索引：
     • 关键词为常驻结构，考虑节省存储，采用堆分配存储表示的串类型；
     • 书号索引在索引表的生成过程中逐个插入，且不同关键词的书号索引个数不等，甚至可能相差很多，则宜采用链表。

第5章 数组和广义表

前面讨论的线性结构的数据元素都是非结构的原子类型，即元素的值是不再分解的。

本章讨论的数组和广义表可以看成是线性表的扩展，因为表中的数据元素本身也是一个数据结构。

5.1 数组的定义

1. 和线性表一样，数组的所有数据元素都必须属于同一数据类型。

2. 数组中的每个元素都对应着一组下标（$j_{1},j_{2},…,j_{n}$），每个下标的取值范围是$0\le j_{i}\le b_{i}-1$，$b_{i}$是数组第i维的长度（i=1, 2, …, n）。

   当n=1时，n维数组就退化为定长的线性表。

3. n维数组含有$\prod_{i=1}^{n}b_{i}$个数据元素，每个数据元素都受着n个关系的约束。

   每个关系中，元素$a_{j_{1}j_{2}…j_{n}}$（$0\le j_{i}\le b_{i}-2$）都有一个直接后继元素，因此，就其单个关系而言，这n个关系仍是线性关系。

4. 二维数组可以看成是（每个数据元素也是一个定长线性表的）线性表，同理一个n维数组类型可以定义为（其数据元素为n-1维数组类型的）一维数组类型。

5. 数组一旦被定义，它的维数和维界就不再改变。因此除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。

5.2 数组的顺序表示和实现

1. 由上一条特性，数组自然地采用顺序存储结构表示。

2. 由于存储单元是一维的，所以二维数组有两种存储方式：

   • 以列序为主序（column major order）：

     

   • 以行序为主序（row major order）：

     

   在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构；而在FORTRAN语言中，用的是以列序为主序的存储结构。

3. 假设每个数据元素占L个存储单元，则二维数组A中任一元素$a_{ij}$的存储位置可由下式确定$$LOC(i,j)=LOC(0,0)+(b_{2}\times i+j)L$$式中LOC(0,0)是二维数组A的起始存储位置（$a_{00}$），也称为基地址或基址；$b_{2}$是第二维（每列）的元素个数。

4. 由上，得到n维数组的数据元素存储位置的计算公式：$$LOC(j_{1},j_{2},…,j_{n})=LOC(0,0,…,0)+(\sum_{i=1}^{n-1}j_{i}\prod_{k=i+1}^{n}b_{k}+j_{n})L=LOC(0,0,…,0)+\sum_{i=1}^{n}c_{i}j_{i}$$（$c_{n}=L, c_{i-1}=b_{i}\times c_{i}, 1<i\le n$）即为每一维的位置乘以更高维长度之积，再加上第n维的位置，最后将总和乘以每个数据元素所占的存储单元，加上基地址即为所求的数据元素的存储位置。称为n维数组的映像函数。

5. 数组元素的存储位置是其下标的线性函数，一旦确定了数组各维的长度，$c_{i}$就是常数。

6. 计算各个元素存储位置的时间相等，则存取数组中任一元素的时间也相等。这种存储结构为随机存储结构。

5.3 矩阵的压缩存储

1. 通常用高级语言编制程序时，都是用二维数组来存储矩阵元。但在数值分析中经常出现一些阶数很高的矩阵，且有很多值相同的元素或零元素。为了节省存储空间，可以对这些矩阵进行压缩存储。
2. 压缩存储是指：为多个值相同的元素只分配一个空间、对零元素不分配空间。
3. 若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之称为稀疏矩阵。

5.3.1 特殊矩阵

1. 对于对称矩阵，可以为每一对对称元只分配一个存储空间，不失一般性，我们可以以行序为主序存储在其下三角（包括对角线）中的元。

   这样就可以将$n^2$个元压缩存储到n(n+1)/2个元的空间中。

   这样就可以用大小为n(n+1)/2的一维数组存储n阶对称矩阵。

2. 重点是如何将一维数组下标k与对称矩阵元素(i,j)间建立一一对应的关系（数组从0开始，矩阵从1开始）：

   • 当$i\ge j$时，按下三角存储，上方有i-1行，每行i个元素，共计i(i-1)/2个元素；在本行中是第j个，且数组从0计，所以k=i(i-1)/2+j-1；
   • 当i<j时，i变j，j变i，代入上式，则k=j(j-1)/2+i-1。

3. 称此数组为n阶对称矩阵A的压缩存储：

   

4. 这种压缩方法同样也适用于三角矩阵和对角矩阵。

5. 在对称矩阵、三角矩阵和对角矩阵等特殊矩阵中，非零元的分布都有一个明显的规律，从而可以压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。

6. 若非零元较零元少，且分布没有一定规律，这种矩阵的压缩存储就比特殊矩阵复杂。这就是下面要讨论的稀疏矩阵。

5.3.2 稀疏矩阵

1. 假设在$m\times n$的矩阵中，有t个元素不为零，则矩阵的稀疏因子为$\frac{t}{m\times n}$。当稀疏因子不超过0.05时，称其为稀疏矩阵。

2. 压缩存储是指存储矩阵的非零元。因此，除了存储非零元的值之外，还必须同时记下它的行标和列标（均从1开始）。这样，矩阵的一个非零元和一个三元组$(i,j,a_{ij})$就互相唯一确定了。

   稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

由三元组表示的不同方法可引出稀疏矩阵不同的压缩方法（两个顺序表、一个链表）。

三元组顺序表——转置

1. 三元组顺序表就是以顺序存储结构来表示三元组表。

2. 在顺序表中，三元组以行序为主序排列。这样做将有利于进行某些矩阵运算。

3. 矩阵的转置运算：

   • 将矩阵的行列值相互交换；
   • 将每个三元组中的i和j相互交换；
   • 重排三元组之间的次序。

4. 转置的前两步很容易，关键是第三步。可以有两种处理方法：

   • 按照转置后排好的顺序，依次在转置前的顺序表中找到相应的三元组进行转置。即按照矩阵的列序来进行转置。

     需要遍历顺序表，依次寻找第1列、第2列……第n列的元素，而顺序表开始时是以行序为主序存放的，所以每一列时的行序是按顺序的。

     算法如下：

     Status TransposeSMatrix(TSMatrix M, TSMatrix &T) {
       T.mu = M.nu;
       T.nu = M.mu;
       T.tu = M.tu;
       if (T.tu) {
         q = 1;
         for (col = 1; col <= M.nu; ++col)
           for (p = 1; p <= M.tu; ++p)
             if (M.data[p].j == col) {
               T.data[q].i = M.data[p].j;
               T.data[q].j = M.data[p].i;
               T.data[q].e = M.data[p].e;
               ++q;
             }
       }
       return OK;
     }

     时间复杂度为O(nu·tu)，而一般转置算法的时间复杂度为O(mu·nu)。要想用此算法提高效率，则必须满足tu远小于mu*nu。

   • 按照转置前顺序表中三元组的次序进行转置，并将转置结果置入转置后的顺序表的恰当位置。

     为确定这些位置，应先求得矩阵每一列中非零元的个数，对应转置后的每一行的非零元的个数，进而通过累加求得每一列的第一个非零元在转置后的顺序表中应有的位置。（思路类似于实验17的基数排序）

     附设两个向量：

     • num[col]表示矩阵第col列中非零元的个数；
     • cpot[col]表示矩阵第col列的第一个非零元在转置后的顺序表中的恰当位置。

     显然：

     • cpot[1]=1；
     • cpot[col]=cpot[col-1]+num[col-1]，$2\le col\le nu$。

     这种转置方法称为快速转置，算法如下：

     Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {
       T.mu = M.nu;
       T.nu = M.mu;
       T.tu = M.tu;
       if (T.tu) {
         for (col = 1; col <= M.nu; ++col)
           num[col] = 0;
         for (t = 1; t <= M.tu; ++t)
           ++num[M.data[t].j];
         cpot[1] = 1;
         for (col = 2; col <= M.nu; ++col)
           cpot[col] = cpot[col-1] + num[col-1];
     
         for (p = 1; p <= M.tu; ++p) {
           col = M.data[p].j;
           q = cpot[col];
           T.data[q].i = M.data[p].j;
           T.data[q].j = M.data[p].i;
           T.data[q].e = M.data[p].e;
           ++cpot[col];
         }
       }
       return OK;
     }

     这种算法仅比前一个算法多用了两个辅助向量（可以求完num后直接累加，不必新建cpot，即可只占一个向量的空间）。从时间上看，算法中有4个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O(nu+tu)。就算tu和mu*tu等数量级，其时间复杂度也才为O(mu*nu)，和经典算法的时间复杂度相同。

5. 三元组顺序表又称有序的双下标法，非零元在表中按行序有序存储，便于进行依行顺序处理的矩阵运算。

6. 但是，若想存取某一行的非零元，则必须从头开始进行查找。

行逻辑链接的顺序表——乘法

1. 为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。按照快速转置算法的思想，可以在矩阵的存储结构中创建一个指示“行”信息的辅助数组rpos。这种“带行链接信息”的三元组表就是行逻辑链接的顺序表。

2. 这种方法虽然只是多了一个行的信息，但是在矩阵乘法中可以体现其优越性。

3. M和N分别是m*n和n*s矩阵，经典的矩阵乘法算法的时间复杂度为O(m*n*s)。

4. 若这两个矩阵均为稀疏矩阵并用三元组表存储时，不能使用经典算法。那么如何计算呢？设M*N=Q：

   • 若M(i,k)和N(k,j)有一个值为零，则Q(i,j)为零，无需再进行计算。因此，为了得到非零的乘积，只需在M.data和N.data中找到相应的各对元素（M.data中j和N.data中i相等的各对元素）相乘即可。

     也就是说，对M.data[1..M.tu]中的每个元素(i,k,M(i,k))，找到N.data中所有相应的元素(k,j,N(k,j))并相乘即可。

     为此，需要在N.data中寻找矩阵N的第k行的所有非零元，此时rpos便派上用场了。

   • 由于矩阵Q的每个元素都是乘积之和，所以应对每个元素设一累计和的变量，通过扫描数组M.data，求得相应元素的乘积并累加。

   • 两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。同理，即使两个分量值相乘不为零，其累加值也可能为零。

     所以应对累加后的值进行判断，为零的应舍去。（因为M.data已经是行主序的，所以可以对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去）

   算法如下：

   Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
     if (M.nu != N.mu)
       return ERROR;
     Q.mu = M.mu;
     Q.nu = N.nu;
     Q.tu = 0;
     if (M.tu * N.tu != 0) {
       for (arow = 1; arow <= M.mu; ++arow) {
         ctemp[] = 0;
         Q.rpos[arow] = Q.tu + 1;
         if (arow < M.mu)
           tp = M.rpos[arow+1];
         else
           tp = M.tu + 1;
         for (p = M.rpos[arow]; p < tp; ++p) {
           brow = M.data[p].j;
           if (brow < N.mu)
             t = N.rpos[brow+1];
           else
             t = N.tu + 1;
           for (q = N.rpos[brow]; q < t; ++q) {
             ccol = N.data[q].j;
             ctemp[ccol] += M.data[p].e * N.data[q].e;
           }
         }
         for (ccol = 1; ccol <= Q.nu; ++ccol)
           if (ctemp[ccol]) {
             if (++Q.tu > MAXSIZE)
               return ERROR;
             Q.data[Q.tu] = (arow, ccol, ctemp[ccol]);
           }
       }
     }
     return OK;
   }

5. 此算法的时间复杂度为：

   • 累加器ctemp初始化的时间复杂度为O(M.mu*N.nu)；
   • 求Q的所有非零元的时间复杂度为O(M.tu*N.tu/N.mu)；
   • 进行压缩存储的时间复杂度为O(M.mu*N.nu)。

   因此，总的时间复杂度就是O(M.mu*N.nu+M.tu*N.tu/N.mu)。

6. 若矩阵M和矩阵N的稀疏因子均小于0.05，且M的列数（N的行数）小于1 000，则此算法的时间复杂度相当于O(m*s)。与经典算法的O(m*n*s)相比，这是一个相当理想的结果。

7. 如果事先能估算出所求乘积矩阵Q不再是稀疏矩阵，则以二维数组表示Q，相乘的算法也就更简单了。

十字链表——加法

1. 当进行矩阵加法操作时，由于非零元的插入，会引起顺序表中元素的移动。类似这种运算，矩阵的非零元个数和位置在操作过程中变化较大时，不宜采用顺序存储结构来表示三元组的线性表，应采用链式存储结构表示三元组的线性表。

2. 在链表中，每个非零元可用一个含5个域的结点表示：

   • i：行标
   • j：列标
   • e：非零元的值
   • right：指向同一行的下一个非零元
   • down：指向同一列的下一个非零元

   这样，每行通过right域链接成一个链表，每列通过down域链接成一个链表。

   每个非零元既是某个行链表的一个结点，又是某个列链表的一个结点，整个矩阵构成了一个十字交叉的链表，故称为十字链表。

3. 这样，稀疏矩阵就可以由两个数组表示，它们分别存储行和列链表的头指针：

   

4. 对于m行n列且有t个非零元的稀疏矩阵，创建十字链表的算法的时间复杂度为O(t*s)，s=max{m,n}。因为每建立一个非零元的结点时都要寻查它在行表和列表中的插入位置，对非零元输入的先后次序没任何要求。

   若按以行序为主序的次序依次输入三元组，则建立十字链表的算法可以是O(t)数量级的。

5. 下面讨论如何将矩阵B加到矩阵A上：

   两矩阵相加类似于两一元多项式相加，只不过有行值和列值两个变元。每个结点既在行表中又在列表中，致使插入和删除时指针的修改稍微复杂，故需更多的辅助指针。

   以矩阵A为基准，只可能出现4种情况：

   • 当$a_{ij}$、$b_{ij}$和二者之和均不为零时，$a_{ij}=a_{ij}+b_{ij}$；
   • 当$a_{ij}$、$b_{ij}$均不为零、但二者之和为零时，删除$a_{ij}$结点；
   • 当$a_{ij}$不为零而$b_{ij}$为零时，$a_{ij}$不变；
   • 当$a_{ij}$为零而$b_{ij}$不为零时，插入新结点$a_{ij}$（等于$b_{ij}$）。

   由此，整个运算过程可从矩阵的第一行起逐行进行，每一行都从表头出发，分别找到A和B在该行中的第一个非零元结点后开始比较：

   • 若pa == NULL或pa->j>pb->j，则需在A矩阵的链表中插入一个值为$b_{ij}$的结点。

     注意，此时还需改变同一行中前一结点的right域值，以及同一列中前一结点的down域值。

   • 若pa->j<pb->j，则只要将pa指针往后推进一步。

   • 若pa->j==pb->j：

     • 若pa->e+pb->e!=0，则只要将$a_{ij}+b_{ij}$的值送到pa所指结点的e域即可；

     • 若pa->e+pb->e==0，则需要在A矩阵的链表中删除pa所指的结点。

       注意，此时还需改变同一行中前一结点的right域值，以及同一列中前一结点的down域值。

   为了便于插入和删除结点，还需要设立一些辅助指针：

   • 在A的行链表上设pre指针，指示pa所指结点的前驱结点；
   • 在A的列链表上设hl[j]指针，初始化与每个列链表的头指针相同（hl[j]=chead[j]）。

   进一步描述将矩阵B加到矩阵A上的操作过程：

   • 初始化：

     pa = A.rhead[1];
     pb = B.rhead[1];
     pre = NULL;
     for (j = 1; j < A.nu; ++j)
       hl[j] = A.chead[1];

   • 重复本步骤，依次处理本行结点，直至B的本行中再无非零元的结点（pb==NULL）：

     • 当A的本行中的非零元已处理完，需要在本行插入新的结点p：

       if (pa == NULL || pa->j > pb->j) {
         if (pre == NULL)
           A.rhead[p->i] = p;
         else
           pre->right = p;
         p->right = pa;
         pre = p;
       }

       再在对应列插入此结点p：

       if (!A.chead[p->j] || A.chead[p->j]->i > p->i) {
         p->down = A.chead[p->j];
         A.chead[p->j] = p;
       } else {
         p->down = hl[p->j]->down;
         hl[p->j]->down = p;
       }
       hl[p->j] = p;

     • 第二种情况：

       if (pa != NULL && pa->j < pb->j) {
         pre = pa;
         pa = pa->right;
       }

     • 第三种情况：

       if (pa->j == pb->j)
         pa->e += pb->e;
       
       if (pa->e == 0) {
         if (pre == NULL)
           A.rhead[pa->i] = pa->right;
         else
           pre->right = pa->right;
         p = pa;
         pa = pa->right;
       
         if (A.chead[p->j] == p)
           A.chead[p->j] = hl[p->j] = p->down;
         else
           hl[p->j]->down = p->down;
         free(p);
       }

   • 若本行不是最后一行，则令pa和pb指向下一行的第一个非零元结点，转上一步；否则结束。

6. 从一个结点来看，进行比较、修改指针所需的时间是一个常数；整个运算过程在于对A和B的十字链表逐行扫描，其循环次数主要取决于A和B矩阵中非零元素的个数ta和tb。

   由此，算法的时间复杂度为O(ta+tb)。

5.4 广义表的定义

1. 顾名思义，广义表是线性表的推广，也被称为列表（lists，用复数形式以示与统称的表list的区别）。
2. 广义表广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
3. 广义表一般记作$$LS=(\alpha_{1},\alpha_{2},…,\alpha_{n})$$其中LS是广义表的名称，n、是它的长度。
4. 在线性表中，$a_{i}$只限于是单个元素。而在广义表中，$\alpha_{i}$可以是单个元素（称为原子），也可以是广义表（称为子表）（递归的定义）。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。
5. 当广义表非空时，称第一个元素为它的表头，称其余元素组成的表为它的表尾。
6. E=(a,E)是一个递归的表，长度为2，相当于一个无限的列表。
7. 列表是一个多层次的结构，可为其他列表所共享，可以是递归的表。
8. 表头可以是原子和列表，表尾必定为列表。

5.5 广义表的存储结构

1. 由于广义表中的数据元素可以具有不同的结构，所以难以用顺序存储结构表示，通常采用链式存储结构。

2. 由于列表中的数据元素可能为原子或列表，所以需要两种结构的结点（不同之处用union）。

3. 非空列表可以分解成表头和表尾，故一对确定的表头和表尾可唯一确定列表。

   因此一个表结点可以由3个域组成：

   • 标志域（公共部分，用以区分表结点和原子结点）
   • 指示表头的指针域hp
   • 指示表尾的指针域tp

   一个原子结点只需两个域：

   • 标志域（公共部分，用以区分表结点和原子结点）
   • 值域

4. 设A=()、B=(e)、C=(a,(b,c,d))、D=(A,B,C)、E=(a,E)，则它们的存储结构可以表示为：

   

   可以看出：

   • 空表的表头指针为空，非空列表的表头指针均指向一个表结点；

   • 表结点的hp域指示该表表头（原子/表），tp域指示该表表尾（表/空）；

   • 容易分清列表中原子和子表所在层次：

     

   • 最高层的表结点个数即为列表的长度。

5. 设A=()、B=(e)、C=(a,(b,c,d))、D=(A,B,C)、E=(a,E)，则它们的另一种存储结构可以表示为：

   

   表结点表示不变，原子结点增加tp指针域指向下一个元素结点。

5.6 m元多项式的表示

1. 一般情况下，广义表不使用递归表，也不为其他表所共享。它的特点只是其中的元素可以是另一个广义表，这是它比线性表更灵活的地方，一个实例就是m元多项式的表示。

2. 由于m元多项式中每一项的变化数目的不均匀性和变元信息的重要性，故不适于用线性表表示。

3. 对于m元多项式，可以灵活地分解出一个变元，从而变成一个变元的多项式；随后再分解出第二个变元，等等。

   由此，一个m元多项式首先是它的主变元的（一元）多项式，而其系数又是第二变元的多项式。每个多项式都可看作是由一个变量加上若干个系数指数偶对构成的。

4. 只需在表结点和原子结点中添加指数域，并在原子结点中添加系数域，就可以用广义表表示一个m元多项式了。

5.7 广义表的递归算法

1. 递归函数虽然结构清晰、程序易读、易证明正确性，但有时递归函数的执行效率很低，因此不能一味追求递归，使用递归应扬长避短。
2. 下面以广义表为例，讨论如何利用“分治法”（Divide and Conquer）进行递归算法设计的方法。
3. 和数学归纳法类似，递归定义由基本项和归纳项两部分组成：
   • 基本项描述一个或几个递归过程的终结状态，一般情况下为n=0或n=1；
   • 归纳项描述了如何从当前状态到终结状态的转化。
4. 递归设计的实质是：当一个复杂的问题可以分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可利用和原问题相同的分析处理方法；反之，这些子问题解决了，原问题也就迎刃而解了。
5. 递归函数的设计用的是归纳思维的方法，故设计递归函数时应注意：
   • 严格定义函数的功能和接口（只要接口一致，便可进行递归调用）；
   • 对每一次递归都看成只是一个简单的操作，切忌想得太深太远；
   • 由归纳假设进行归纳证明时绝不能怀疑归纳假设的正确性。

5.7.1 求广义表的深度

1. 广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。

   正如m元多项式中提到的，广义表的深度定义为多项式中变元的个数。

2. 要求广义表的深度，可以求它每个元素的深度：

   • 若为原子，则深度为0；

   • 若为表，则和上述一样处理。

     注意，空表的深度为1。

   可见，求广义表的深度的递归算法有两个终结状态：空表和原子。

   最后在最外层广义表的每个元素的深度中找到最大值并加1，就得到了广义表的深度。

   算法如下：

   int GListDepth(GList L) {
     if (!L)
       return 1;
     if (L->tag == ATOM)
       return 0;
     for (max = 0; pp = L; pp = pp->ptr.tp) {
       dep = GListDepth(pp->ptr.hp);
       if (dep > max)
         max = dep;
     }
     return max + 1;
   }

3. 此算法实际上遍历了整个广义表，过程中求了各子表的深度，最后综合得到广义表的深度：

   

5.7.2 复制广义表

因为一对确定的表头和表尾可唯一确定一个广义表，所以复制广义表时只需分别复制其表头和表尾，然后合成即可。

算法如下（从L复制到T）：

Status CopyGList(GList &T, GList L) {
  if (!L) // null lists
    T = NULL;
  else {
    if (!(T = (GList)malloc(sizeof(GLNode))))
      exit(OVERFLOW);
    T->tag = L->tag;
    if (L->tag == ATOM) // atom
      T->atom = L->atom;
    else { // lists
      CopyGList(T->ptr.hp, L->ptr.hp); // head
      CopyGList(T->ptr.tp, L->ptr.tp); // tail
    }
  }
}

5.7.3 建立广义表的存储结构

1. 上述两种广义表操作的递归算法分别是：

   • 把广义表看成是含有n个并列子表（假设原子也视作子表）的表；
   • 把广义表分解成表头和表尾两部分。

2. 若采用第二种方法存储广义表，只需对表头和表尾存储并进行递归即可，算法和上一节的复制算法极为相似。

3. 若采用第一种方法存储广义表，和求深度的算法类似（设S为广义表字符串）：

   • 基本项：

     • 当S为空表串时，置空广义表；
     • 当S为单字符串时，置空广义表；

   • 归纳项：

     对每一个非空子串建立一个表结点，令其hp域为建立的子表的头指针。其余表结点的尾指针均指向之后的表结点（最后建立的表结点的尾指针为NULL）。

第6章 树和二叉树

前面讨论了线性结构，下面开始讨论一类重要的非线性数据结构——树型结构（重点是二叉树）。

6.1 树的定义和基本术语

1. 树（Tree）是n（n≥0）个结点的有限集：

   • n=0时为空树；
   • 在任意一棵非空树中：
     • 有且仅有一个特定的称为根（Root）的结点（n=1时仅有一个根结点）；
     • n>1时，其余结点可分为若干个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

2. 和广义表的定义类似，树的结构定义也是一个递归的定义，因为在定义中又用到了树的概念，这也是树的固有特性。

3. 树的其他表示形式：

   

4. 一般来说，分等级的分类方案都可用树这种层次结构来表示。

5. 基本术语：

   • 结点：包含一个数据元素和若干个指向其子树的分支；
   • （结点的）度（Degree）：结点拥有的子树的个数；
   • 叶子（Leaf）：度为零的结点，也称终端结点；
   • 分支结点：度不为零的结点，也称非终端结点（除根结点之外的分支结点也称内部结点）；
   • （树的）度：树内各结点的度的最大值；
   • 孩子（Child）：结点的子树的根；
   • 双亲（Parent）：上一条提到的结点（一个结点）；
   • 兄弟（Sibling）：同一个双亲的孩子之间互称兄弟；
   • 祖先：从根到该结点所经分支上的所有结点；
   • 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙；
   • 层次（Level）：从根开始定义，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层；
   • 堂兄弟：双亲在同一层的结点互为堂兄弟；
   • （树的）深度（Depth）：树中结点的最大层次，也称高度；
   • 有序树：树中结点的各子树从左至右是有次序的，不能互换。有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子；
   • 无序树：树中结点的各子树是没有次序的，可以互换；
   • 森林（Forest）：m（m≥0）棵互不相交的树的集合。树中每个结点的子树的集合即为森林。由此，也可以用森林和树的相互递归的定义来描述树。

6.2 二叉树

6.2.1 二叉树的定义

1. 二叉树（Binary Tree）是另一种树型结构：

   • 每个结点至多只有两棵子树（即不存在度大于2的结点）；
   • 子树有左右之分，次序不能任意颠倒。

2. 二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

   即，二叉树可以是空树、可以是只有一个结点的树、可以是根只有左子树的树、可以是根只有右子树的树、可以是一般的二叉树。

3. 完全二叉树和满二叉树是两种特殊形态的二叉树：

   • 一棵深度为$k$且有$2^{k}-1$个结点的二叉树称为满二叉树。

     特点是每一层上的结点数都是最大结点数。

   • 从根结点起，从上到下、从左到右对满二叉树的结点进行连续编号。

     深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。（满二叉树从右下角向左减少）

     特点是

     • 叶子结点只可能在层次最大的两层上出现；
     • 对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。

6.2.2 二叉树的性质

1. 性质1 在二叉树的第$i$层上至多有$2^{i-1} (i\ge 1)$个结点

   等比数列通项公式。

2. 性质2 深度为$k$的二叉树至多有$2^{k}-1 (k\ge 1)$个结点

   等比数列前$k$项和。

3. 性质3 对任何一棵二叉树$T$，如果其叶子结点数为$n_{0}$，度为2的结点数为$n_{2}$，则$n_{0}=n_{2}+1$

   • 从下往上看：结点由度为0、度为1和度为2的结点组成，故结点总数$n=n_{0}+n_{1}+n_{2}$；
   • 从上往下看：除根结点外，每个结点或接受了度为1的结点发出的一个分支，或接受了度为2的结点发出的两个分支，故有$n-1=n_{1}+2n_{2}$。

4. 性质4 具有$n$个结点的完全二叉树的深度为$\lfloor log_{2}n\rfloor +1$

   设深度为$k$：

   • $2^{k-1}-1$是$k-1$层的结点总数上限，故有$n>2^{k-1}-1$；
   • $2^{k}-1$是$k$层的结点总数上限，故有$n\le 2^{k}-1$。

   解得$k-1\le log_{2}n<k$，因为$k$是整数，所以$k=\lfloor log_{2}n\rfloor +1$。

5. 性质5 如果对一棵有$n$个结点的完全二叉树的结点按层序编号（从上到下、从左到右），则对任一结点$i(1\le i\le n)$，有

   • 如果$i=1$，则结点$i$是二叉树的根，无双亲；如果$i>1$，则其双亲PARENT(i)是结点$\lfloor i/2\rfloor$；
   • 如果$2i>n$，则结点$i$无左孩子（结点$i$为叶子结点）；否则其左孩子LCHILD(i)是结点$2i$；
   • 如果$2i+1>n$，则结点$i$无右孩子；否则其右孩子RCHILD(i)是结点$2i+1$。

6.2.3 二叉树的存储结构

1. 顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。若要存储一般二叉树，则用零占位。

2. 链式存储结构：结点至少包含3个域：数据域和左、右指针域(二叉链表）。有时为了便于找到结点的双亲，还可增加一个指向其双亲结点的指针域（三叉链表）。

   链表的头指针指向二叉树的根结点。

   在含有n个结点的二叉链表中有2n-(n-1)=n+1个空链域，可以存储其他有用信息，从而得到另一种链式存储结构——线索链表。

6.3 遍历二叉树和线索二叉树

6.3.1 遍历二叉树

1. 为了在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，提出了遍历二叉树（traversing binary tree）的问题，即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
2. 线性结构的遍历很容易，树这种非线性结构的遍历则不然。所以需要将二叉树排列在一个线性队列上，从而便于遍历。
3. 由于二叉树由根结点、左子树和右子树这三个基本单元组成，因此，若能依次遍历这三部分，便是遍历了整个二叉树。
4. 二叉树的遍历分为先（根）序遍历、中（根）序遍历和后（根）序遍历。
5. 遍历二叉树是二叉树各种操作的基础，可以在遍历过程中求结点的双亲、求结点的孩子、判定结点所在层次等。反之，也可在遍历过程中生成结点，建立二叉树的存储结构。
6. 除了先序、中序和后序遍历，还可从上到下、从左到右按层次进行。
7. 对n个结点的二叉树，遍历算法的时间复杂度为O(n)，空间复杂度也为O(n)。

6.3.2 线索二叉树

1. 遍历二叉树是对一个非线性结构进行线性化操作的过程，可以得到某个结点的前驱和后继。

2. 但是当以二叉链表存储时，只能找到结点的左右孩子，而不能直接得到结点在任一序列中的前驱和后继信息。

3. 这些信息只能在遍历的动态过程中才能得到，为了保存这些信息，可以在结点结构中增加两个指针域fwd和bkwd分别指示前驱和后继信息。

   这样就可以使结构的存储密度大大降低。

4. 若结点有左子树，则其lchild域指示其左孩子，否则指示其前驱。再增加LTag域，为0说明是第一种情况，为1说明是第二种情况。rchild和RTag同理。

   以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。

   其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树叫做线索二叉树（Threaded Binary Tree）。

   图(a)为中序线索二叉树，图(b)为与其对应的中序线索链表：

   

5. 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

6. 在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时而止。

   为找到中间结点的后继，根据中序遍历的特点，可知其后继是子树中根结点的右结点最左下的结点。根据这个思路可以沿着指针直至Tag域为1。前驱同理。

7. 在后序线索树中找结点后继较为复杂：

   • 若为二叉树的根结点，则其后继为空；
   • 若为右孩子或双亲无右子树的左孩子，则其后继为双亲；
   • 若为左孩子且双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

8. 在中序线索二叉树上遍历二叉树，虽然时间复杂度还是O(n)，但常数因子比上节讨论的算法小，且不需要设栈。

   因此，若在某程序中所用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。

9. 在二叉树的线索链表上添加头结点，令：

   • lchild域的指针指向二叉树的根结点；
   • rchild域的指针指向中序遍历时访问的最后一个结点；

   令二叉树中序序列中的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。

   这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

10. 二叉树的线索化实质是将二叉链表中的空指针改为指向前驱或后继的元素，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。

11. 在遍历过程中，记下访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。

6.4 树和森林

6.4.1 树的存储结构

1. 双亲表示法

   以一组连续空间存储树的结点，同时在每个结点中指示其双亲结点在链表中的位置：

   

   原理：利用了“每个结点（除根以外）只有唯一的双亲”的性质。

   优点：可以快速找到根。

   缺点：求结点的孩子时需要遍历整个结构。

2. 孩子表示法

   每个结点有多个指针域，每个指针指向一棵子树的根结点：

   

   原理：

   • 根据树的度来确定要有几个指针域，但要么浪费空间，要么操作不便。
   • 把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构。所有结点的链表头指针又组成一个线性表，采用顺序存储结构。

   优点：便于那些涉及孩子的操作的实现。

   缺点：不适用于涉及双亲的操作。

3. 可以将前两种方法结合起来：

   

4. 孩子兄弟表示法（二叉树表示法/二叉链表表示法）

   以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域：

   

   优点：便于实现各种树的操作，如易于实现找结点孩子等的操作。

6.4.2 森林与二叉树的转换

1. 上面我们看到，树和二叉树都可用二叉链表作为存储结构（是相同的二叉链表的不同解释），所以二叉链表可以作为媒介来导出树与二叉树之间的一个对应关系：

   

   给定一棵树，可以找到唯一一棵二叉树与之对应。

2. 从树的二叉链表表示可知，它对应的二叉树的右子树必为空。既然有这个空位，就可以依次将若干棵树（森林）转换成二叉树并通过这个空位相连：

   

6.4.3 树和森林的遍历

1. 可以先根遍历树（ABCDE），也可以后根遍历树（BDCEA）。注意子树从左至右按次序遍历。

2. 根据森林和树相互递归的定义，遍历森林也有两种方法：

   • 先序遍历森林（对应的二叉树的先序遍历）

     第一棵树的根结点->先序遍历第一棵树的根结点的子树森林->先序遍历剩余森林

     ABCDEFGHIJ

   • 中序遍历森林（对应的二叉树的中序遍历）

     中序遍历第一棵树的根结点的子树森林->第一棵树的根结点->中序遍历剩余森林

     BCDAFEHJIG

3. 当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现。

6.5 树与等价问题

1. 自反、对称、传递，则为等价关系。
2. 划分等价类的算法思想也可用于求网络的最小生成树等图的算法中。

6.6 赫夫曼树及其应用

赫夫曼（Huffman）树，又称最优树，是一类带权路径长度最短的树。

6.6.1 最优二叉树（赫夫曼树）

1. 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

2. （结点的）路径长度：路径上的分支数目。

3. （树的）路径长度：从树根到每一结点的路径长度之和。

   完全二叉树就是这种路径长度最短的二叉树。

4. （结点的）带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积（叶子结点）。

5. （树的）带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作$$WPL=\sum_{k=1}^{n}w_{k}l_{k}$$

6. 假设有n个权值，试构造一棵有n个叶子结点的二叉树，带相应的权值，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。

7. 构造赫夫曼树的方法：

   • 将n个权值构成n棵只有一个带权根结点的二叉树，构成集合F；
   • 在F中选取两棵权值最小的树作为左右子树构造一棵新的二叉树，根结点的权值为二者之和；
   • 在F中删除这两棵树，添加新生成的二叉树；
   • 重复上上步和上步，直到F中只含一棵树为止。

   这棵树便是赫夫曼树。

6.6.2 赫夫曼编码

1. 为了使字符串的编码尽可能短，可以将常用字符的编码变短，不常用字符的编码变长。但是这种长短不等的编码导致无法“断句”，为解决这一问题，必须让任一字符的编码都不是另一个字符编码的前缀。这种编码称做前缀编码。
2. 若约定二叉树左右分支分别表示字符'0'和'1'，那么从根结点到某一叶子结点的路径就唯一确定了一种字符编码。
3. 设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。
4. 赫夫曼树中没有度为1的结点，这类树又称严格的（strict，正则的）二叉树。
5. 一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。
6. 赫夫曼树具体算法请走传送门。

6.7 回溯法与树的遍历

1. 有一类问题要求一组解、全部解或最优解，而不是根据某种确定的计算法则，是利用试探和回溯（Backtracking）的搜索技术求解。
2. 回溯法也是设计递归过程的一种重要方法，实质上是一个先序遍历一棵“状态树”的过程。这棵树不是遍历前预先建立的，而是隐含在遍历过程中的。

6.8 树的计数

1. 两棵二叉树相似，是指二者都为空树或二者均不为空树，且它们的左右子树分别相似。
2. 两棵二叉树等价，是指二者不仅相似，而且所有对应结点上的数据元素都相同。
3. 二叉树的计数问题就是讨论具有$n$个结点、互不相似的二叉树的数目$b_{n}$。
4. 通过数学方法的计算（书152～154页），得出结论：含有$n$个结点的不相似的二叉树有$\frac{1}{n+1}C_{2n}^{n}$棵。
5. 任意一棵二叉树结点的前序序列和中序序列是唯一的，反过来，给定结点的前序序列和中序序列（或给定中序序列和后序序列）也可以确定一棵二叉树；但给定前序序列和后序序列，无法确定一棵二叉树。
6. 首先根据前序遍历得知根结点->在中序遍历中划分出左右子树->根据前序遍历得知根结点的左右孩子->左右孩子再次将中序遍历划分为四棵子树->……

第7章 图

图（Graph）是一种较线性表和树更为复杂的数据结构。

图没有线性表的线性关系，也没有树形结构的层次关系，而是任意的关系，图中任意两个数据元素之间都可能相关。

7.1 图的定义和术语

1. 基本术语：
   • 顶点（Vertex）：图中的数据元素；
   • 弧（Arc）：若顶点v和w有关系，则从v到w存在一条弧；
   • 弧尾（Tail）：弧的初始点（Initial node）；
   • 弧头（Head）：弧的终端点（Terminal node）；
   • 有向图（Digraph）：弧为单向；
   • 边（Edge）：若弧为双向，则用边代替（不考虑顶点到自身的弧或边）；
   • 无向图（Undigraph）：弧为双向；
   • 完全图（Completed graph）：顶点数为n时，有n(n-1)/2条边的无向图；
   • 有向完全图：具有n(n-1)条弧的有向图；
   • 稀疏图（Sparse graph）：有很少条边或弧（如e<nlogn）的图；
   • 稠密图（Dense graph）：与稀疏图相反；
   • 权（Weight）：与图的边或弧相关的数，可以表示从一个顶点到另一个顶点的距离或耗费；
   • 网（Network）：带权的图；
   • 子图（Subgraph）：一个图的顶点和边或弧均为另一个图的子集，则称这个图是另一个图的子图；
   • 邻接点（Adjacent）：无向图中之间存在边的两顶点互为邻接点；
   • 依附（Incident）：无向图中两顶点之间的边依附于这两个顶点，或称这条边和这两个顶点相关联；
   • 度（Degree）：和顶点v相关联的边的数目，记为TD(v)；
   • 邻接自、邻接到：有向图中若顶点v到顶点v’存在一条弧，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v，这条弧和顶点v,v’相关联；
   • 入度（Indegree）：有向图中以顶点v为头的弧的数目，记为ID(v)；
   • 出度（Outdegree）：有向图中以顶点v为尾的弧的数目，记为OD(v)，TD(v)=ID(v)+OD(v)，所有顶点的度数之和为边数的2倍；
   • 路径（Path）：是一个顶点序列，有向图的路径也是有向的，路径的长度是路径上的边或弧的数目；
   • 环（Cycle）：第一个顶点和最后一个顶点相同的路径，也称回路；
   • 简单路径：顶点序列中不重复出现的路径；
   • 简单环：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，也称简单回路；
   • 连通：无向图中两顶点之间有路径，则称这两个顶点连通；
   • 连通图（Connected Graph）：任意两个顶点都连通的图；
   • 连通分量（Connected Component）：无向图中的极大连通子图；
   • 强连通图：任意两个顶点之间都双向连通的有向图；
   • 强连通分量：有向图中的极大强连通子图；
   • 生成树：一个连通图的极小连通子图，含有原图的全部n个顶点，但只有足以构成一棵树的n-1条边，在一棵生成树上添加一条边则必定构成一个环（两个顶点之间有了第二条路径）（有n个顶点的图：若边数小于n-1，则是非连通图；若边数多于n-1，则一定有环；若边数等于n-1，也不一定是生成树）；
   • 生成森林：一个有向图的生成森林由若干棵有向树组成（如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树），含有原图的全部结点，但只有足以构成若干棵不相交的有向树的弧；
2. 无法将图中顶点排列成一个线性序列，不存在次序关系，所以“顶点的位置”和“邻接点的位置”都只是一个相对的概念。

7.2 图的存储结构

图的结构比较复杂，任意两个顶点之间都可能存在联系，则不能以存储区的物理位置来表示元素之间的关系，即图没有顺序映像的存储结构。

可以用多重链表表示图，这是一种最简单的链式映像结构，但由于各结点的度数不能确定，要么浪费存储单元，要么操作不便。

7.2.1 数组表示法

1. 用两个数组：
   • 一个存储数据元素（顶点）的信息；
   • 一个存储数据元素之间的关系（边或弧）的信息。
2. 以邻接矩阵表示有n个顶点的图时，需存放n个顶点信息和$n^{2}$个弧信息的存储量。可以对无向图的对称邻接矩阵压缩存储。
3. 借助邻接矩阵，易判定两顶点之间是否有边或弧相连，并且对于无向图，某一行（或一列）的元素之和就是对应顶点的度（有向图的行和为出度、列和为入度）。
4. 网的邻接矩阵可以定义为：
   • 若两顶点间有弧，则对应值为权值；
   • 若两顶点间无弧，则对应值为∞。

7.2.2 邻接表

1. 邻接表（Adjacency List）是图的一种链式存储结构。
2. 邻接表中：
   • 图中每个顶点都建立一个单链表，每个单链表中的结点表示依附于“起始”顶点的边或弧；
   • 每个表结点由3个域组成：
     • 邻接点域（adjvex）指示与“起始”顶点邻接的点；
     • 链域（nextarc）指示下一条边或弧的结点；
     • 数据域（info）存储和边或弧相关的信息（如权值等）；
   • 每个链表附设一个表头结点：
     • 链域（firstarc）指向链表中第一个结点；
     • 数据域（data）存储“起始”顶点的名或其他有关信息；
   • 表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。
3. 由于无向图以邻接表存储时，需要将一条边分成两条弧存储，所以当边很少（稀疏）的情况下，邻接表比邻接矩阵更省空间，尤其是当和边相关的信息较多时。
4. 无向图的邻接表中，链表的结点数就是对应顶点的度；有向图的邻接表中，链表的结点数只是对应顶点的出度，为求入度，必须遍历整个邻接表。
5. 为便于求有向图的入度，可以建立一个有向图的逆邻接表，即将所有边逆向存储。
6. 建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e)；否则需要查找顶点的位置，则时间复杂度为O(n·e)。
7. 邻接表的优点是易找到任一顶点的第一个邻接点和下一个邻接点，缺点是需要搜索才能判断任意两个顶点之间是否有边或弧相连。

7.2.3 十字链表

1. 十字链表（Orthogonal List）是有向图的另一种链式存储结构，是将有向图的邻接表和逆邻接表结合起来得到的。

2. 十字链表中：

   • 弧结点有5个域：
     • 尾域（tailvex）指示弧尾顶点；
     • 头域（headvex）指示弧头结点；
     • 链域hlink指向弧头相同的下一条弧；
     • 链域tlink指向弧尾相同的下一条弧；
     • info域指向该弧的相关信息；
   • 弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上；
   • 顶点结点有3个域：
     • data域存储和顶点相关的信息（如顶点的名称等）；
     • firstin链域指向以该顶点为弧头的第一个弧结点；
     • firstout链域指向以该顶点尾弧尾的第一个弧结点；

3. 可以将有向图的邻接矩阵看成是稀疏矩阵，这样十字链表也可以看成是邻接矩阵的链表存储结构。

4. 图的十字链表的弧结点：

   • 所在链表非循环链表；
   • 结点之间相对位置自然形成，不一定按顶点序号有序；

   表头结点即顶点结点：

   • 之间是顺序存储，不是链接。

5. 在十字链表中既容易找到以某顶点为尾的弧，也容易找到以某顶点为头的弧，因而也容易求得顶点的出度和入度。

6. 建立十字链表的时间复杂度和建立邻接表是相同的。

7.2.4 邻接多重表

1. 邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构，和十字链表类似。
2. 由于无向图的邻接表无法将一条边只存储一次，换句话说，一条边的两个结点不在一起，从而使得标记一条边或删除一条边等操作很不便。
3. 邻接多重表中：
   • 边结点有6个域：
     • mark为标志域，用以标记该条边是否被搜索过；
     • ivex为边依附的一个顶点；
     • jvex为边依附的另一个顶点；
     • ilink指向下一条依附于顶点ivex的边；
     • jlink指向下一条依附于顶点jvex的边；
     • info指向和边有关的各种信息；
   • 顶点结点有2个域：
     • data域存储和该顶点相关的信息；
     • firstedge域指示第一条依附于该顶点的边；
   • 所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。
4. 对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。
5. 除了在边结点中增加了一个标志域外，邻接多重表所需的存储量和邻接表相同。

7.3 图的遍历

1. 和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这就是图的遍历（Traversing Graph）。
2. 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
3. 为了避免同一顶点被访问多次，可以设一个辅助数组visited[0..n-1]，初始值置为“假”或者零，一旦访问了某个顶点，便置对应的visited为“真”或者被访问时的次序号。
4. 这两种遍历图的路径对于无向图和有向图都适用。

7.3.1 深度优先搜索

1. 深度优先搜索（Depth-First Search，DFS）遍历是树的先根遍历的推广。

2. 深度优先搜索：

   • 从某个顶点v出发，访问此顶点；
   • 然后依次从v的未被访问的邻接点出发深度优先遍历图，直至和v相通的顶点都被访问到；
   • 若此时图中还有未访问过的顶点，则选择它并重复上述过程，直至图中所有顶点都被访问。

   这显然是一个递归的过程。

3. 算法如下：

   Boolean visited[MAX];
   Status (*VisitFunc)(int v);
   
   void DFSTraverse(Graph G, Status (*Visit)(int v)) {
     VisitFunc = Visit;
     for (v = 0; v < G.vexnum; ++v)
       visited[v] = FALSE;
     for (v = 0; v < G.vexnum; ++v)
       if (!visited[v])
         DFS(G, v);
   }
   
   void DFS(Graph G, int v) {
     visited[v] = TRUE;
     VisitFunc(v);
     for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
       if (!visited[w])
         DFS(G, w);
   }

   每个顶点至多调用一次DFS函数。

4. 深度优先搜索遍历图的过程实质上就是对每个顶点查找其邻接点的过程，（查找每个顶点）耗费的时间则取决于所采用的存储结构：

   • 邻接矩阵：O($n^{2}$)；
   • 邻接表：O(e)

   则以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。

7.3.2 广度优先搜索

1. 广度优先搜索（Breadth-First Search，BFS）遍历类似于树的按层次遍历的过程。

2. 广度优先搜索：

   • 从某个顶点v出发，访问此顶点；
   • 然后依次访问v的各个未被访问的邻接点；
   • 然后分别从这些邻接点出发依次访问它们的邻接点，并使“先访问的顶点的邻接点”先于“后访问顶点的邻接点”被访问，直至所有已访问的顶点的邻接点都被访问到；
   • 若此时图中还有未访问过的顶点，则选择它并重复上述过程，直至图中所有顶点都被访问。

   广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1, 2, …的顶点。

3. 除了需要设visited数组之外，为了顺次访问路径长度为2, 3, …的顶点，还需附设队列以存储已被访问的路径长度为1, 2, …的顶点。

   算法如下：

   void BFSTraverse(Graph G, Status (*Visit)(int v)) {
     for (v = 0; v < G.vexnum; ++v)
       visited[v] = FALSE;
     InitQueue(Q);
     for (v = 0; v < G.vexnum; ++v)
       if (!visited[v]) {
         visited[v] = TRUE;
         Visit(v);
         EnQueue(Q, v);
         while (!QueueEmpty(Q)) {
           DeQueue(Q, u);
           for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
             if (!visited[w]) {
               visited[w] = TRUE;
               Visit(w);
               EnQueue(Q, w);
             }
         }
       }
   }

   每个顶点至多进一次队列。

4. 广度优先搜索遍历图的过程实质上是通过边或弧找邻接点的过程，故时间复杂度和DFS遍历相通，不同之处仅仅在于对顶点访问的顺序不同。

5. BFS搜索一般采用队列来暂存刚访问过的顶点；DFS搜索一般采用栈来暂存刚访问过的顶点。

7.4 图的连通性问题

7.4.1 无向图的连通分量和生成树

1. 在非连通图中，一次DFS或BFS过程得到的顶点访问序列恰为图中各连通分量中的顶点集，分别加上所有依附于这些顶点的边，便构成了非连通图的若干个连通分量。

2. 在连通图中，从某一顶点出发，进行一次DFS或BFS，可将边分为访问过的边和未访问过的边，其中访问过的边再加上所有顶点，就构成了连通图的一个极小连通子图，是连通图的一棵生成树。（生成树和极小连通子图都只存在于连通图）

   （“图G的生成树是该图的一个极小连通子图”这种说法为什么是错误的？）

   称DFS得到的生成树为深度优先生成树，BFS得到的生成树为广度优先生成树。

3. 在非连通图中，有若干棵生成树，组成非连通图的生成森林。

   同样分为两类。

4. 算法的时间复杂度和遍历相同。

7.4.2 有向图的强连通分量

1. 深度优先搜索是求有向图的强连通分量的一个新的有效方法。

2. 假设以十字链表作有向图的存储结构，求强连通分量的步骤如下：

   • 从某顶点出发，进行一次DFS遍历，按退出DFS函数的顺序排列顶点，得到finished数组；
   • 从最后完成搜索的顶点（finished[vexnum-1]）出发，逆向DFS遍历，直至所有顶点都被访问。

   每一次调用DFS作逆向深度优先遍历所访问到的顶点集，也就是得到深度优先生成森林中每一棵树的顶点集，就是有向图G中一个强连通分量的顶点集。

3. 算法的时间复杂度亦和遍历相同。

7.4.3 最小生成树

1. 一棵生成树的代价就是树上各边的代价之和，为使总耗费最少，就是构造连通网的最小代价生成树（Minimum Cost Spanning Tree，最小生成树）的问题。

2. MST性质：假设有一个连通网，若其中权值最小的边的两个顶点分别在两个互补顶点集中，则它的最小生成树必包含这条边。

3. 构造（无向图）最小生成树有两种算法：

   • 普里姆（Prim）算法

     核心思想是加点。

     从某一顶点开始，寻找与它相连的且相连边权最小的顶点，将它们加入已经访问的顶点集合。再次寻找与这两个顶点相连的所有顶点中相连边权最小的顶点，并加入顶点集合。重复此步骤，直到访问了所有顶点，即全部顶点都已加入已经访问的顶点集合。

     由于需要求最小权值、选择具有最小代价的边，故时间复杂度为O($n^{2}$)，和边数无关，适用于求边稠密的网的最小生成树。

   • 克鲁斯卡尔（Kruskal）算法

     核心思想是加边。

     将图中所有边按权值大小进行排序，从权最小的边开始，逐条边加入生成树中，注意加边后不可与已加入的边构成环，直至所有顶点均连通。

     至多对e条边各扫描一次，每次选择最小权的边仅需O(loge)的时间（前提以“堆”存放，且第一次需O(e)）；每个连通分量看成一个等价类，加边则相当于求等价类，仅需O(eloge)时间（前提以MFSet类型来描述），故时间复杂度为O(eloge)，和顶点数无关，适合于求边稀疏的网的最小生成树。

   具体算法请走传送门。

7.4.4 关节点和重连通分量

1. 若删去顶点v以及和v相关联的各边后，图的一个连通分量被分割成了两个以上的连通分量，则称顶点v为该图的一个关节点（articulation point，割点）。
2. 一个没有关节点的连通图是一个重连通图（biconnected graph）。
3. 重连通图的任意一对顶点之间至少存在两条路径，以至于删去某顶点以及边后也不会破坏图的连通性。
4. 若在连通图上至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。
5. 利用DFS便可求得图的关节点，并由此可判别图是否是重连通的：
   • 若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点；
   • 若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边，则v为关节点。
6. 求关节点的时间复杂度仍为O(n+e)。

7.5 有向无环图及其应用

1. 一个无环的有向图称做有向无环图（directed acycline graph，DAG图）。

2. DAG图是一类比有向树更一般的特殊有向图：

   

   从左至右依次为有向树、DAG图和有向图。

3. 二叉树可以表示表达式，若表达式含有公共子式，则可以用DAG图实现对相同子式的共享，从而节省存储空间。

4. 判定一个图是有向无环图，需要在有向图中检查是否存在环：

   • 在无向图中，若DFS遍历过程中遇到回边，则必定存在环；
   • 在有向图中，这条回边可能是指向深度优先生成森林中另一棵生成树上顶点的弧。

   在有向图中，若从顶点v开始进行DFS遍历，结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。

5. 几乎所有工程（project）都可分为若干个子工程，称为活动（activity）。活动之间通常受一定条件的约束，即存在先后次序。

6. 工程是否顺利进行？——拓扑排序；

   估算整个工程完成所必需的最短时间——求关键路径。

7.5.1 拓扑排序

1. 拓扑排序（Topological Sort）就是由某个集合上的一个偏序得到该集合上的一个全序的操作。

   （偏序关系：自反、反对称、传递。）

   （设R是集合X上的偏序（Partial Order），如果对X中每个x和y，必有xRy或yRx，则称R是集合X上的全序关系。）

   直观来说，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较：

   

   左侧为偏序，右侧为全序。

2. 若在偏序中添加条件使得可以表示全序，则这个全序称为拓扑有序（Topological Order），这个操作便是拓扑排序。

3. 用顶点表示活动、用弧表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network，AOV-网）。

4. AOV-网中不能出现有向环。若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。

5. 构造拓扑序列：

   • 在有向图中选一个没有前驱的顶点且输出之；
   • 从图中删除该顶点和所有以它为尾的弧；
   • 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止（这种情况说明有向图中存在环）。

6. 具体算法请走传送门。

7. 拓扑排序总的时间复杂度为O(n+e)。

8. 当有向图无环时，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

7.5.2 关键路径

1. AOE-网（Activity On Edge）是边表示活动的网，是一个带权的有向无环图。顶点表示事件（Event），弧表示活动，权表示活动持续的时间。

2. 工程只有一个开始点和一个完成点，故在正常无环的情况下，网中只有一个入度为零的点（源点）和一个出度为零的点（汇点）。

3. 和AOV-网不同，AOE-网研究的问题是：

   • 完成整项工程需要多少时间？
   • 哪些活动是影响工程进度的关键？

4. AOE-网中有些活动可以并行地进行，所以总时间是最长路径的加权长度，最长的路径就是关键路径（Critical Path）。

5. 从开始点到某一顶点的最长路径长度叫做对应事件的最早发生时间，决定了以该顶点为尾的弧所表示的活动的最早开始时间。

6. 还可以定义一个活动的最迟开始时间，与最早开始时间之差尾该活动的时间余量，时间余量为零的活动就是关键活动。

7. 关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。所以分析关键路径的目的就是找出关键活动，争取关键活动的工效，缩短整个工期。

8. 由分析知，要求关键路径，就要找关键活动，就要先求事件的最早和最迟开始时间e和l：

   • 最早开始时间就是活动的最早发生时间；
   • 最迟开始时间就是活动的最迟发生时间减去持续时间dut；

   求最早和最迟发生时间ve和vl：

   • 从ve(0)=0开始向前递推，每次取ve+dut的最大值：

     ve(j)=Max{ve(i)+dut(<i,j>)}, <i,j>∈T, j=1,2,…,n-1, T是所有以第j个顶点为头的弧的集合（前提拓扑有序，因为ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定）；

   • 从vl(n-1)=ve(n-1)开始向后递推，每次取vl-dut的最小值；

     vl(i)=Min{vl(j)-dut(<i,j>)}, <i,j>∈S, i=n-2,…,0, S是所有以第i个顶点为尾的弧的集合（前提逆拓扑有序，因为vl(j-1)必须在vj的所有后继的最迟发生时间求得之后才能确定）；

9. 求关键路径的算法：

   • 输入e条弧，建立AOE-网；
   • 从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve（若检查存在环则终止）；
   • 从汇点vn出发，令vl[n-1]= ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl；
   • 根据各顶点的ve和vl值，求每条弧的最早开始时间e和最迟开始时间l。

   若某条弧满足条件e=l，则为关键活动。

10. 逆拓扑排序可用DFS。求关键路径算法的时间复杂度为O(n+e)。

11. 关键活动的速度提高是有限度的，只有在不改变网的关键路径的情况下，提高关键活动的速度才有效，且必须提高同时在几条关键路径上的活动的速度。

7.6 最短路径

路径上的第一个顶点为源点（Source），最后一个顶点为终点（Destination），路径长度的度量是路径上边的权值之和。

7.6.1 从某个源点到其余各顶点的最短路径

解决单源点的最短路径问题——迪杰斯特拉（Dijkstra）算法：

具体算法请走传送门。

7.6.2 每一对顶点之间的最短路径

1. 根据上一节的从单个源点到其余各顶点的最短路径算法，此处只需每次以一个顶点为源点，重复执行Dijkstra算法n次即可，总执行时间为O($n^{3}$)。

2. 下面介绍由弗洛伊德（Floyd）提出的另一个算法，时间复杂度也是O($n^{3}$)，但形式上更简单。

3. Floyd算法仍从图的带权邻接矩阵cost出发，其基本思想是（求顶点vi到vj的最短路径）：

   • 若vi到vj有弧，则为一条路径，但不一定最短，还需进行n次试探；
   • 考虑(vi,v0,vj)是否存在，和(vi,vj)相比，取较短的作为中间顶点序号≤0的最短路径；
   • 增加顶点，若(vi,…,v1)和(v1,…,vj)分别是当前找到的中间顶点序号≤0的最短路径，则(vi,…,v1,…,vj)可能是中间顶点序号≤1的最短路径；
   • 将中间顶点序号≤0的最短路径和中间顶点序号≤1的最短路径相比，取较短的作为中间顶点序号≤1的最短路径；
   • 增加顶点，继续试探……

   一般情况下，若(vi,…,vk)是从vi到vk的中间顶点序号≤k-1的最短路径、(vk,…,vj)是从vk到vj的中间顶点序号≤k-1的最短路径，则将(vi,…,vk,…,vj)和已经得到的从vi到vj的中间顶点序号≤k-1的最短路径相比，取较短的就是从vi到vj的中间顶点序号≤k的最短路径。

   这样经过n次比较后，最后求得的必是从vi到vj的最短路径。

第8章 动态存储管理

第9章 查找

1. 查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。

   日常生活中的电话号码簿和字典等都可视作一张查找表。

2. “集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

3. 静态查找表（Static Search Table）只进行查找操作：

   • 查询特定数据元素是否在表中
   • 检索特定数据元素的各种属性

   动态查找表（Dynamic Search Table）除了进行查找操作，还进行：

   • 在表中插入一个数据元素
   • 从表中删除某个数据元素

4. 关键字（Key）：数据元素（或记录）中某个数据项的值，用以识别某个数据元素（或记录）：

   • 主关键字（Primary Key）：可以唯一地标识一个记录的关键字；
   • 次关键字（Secondary Key）：可以标识若干记录的关键字。

   当数据元素只有一个数据项时，其关键字就是该数据元素的值。

5. 查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素：

   • 查找成功：表中存在符合条件的记录（此时查找结果可以是记录的信息，也可以是记录在查找表中的位置）；
   • 查找不成功：表中不存在符合条件的记录（此时查找结果可给出一个“空”记录或“空”指针）。

6. 查找的过程依赖于数据元素在结构中所处的地位。

7. 约定如下的宏定义：

   // 对数值型关键字
   #define EQ(a,b) ((a) == (b))
   #define LT(a,b) ((a) < (b))
   #define LQ(a,b) ((a) <= (b))
   ...
   // 对字符串型关键字
   #define EQ(a,b) (!strcmp((a), (b)))
   #define LT(a,b) (strcmp((a), (b)) < 0)
   #define LQ(a,b) (strcmp((a), (b)) <= 0)
   ...

9.1 静态查找表

9.1.1 顺序表的查找

1. 线性链表模块的查找与顺序存储结构模块的查找类似，不再赘述。

2. 顺序查找（Sequential Search）：从表中最后一个记录开始向前查找：

   int Search_Seq(SSTable ST, KeyType key) {
     ST.elem[0].key = key;
     for (i = ST.length; !EQ(ST.elem[i],key,key); --i);
     return i;
   }

   在零处设置“哨兵”，用于结束查找不成功的情况，免去查找过程中每一步都要检测整个表是否查找完毕。

3. 平均查找长度（Average Search Length，ASL）：和给定值进行比较的关键字的个数的期望值：$$ASL=\sum_{i=1}^{n}P_{i}C_{i}$$$P_{i}$为查找表中第$i$个记录的概率，总和为1；$C_{i}$为查找到第$i$个记录时已经比较过的关键字个数，顺序查找中为$n-i+1$。

4. 等概率（1/n）下顺序查找的平均查找长度为(n+1)/2。

5. 有时可以根据实际情况调整查找概率并排序，可以提高查找效率。

6. 当记录的查找概率无法预知时，可以根据每次查找时对其访问的频度作以调整，保持按访问频度非递减有序的次序，使查找概率大的记录在查找过程中不断后移。

7. 当查找不成功的情形不能忽视时，ASL应为成功与不成功时的ASL之和。此时等概率（1/2n）下顺序查找的平均查找长度为3(n+1)/4。

9.1.2 有序表的查找

1. 折半查找（Binary Search）：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

2. 折半查找的过程可用二叉树来描述，称为判定树。

   找到有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，和给定值进行比较的关键字个数最多不超过树的深度。

   判定树非完全二叉树，但其叶子结点所在层次之差最多为1，则n个结点的判定树的深度和n个结点的完全二叉树的深度相同，均为$\lfloor log_{2}n\rfloor+1$。

3. 折半查找法在查找成功时和给定值进行比较的关键字个数至多为$\lfloor log_{2}n\rfloor+1$。

4. 在判定树的空指针域加上一个指向方形结点的指针，这些方形结点就是判定树的外部结点（圆形结点为内部结点）。

   则查找不成功时就是走到了外部结点上，此时比较过的关键字个数就是路径上内部结点的个数。

   因此不成功时的比较过的关键字个数不超过$\lfloor log_{2}n\rfloor+1$。

5. 折半查找的平均查找长度为$\frac{n+1}{n}log_{2}(n+1)-1$，当n较大（>50）时，近似为$log_{2}(n+1)-1$。

6. 优点：比顺序查找效率高；

   缺点：只适用于顺序存储的有序表。

7. 斐波那契查找：根据斐波那契序列的特点对表进行分割，分段进行查找。

   优点：平均性能比折半查找好，分割时只需进行加、减运算；

   缺点：最坏情况下的性能（虽然仍是O(logn)）比折半查找差。

8. 插值查找：根据给定值key来确定进行比较的关键字。

   只适用于关键字均匀分布的表，此时对于表长较大的顺序表，其平均查找性能比折半查找好。

9.1.3 静态树表的查找

1. 下面考虑有序表中各记录的查找概率不等的情况，此时折半查找的性能未必是最优的。
2. 设判定树的带权内路径长度之和为PH值$$PH=\sum_{i=1}{n}w_{i}h_{i}$$$w_{i}=cp_{i}$，c为某常量，p为结点的查找概率；h为层数。
3. 查找性能最佳的判定树是PH最小的二叉树，称为静态最优查找树（Static Optimal Search Tree）。
4. 若一棵二叉树的PH值在所有具有同样权值的二叉树中近似为最小，则称这类二叉树为次优查找树（Nearly Optimal Search Tree）。

9.1.4 索引顺序表的查找

1. 分块查找又称索引顺序查找，是顺序查找的一种改进方法。

2. 在此查找法中，除表本身以外，还需建立一个“索引表”，存放：

   • 关键字项：每个分块的最大关键字；
   • 指针项：每块第一个记录在表中的位置。

3. 索引表按关键字有序，则表或者有序或者分块有序（块的最大关键字有序）。

4. 根据结构的特点，分块查找过程需分两步进行：

   • 确定待查记录所在的块（子表）；
   • 在块中顺序查找（若有序则可折半查找）。

5. 分块查找的平均查找长度：

   （表长为n、均匀分成b块、每块含有s个记录、每个记录查找概率均等）

   采用顺序查找：

   • 此时ASL=(n/s+s)/2+1，当$s=\sqrt n$时，ASL取最小值$\sqrt{n}+1$。虽然较顺序查找有了很大改进，但远不及折半查找。

   采用折半查找：

   • ASL约为$log_{2}(\frac{n}{s}+1)+\frac{s}{2}$

6. 查找方法比较：

   比较项	顺序查找	折半查找	分块查找
   ASL	最大	最小	两者之间
   表结构	有序表、无序表	有序表	分块有序表
   存储结构	顺序存储结构、线性链表	顺序存储结构	顺序存储结构、线性链表

7. 几种查找表的特性：

   表类型	查找	插入	删除
   无序顺序表	O(n)	O(1)	O(n)
   无序线性链表	O(n)	O(1)	O(1)
   有序顺序表	O(logn)	O(n)	O(n)
   有序线性链表	O(n)	O(1)	O(1)

9.2 动态查找表

动态查找表的特点是表结构本身是在查找过程中动态生成的，即查找不成功时将key值插入。

9.2.1 二叉排序树和平衡二叉树

1. 二叉排序树（Binary Sort Tree，BST，二叉查找树）或者是一棵空树，或者是具有下列性质的二叉树：

   • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
   • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
   • 它的左右子树也分别为二叉排序树。

2. 二叉排序树的查找过程和次优二叉树类似，但和次优二叉树相对，二叉排序树是一种动态树表。

3. 二叉排序树中，新插入的结点一定是一个新添加的叶子结点，而且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

   即，插入时不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可。

4. 中序遍历二叉排序树可以得到关键字的有序序列，即一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。

5. 二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。

6. 当删除二叉排序树的一个结点时，若待删除结点为叶子结点，或只有左子树，或只有右子树时，删除都很容易。

   当待删除结点的左右子树均不空时，为保持其他元素之间的相对位置不变，可以有两种做法：

   • 将其左子树给双亲、右子树给左子树最右下角的叶子结点；
   • 令待删除结点的直接前驱（或直接后继）替代待删除结点，再删去它的直接前驱（或直接后继），再相应地改变子树。

7. 含有n个结点的判定树是唯一的，但二叉排序树并不唯一，而且平均查找长度也和树的形态有关：

   最坏的情况：先后插入的关键字有序，此时树的深度为n，ASL=(n+1)/2，和顺序查找相同。

   最好的情况：形态和折半查找的判定树相同，ASL和$log_{2}n$成正比。

   在随机的情况下，二叉排序树的平均查找长度和logn是等数量级的；然而在某些情况下，需要在构成二叉排序树的过程中进行“平衡化”处理，成为二叉平衡树。

8. 平衡二叉树（Balanced Binary Tree，Height-Balanced Tree，AVL树）或者是一棵空树，或者是具有下列性质的树：

   • 它的左子树和右子树都是平衡二叉树；
   • 左子树和右子树的深度之差的绝对值不超过1。

9. （结点的）平衡因子（Balance Factor，BF）是该结点的左子树的深度减去减去它的右子树的深度。

   AVL树上所有结点的BF可能的取值为-1、0和1。

10. AVL树的深度和logn是同数量级的，则它的ASL也和logn同数量级。

11. 构造平衡二叉树的平衡旋转技术：

    • 单向右旋平衡处理（LL）：

      

    • 单向左旋平衡处理（RR）：

      

    • 双向旋转（先左后右）平衡处理（LR）：

      

    • 双向旋转（先右后左）平衡处理（RL）：

      

    特点：

    • 对不平衡的最小子树操作；
    • 旋转后树根结点BF=0；
    • 旋转后子树深度不变故不影响全树，也不影响插入路径上所有祖先结点的平衡度。

12. 在平衡二叉树上进行查找的时间复杂度为O(logn)。

13. 二叉排序树（二叉查找树）、平衡二叉树、最优二叉树和次优二叉树都是二叉树，查找方法一样；但前两者为动态树表，后两者是静态树表。

9.2.2 B-树和B+树

1. B-树是一种平衡的多路查找树，或为空树，或为满足下列特性的m叉树：

   • 每个结点至多有m棵子树；
   • 若根结点不是叶子结点，则至少有两棵子树；
   • 内部结点至少有$\lceil m/2\rceil$棵子树；
   • 所有的非叶子结点包含信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)，其中K为关键字（升序），A为指向树根结点的指针，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn，n为关键字的个数（n+1为子树个数）；
   • 所有的叶子结点都出现在同一层次上，并且不带信息。

   4阶的B-树：

   

2. 3阶B-树也叫2-3树。

3. B-树的查找操作包含找结点和找关键字。在m阶含有N个关键字（$N\ge \lceil m/2\rceil-1$）的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过$log_{\lceil m/2\rceil}(\frac{N+1}{2})+1$。

4. B-树的每次插入一个关键字不是添加叶子结点，而是首先在某个非叶子结点中添加一个关键字，若此结点的关键字个数超过m-1，则要产生结点的“分裂”，关键字$K_{\lceil m/2\rceil}$和前后指针插入到双亲结点。

5. B-树的每次删除一个关键字要首先找到该关键字所在结点进行删除，若结点为叶子结点或关键字数目少于$_{\lceil m/2\rceil}$，则需进行结点的“合并”。

6. B+树是B-树的变型树，不再是第6章中定义的树：

   • 关键字个数等于子树个数；
   • 全部关键字信息都在叶子结点，同时还包含指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
   • 所有的非叶子结点都是索引，这些结点仅含有子树（根结点）中的最大（或最小）关键字。

   3阶的B+树：

   

7. B+树有两个头指针，分别指向根结点和关键字最小的叶子结点，因此可以对B+树进行两种查找运算：

   • 从最小关键字起顺序查找；
   • 从根结点开始随机查找。

8. B+树的每次查找都走到叶子结点，插入与删除也只在叶子结点进行，并相应地分裂与合并。

9.2.3 键树

1. 键树又称数字查找树（Digital Search Tree），是一棵度≥2的树，树中的每个结点中不是包含关键字，而是只含有组成关键字的符号（数位或字符等）。

2. 集合、子集和元素之间的层次关系可以用一棵树来表示，这棵树便为键树：

   

3. 约定键树是有序树，且同一层中自左至右有序，结束符$小于任何字符。

4. 键树的存储结构：

   • 孩子兄弟链表：

     分支结点包括3个域：

     • symbol域存储关键字的一个字符；
     • first域存储指向第一棵子树根的指针；
     • next域存储指向右兄弟的指针；

     叶子结点的infoptr存储指向该关键字记录的指针。

     此时的键树又称双链树。

   • 多重链表：

     每个结点含有d个指针域（d是每个结点的最大度），此时的键树又称Trie树。

9.3 哈希表

9.3.1 什么是哈希表

1. 前面讨论的各种结构中，记录在结构中的相对位置是随机的，查找的效率依赖于查找过程中所进行的比较次数。所以理想的情况是不进行比较而通过一次存取就能得到所查记录，即关键字和它的存储位置有一个对应关系，则称这个对应关系为哈希（Hash）函数。
2. 哈希函数是一个映像，很灵活，只要满足函数值都在表长允许的范围内即可。
3. 若不同的关键字却得到了同一哈希地址，则称这种现象为冲突（collision），这两个关键字是同义词（synonym）。
4. 冲突只能尽可能减少，而不能完全避免，因为哈希函数一般就是一个压缩的映像。
5. 所以，根据设定的哈希函数，以及处理冲突的方法，就可以将一组关键字映像到一个有限连续地址集（区间）上，这种表就是哈希表，这种映像过程称为哈希造表或散列，这种存储位置称为哈希地址或散列地址。

9.3.2 哈希函数的构造方法

1. 哈希函数应试图将冲突减到最少，所以哈希函数应使映像到地址集合中任何一个地址的概率均等，从而使一组关键字的哈希地址均匀分布，此类哈希函数为均匀的（Uniform）哈希函数。
2. 常用的构造哈希函数的方法：
   • 直接定址法：H(key)=key或H(key)=a·key+b
   • 数字分析法：取关键字的若干数位组成哈希地址
   • 平方取中法：取关键字平方后的中间几位为哈希地址
   • 折叠法：均匀分割关键字，取各部分叠加和（舍去进位）为哈希地址
   • 除留余数法：H(key)=key MOD p, p≤m（可以选p为质数或不包含小于20的质因数的合数）
   • 随机数法：H(key)=random(key)

9.3.3 处理冲突的方法

1. 处理冲突，就是为关键字另找一个“空”的哈希地址。

2. 常用的处理冲突的方法：

   • 开放定址法：Hi=(H(key)+di) MOD m（m为哈希表表长，d为增量序列，可以是：1～m-1（线性探测再散列）、$\pm k^{2}$（二次探测再散列）、伪随机数（伪随机探测再散列））

     采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录所在位置置空，因为这会影响以后的查找（遇空终止）。

   • 再哈希法：Hi=RHi(key)（RHi均是不同的哈希函数）

   • 链地址法：将所有同义词的记录存储在同一线性链表中

   • 建立一个公共溢出区：另设向量为溢出表

9.3.4 哈希表的查找及其分析

1. 查找过程和哈希造表的过程基本一致。
2. 由于“冲突”的产生，使得哈希表的查找仍是一个比较的过程，仍需以ASL作为衡量哈希表的查找效率的量度。
3. 比较的个数取决于：哈希函数、处理冲突的方法以及哈希表的饱和程度（装填因子$\alpha=n/m$（记录数/表长）的大小）。
4. 线性探测再散列容易产生记录的二次聚集，而链地址法则不会。
5. 可以证明，下列三种方法的哈希表查找成功时的ASL为：
   • 线性探测再散列：$S_{nl}\thickapprox \frac{1}{2}(1+\frac{1}{1-\alpha})$
   • 随机探测再散列、二次探测再散列和再哈希：$S_{nr}\thickapprox -\frac{1}{\alpha}ln(1-\alpha)$
   • 链地址法：$S_{nc}\thickapprox 1+\frac{\alpha}{2}$
6. 哈希表的ASL是$\alpha$的函数，而不是n的函数。所以，不管n多大，我们总可以选择一个合适的装填因子，以便将ASL限定在一个范围内。
7. 具体算法请走传送门。

第10章 内部排序

10.1 概述

1. 排序（Sorting）是将任意序列重新排列成一个有序序列（按关键字）。

2. 对主关键字的排序结果唯一，对次关键字的排序结果不唯一（可能有相等的情况）。

3. 对于关键字相等的两个记录，若排序前后二者先后顺序不改变，则称所用的排序方法是稳定的；反之则称所用的排序方法是不稳定的。

4. 内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程；

   外部排序指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

5. 根据排序原则，可将内部排序分为5类：

   • 插入排序
   • 交换排序
   • 选择排序
   • 归并排序
   • 计数排序

   根据工作量，可将内部排序分为3类：

   • 简单的排序方法，时间复杂度为O($n^{3}$)
   • 先进的排序方法，时间复杂度为O(nlogn)
   • 基数排序，时间复杂度为O(d·n)

6. 通常，排序需要两个操作：比较和移动。

7. 待排序的记录序列可能有下列3种存储方式：

   • 存放在地址连续的一组存储单元上，类似于线性表的顺序存储结构，记录之间的次序关系由其存储位置决定，则实现排序必须借助移动记录；

   • （链）表排序：存放在静态链表中，记录之间的次序关系由指针指示，则实现排序不需移动记录，仅需修改指针；

     之所以不用动态链表，是因为排序算法仅需改变次序关系，无需进行插入和删除操作，且在排序结束时尚需调整记录；

   • 地址排序：存放在地址连续的一组存储单元上，同时另设一个指示各个记录存储位置的地址向量，则排序时仅需移动“地址”，结束后按地址值调整记录的存储位置。

10.2 插入排序

10.2.1 直接插入排序

1. 直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表：

   void InsertSort(SqList &L) {
     for (i = 2; i <= L.length; ++i)
       if (LT(L.r[i].key,L.r[i-1].key)) {
         L.r[0] = L.r[i]; // copy
         L.r[i] = L.r[i-1];
         for (j = i - 2; LT(L.r[0].key,L.r[j].key); --j)
           L.r[j+1] = L.r[j]; // move
         L.r[j+1] = L.r[0]; // insert
       }
   }

2. 直接插入排序的时间复杂度为O($n^{2}$)。

3. 直接插入排序是一种稳定的排序方法。

10.2.2 其他插入排序

1. 当待排序序列中的记录数量n很大时，则不宜采用直接插入排序，应减少“比较”和“移动”的次数。

2. 折半插入排序：将查找操作利用折半查找来实现：

   void BInsertSort(SqList &L) {
     for (i = 2; i <= L.length; ++i) {
       L.r[0] = L.r[i];
       low = 1;
       high = i - 1;
       while (low <= high) {
         m = (low + high) / 2;
         if (LT(L.r[0].key,L.r[m].key))
           high = m - 1;
         else
           low = m + 1;
       }
       for (j = i - 1; j >= high + 1; --j)
         L.r[j+1] = L.r[j];
       L.r[high+1] = L.r[0];
     }
   }

   时间复杂度为O($n^{2}$)，同时也是一种稳定的排序方法。

3. 2-路插入排序：在折半插入排序的基础上再改进，减少排序过程中移动的次数，需要n个记录的辅助空间。另设一个同类型循环向量，将待排序数组按顺序复制到此向量中，同时设两个指针first和final分别指示有序序列的第一个和最后一个记录的在向量中的位置。

   比插入排序减少了一半的移动次数，但不能绝对避免移动。而且当L.r[1]是待排序记录中最小或最大的记录时，2-路插入排序就完全失去了它的优越性。

4. 表插入排序：若希望彻底避免移动记录，则只能改变存储结构，采用静态链表，修改2n次指针代替移动记录，比较次数相同。时间复杂度仍为O($n^{2}$)。

   而且得到的仍是一个链表，虽然有序，但也只能顺序查找，不能随机查找。为实现折半查找，还需重新排列记录（顺序扫描链表，移动结点至数组对应位置（互换、改指针））。

10.2.3 希尔排序

1. 希尔排序（Shell’s Sort）又称“缩小增量排序（Diminishing Increment Sort）”，是一种插入排序的方法，但在时间效率上较前述几种排序方法有较大的改进。

2. 若待排序记录基本上是有序的，或者待排序列很短，则直接插入排序的效率较高。那么何不将待排序序列分割成若干子序列后，再分别进行插入排序呢？这就是希尔排序的基本思想。

3. 子序列的构成不是简单的逐段分割（即不是连续的），而是相隔某个“增量”的记录组成一个子序列。

4. 增量开始时很大，以至于子序列中对象较少，所以排序很快；后来增量逐渐变小，以至于子序列中对象逐渐增多，但已基本有序，所以排序依然很快。

5. 算法如下：

   void ShellInsert(SqList &L, int dk) {
     for (i = dk + 1; i <= L.length; ++i)
       if (LT(L.r[i].key,L.r[i-dk].key)) {
         L.r[0] = L.r[i];
         for (j = i - dk; j > 0 && LT(L.r[0].key,L.r[j].key); j -= dk)
           L.r[j+dk] = L.r[j];
         L.r[j+dk] = L.r[0];
       }
   }
   
   void ShellSort(SqList &L, int dlta[]; int t) {
     for (k = 0; k < t; ++k)
       ShellInsert(L, dlta[k]);
   }

6. 增量序列可以有各种取法，但增量序列中的值应不含除1之外的公因子，并且最后一个增量值必须等于1。

7. 当n在某个特定的范围内，希尔排序所需的比较和移动次数约为$n^{1.3}$，当n趋于∞时可减少到$n(log_{2}n)^{2}$。

8. 希尔排序是一种不稳定的排序方法。

10.3 快速排序

1. 下面讨论借助“交换”进行排序的方法，最简单的一种就是起泡排序（Bubble Sort）。
2. 在起泡排序的过程中，关键字较小的记录好比水中气泡逐趟向上漂浮，而关键字较大的记录好比石块往下沉，每一趟有一块“最大”的石头沉到水底。
3. 起泡排序的时间复杂度为O($n^{2}$)，同时也是一个稳定的排序方法。
4. 快速排序（Quick Sort）是对起泡排序的一种改进，它的基本思想是，选取一个对象作为枢轴（pivot，支点、基准），将对象序列分为比它大和比它小的两部分，再继续对子序列重复上述过程，直到所有对象都排在相应位置上。
5. 具体算法请走传送门。
6. 快速排序在所有同数量级O(nlogn)的排序方法中是平均性能最好的，但若初始记录序列按关键字有序或基本有序时，快排退化为起泡排序，时间复杂度为O($n^{2}$)。
7. 快速排序是一种不稳定的排序方法。

10.4 选择排序

选择排序（Selection Sort）的基本思想是，每一趟在后面n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。

10.4.1 简单选择排序

1. 直接选择排序（Simple Selection Sort）：
   • 在i～n-1中选择关键字最小的；
   • 若它不是这组序列的第一个，就和第一个对调；
   • 在序列中剔除这个最小的，在剩下的序列中重复执行上两步，直到剩余对象只有一个为止。
2. 最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3(n-1)。
3. 直接选择排序是一种不稳定的排序方法。

10.4.2 树形选择排序

1. 体育比赛中的锦标赛的规则是，若乙胜丙，甲胜乙，则认为甲必定能胜丙。

2. 树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛思想进行选择排序的方法：

   • 首先对n个记录的关键字进行两两比较；
   • 然后在其中$\lceil \frac{n}{2}\rceil$个较小者之间再进行两两比较；
   • 重复上述过程，直至选出最小关键字的记录为止。

   上面是进行一次排序的过程。选出最小关键字的记录之后，将叶子中的最小关键字改为“最大值”，重复以上过程，就可以依次选出从小到大的所有关键字。

3. 树形选择排序的时间复杂度为O(nlogn)，缺点是辅助存储空间较多、和最大值作多余的比较等。

10.4.3 堆排序

1. 堆排序（Heap Sort）只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
2. 具体算法请走传送门。
3. 堆排序在最坏的情况下，时间复杂度也为O(nlogn)，同时堆排序是一个不稳定的排序方法。

10.5 归并排序

1. 归并是将两个或两个以上的有序表组合成一个新的有序表。
2. 可以将n个记录看成是n个有序的子序列，然后两两归并，得到$\lceil \frac{n}{2}\rceil$个长度为2或1的有序子序列，再重复两两归并，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。
3. 具体算法请走传送门。
4. 实现归并排序需和待排记录等数量的辅助空间，其时间复杂度为O(nlogn)。归并排序是一个稳定的排序方法。

10.6 基数排序

基数排序（Radix Sorting）是一种借助多关键字排序思想，对单逻辑关键字进行排序的方法，不需要进行记录关键字间的比较。

10.6.1 多关键字的排序

具体算法请走传送门。

10.6.2 链式基数排序

1. 基数排序：借助“分配”和“收集”对单逻辑关键字进行排序。
2. 链式基数排序方法：用链表作存储结构的基数排序。

10.7 各种内部排序方法的比较讨论

排序方法	最好比较次数	最坏比较次数	最好移动次数	最坏移动次数	稳定性	最好附加存储	最坏附加存储
简单排序	n	$n^{2}$	0	$n^{2}$	好	1	1
折半插入排序	nlogn	nlogn	0	$n^{2}$	好	1	1
快速排序	nlogn	$n^{2}$	nlogn	$n^{2}$	差	logn	$n^{2}$
简单选择排序	$n^{2}$	$n^{2}$	0	n	差	1	1
锦标赛排序	nlogn	nlogn	nlogn	nlogn	好	n	n
堆排序	nlogn	nlogn	nlogn	nlogn	差	1	1
归并排序	nlogn	nlogn	nlogn	nlogn	好	n	n
基数排序	d(n+rd)	d(n+rd)	d(n+rd)	d(n+rd)	好	rd	rd

1. 就平均时间性能而言，快排最佳，其所需时间最省，但其在最坏情况下的时间性能不如堆排序和归并排序。
2. n较大时，归并排序比堆排序省时间，但它所需的辅助存储量最多。
3. “简单排序”包括除希尔排序、折半插入排序之外的插入排序，以及起泡排序。
4. 简单排序中，直接插入排序最简单，当序列基本有序或n较小时，是最佳的排序方法。
5. 基数排序的时间复杂度也可写成O(d·n)，最适用于n很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则也可以按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。
6. 基数排序是最稳定的内排方法，所有时间复杂度为O($n^{2}$)的简单排序法也是稳定的。然而，快排、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。
7. 一般来说，排序过程中的“比较”在“相邻的两个记录关键字”间进行的排序方法是稳定的。
8. 由于大多数情况下排序按记录的主关键字进行，则所用的排序方法是否稳定无关紧要。
9. 借助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度为O(nlogn)。

第11章 外部排序

第12章 文件