• 本篇文章是在准备考研时，对《王道计算机考研 数据结构》的所有笔记进行汇总，方便学习和复习时查看。对于期末考试也可以食用。笔记是纯人工手打的，会有一些小问题，如果有错误的地方请评论或私信…
• 本篇笔记课程来源：王道计算机考研 数据结构，配套书籍建议使用正版（盗版的油墨我闻一下都感觉要中毒了）。
• 另外也放上单章笔记的传送门：
  • 【数据结构】第一章：数据结构与算法概述
  • 【数据结构】第二章：线性表
  • 【数据结构】第三章：栈和队列
  • 【数据结构】第四章：串
  • 【数据结构】第五章：树与二叉树
  • 【数据结构】第六章：图
  • 【数据结构】第七章：查找
  • 【数据结构】第八章：排序
• 其他 408 科目：
  • 本文：《数据结构与算法》笔记汇总（超详细合集）
    
  • 《计算机网络》笔记汇总（超详细合集）
  • 《操作系统》笔记汇总（超详细合集）
  • 《计算机组成原理》笔记汇总（超详细合集）

第一章：数据结构与算法概述

一、数据结构的基本概念

1. 数据

• 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
• 早期计算机：只用于处理纯数值型问题
• 现代计算机：经常处理非数值型问题

2. 数据元素、数据项

• 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
• 一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

3. 数据对象、数据结构

• 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
• 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
• 相同的数据元素，可以组成不同的数据结构；
  不同的数据元素，可以组成相同的数据结构。
  • 线性数据结构
  • 网状数据结构

4. 数据类型、抽象数据类型

• 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
  1. 原子类型。其值不可再分的数据类型。
  2. 结构类型。其值可以再分解为若干成分（分量）的数据类型。
• 抽象数据类型（Abstract Date Type，ADT）是抽象数据组织及与之相关的操作。定义一个 ADT，就是在定义一种数据结构。确定了 ADT 的物理结构，才能实现这种数据结构。

二、数据结构的三要素

1. 逻辑结构

1. 集合：各个元素同属一个集合，并无其他关系。
2. 线性结构：数据元素之间是一对一的关系。
   • 除了第一个元素，所有元素都有唯一前驱
   • 除了最后一个元素，所有元素都有唯一后继
3. 树形结构：数据元素之间是一对多的关系。
4. 图结构：数据元素之间是多对多的关系。

2. 数据的运算

• 数据的运算：针对于某种逻辑结构，结合实际需求，定义基本运算
  1. 查找第 $i$ 个数据元素
  2. 在第 $i$ 个位置插入新的数据元素
  3. 删除第 $i$ 个位置的数据元素
• 运算的定义是针对逻辑结构的，指出运算的功能；
  运算的功能是针对物理结构的，指出运算的具体操作步骤。

3. 物理结构（存储结构）

1. 顺序存储
   • 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
2. 链式存储
   • 逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
3. 索引存储
   • 在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
4. 散列存储
   • 根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

• 除了顺序存储外，其他都是非顺序（离散）存储。
• 若采用顺序存储，则各个数据元素在物理上必须是连续的；
  若采用非顺序存储，则各个数据元素在物理上可以是离散的。
• 数据的存储结构会影响存储空间分配的方便程度，也会影响对数据运算的速度

三、算法的基本概念

1. 算法的定义

• 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
• 程序 = 数据结构 + 算法
  • 数据结构是要处理的信息
  • 算法是处理信息的步骤

2. 算法的特性

1. 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
   • 算法必须是有穷的，而程序可以是无穷的
2. 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
3. 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5. 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

3. 算法的目标

1. 正确性：算法应能够正确地解决求解问题。
2. 可读性：算法应具有良好的可读性，以帮助人们理解。
3. 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 高效率和低存储量需求：花的时间少，时间复杂度低；不费内存，空间复杂度低。

四、时间复杂度

• 算法时间复杂度：事前预估算法时间开销 T(n) 与问题规模 n 的关系（T 表示 time）
• 当问题规模 n 足够大时，可只考虑阶数高的部分

$$T_1(n)=3n+3\approx 3n\underrightarrow{简化}{T}_1(n)=O(n)$$$$T_2(n)=n^2+3n+1000\approx n^2\underrightarrow{简化}{T}_2(n)=O(n^2)$$
O 表示“同阶”，同等数量级。即：当 $n\to \infty$ 时，二者之比为常数。
$$T(n)=O(f(n))⟺\underset{n\to \infty }{\lim }\frac{T(n)}{f(n)}=k$$

• 对时间复杂度的度量，遵循以下规则：
  1. 加法规则：
     • 多项相加，只保留最高阶的项，且系数变为 1
     • $T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$
  2. 乘法规则：
     • 多项相乘，都保留
     • $T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$
• 如何计算：
  1. 顺序执行的代码只会影响常数项，可以忽略
  2. 只需挑循环中的一个基本操作分析它的执行次数与 n 的关系即可
  3. 如果有多层嵌套循环，只需关注最深层循环了几次

• 数量级大小对比：常对幂指阶
  $$O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

• 三种复杂度：
  1. 最坏时间复杂度：最坏情况下算法的时间复杂度
  2. 最好时间复杂度：最好情况下算法的时间复杂度
  3. 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间

五、空间复杂度

• 算法空间复杂度：事前预估算法空间开销（内存开销） S(n) 与问题规模 n 的关系（S 表示 Space）
• 若算法所需内存空间为常量，则称算法可原地工作
• 普通程序如何计算：
  1. 找到所占空间大小与问题规模相关的变量
  2. 分析所占空间 x 与问题规模 n 的关系 $x=f(n)$
  3. x 的数量级 O(x) 就是算法空间复杂度 S(n)
• 递归程序如何计算：
  1. 找到递归调用的深度 x 与问题规模 n 的关系 $x=f(n)$
  2. x 的数量级 O(x) 就是算法空间复杂度 S(n)
• 加法规则、乘法规则、数量级大小对比在空间复杂度的问题中同样适用。

第二章：线性表

一、线性表的定义和基本操作

1. 定义

• 线性表（Linear List）是具有相同数据类型的 n（n≥0）个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为 $L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$
  • $a_i$ 是线性表中的 “第 i 个” 元素线性表中的位序（从 1 开始）
  • $a_1$ 是表头元素，$a_n$ 是表尾元素
  • 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2. 基本操作

1. InitList(&L)：初始化表。构造一个空的线性表 L，分配内存空间。
2. DestoryList(&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。
3. ListInsert(&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e。
4. ListDelete(&L,i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
5. LocateElem(L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
6. GetElem(L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。

其他常用操作：

• Length(L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
• PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
• Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。

二、顺序表

1. 顺序表的定义

• 顺序表（sequence list）：用顺序存储的方式实现线性表。
• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2. 顺序表的实现

1. 静态分配：顺序表的表长确定后就无法更改

   #define MaxSize 10				// 定义最大长度
   typedef struct {
   	ElemType data[MaxSize];		// 用静态的“数组”存放数据元素
   	int length;					// 顺序表的当前长度
   } SqList;						// 顺序表的类型定义（静态分配方式）
   

2. 动态分配：使用 malloc 和 free 申请或释放内存空间

   #define InitSize 10		// 顺序表的初始长度
   typedef struct {
       ElemType *data;		// 指示动态分配数组的指针
       int MaxSize;		// 顺序表的最大容量
       int length;			// 顺序表的当前长度
   }SeqList;				// 顺序表的类型定义（动态分配方式）
   

3. 顺序表的特点

1. 随机访问，即可以在 O(1) 时间内找到第 i 个元素。
2. 存储密度高，每个节点只存储数据元素
3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
4. 插入、删除操作不方便，需要移动大量的元素

4. 顺序表的插入

• ListInsert(&L,i,e)：插入操作。在表 L 中的第 i 个位置（位序）上插入指定元素 e。

  // 静态分配实现顺序表的代码省略...
  
  bool ListInsert(SqList &L, int i, int e) {
      if (i < 1 || i > L.length + 1) {        // 判断 i 的范围是否有效
          return false;
      }
      if (L.length == MaxSize) {              // 当前存储空间已满，不能插入
          return false;
      }
      for (int j = L.length; j >= i; j--) {   // 将第 i 个元素及之后的元素后移
          L.data[j] = L.data[j - 1];
      }
      L.data[i - 1] = e;                      // 在位置 i 处放入 e
      L.length++;                             // 长度加 1
      return true;
  }
  

• 平均时间复杂度：O(n)

5. 顺序表的删除

• ListDelete(&L,i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。

  // 静态分配实现顺序表的代码省略...
  	
  bool ListDelete(SqList &L, int i, int &e) {
      if (i < 1 || i > L.length) {            // 判断 i 的范围是否有效
          return false;
      }
      e = L.data[i - 1];                      // 将被删除的元素赋值给 e
      for (int j = i; j < L.length; j++) {    // 将第 i 个位置后的元素前移
          L.data[j - 1] = L.data[j];
      }
      L.length--;                             // 线性表长度减 1
      return true;
  }
  

• 平均时间复杂度：O(n)

6. 顺序表的查找

• GetElem(L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。

  int GetItem(SqList L, int i) {
      return L.data[i - 1];
  }
  

  时间复杂度：O(1)

• LocateElem(L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
  == 仅适用于基本数据类型，结构体需要依次对比各个分量来判断是否相等。

  int LocateElem(SqList L, int e) {
      for (int i = 0; i < L.length; i++) {
          if (L.data[i] == e) {
              return i + 1;   // 数组下标为 i 的元素值等于 e，返回其位序 i+1
          }
      }
      return 0;               // 退出循环，说明查找失败
  }
  

  时间复杂度：O(n)

三、单链表

1. 单链表的定义

• 每个结点除了存放数据元素外，还要存储指向下一个结点的指针
• 优点：不要求大片连续空间，改变容量方便
• 缺点：不可随机存取，要耗费一定空间存放指针

2. 单链表的实现

• 定义单链表

  struct LNode{           // 定义单链表结点类型
      ElemType data;      // 每个结点存放一个数据元素
      struct LNode *next; // 指针指向下一个结点
  };
  // typedef struct LNode LNode;		// 重命名
  // typedef struct LNode *LinkList;	// 重命名，强调这是一个单链表
  
  // 新增一个结点，用 LNode * 强调这是一个结点
  struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));
  

• 初始化不带头结点的单链表

  #include <stdbool.h>
  #include <stdlib.h>
  
  typedef struct LNode{   // 定义单链表结点类型
      int data;           // 每个结点存放一个数据元素
      struct LNode *next; // 指针指向下一个结点
  } LNode, *LinkList;
  
  bool InitList(LinkList &L) {
      L = NULL;           // 空表，暂时还没有任何结点（防止脏数据）
      return true;
  }
  
  void test() {
      LinkList L;         // 声明一个指向单链表的指针
      InitList(L);
  }
  

• 初始化带头结点的单链表

  // 省略定义单链表的代码...
  
  bool InitList(LinkList &L) {
      L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
      if (L == NULL) {    // 内存不足，分配失败
          return false;
      }
      L->next = NULL;     // 头结点之后暂时还没有结点
      return true;
  }
  

3. 单链表的插入

• 带头结点按位序插入：平均时间复杂度 O(n)

  bool ListInsert(LinkList &L, int i, int e) {
      if (i < 1) return false;
      LNode *p;       // 指针 p 指向当前扫描到的结点
      int j = 0;      // 当前 p 指向的是第几个结点
      p = L;          // L 指向头结点，头结点是第 0 个结点（不存数据）
      while (p != NULL && j < i - 1) {    // 循环找到第 i-1 个结点
          p = p->next;
          j++;
      }
      if (p == NULL) return false;        // i 值不合法
      LNode *s = (LNode *)malloc(sizeof(LNode));
      s->data = e;
      s->next = p->next;
      p->next = s;    // 将结点 s 连到 p 之后
      return true;    // 插入成功
  }
  

• 不带头结点按位序插入

  bool ListInsert(LinkList &L, int i, int e) {
      if (i < 1) return false;
      if (i == 1) {       // 插入第 1 个结点的操作与其他结点操作不同
          LNode *s = (LNode *)malloc(sizeof(LNode));
          s->data = e;
          s->next = L;
          L = s;          // 头指针指向新结点
          return true;
      }
      LNode *p;           // 指针 p 指向当前扫描到的结点
      int j = 1;          // 当前 p 指向的是第几个结点
      p = L;              // p 指向第一个结点（不是头结点）
      while (p != NULL && j < i - 1) {    // 循环找到第 i-1 个结点
          p = p->next;
          j++;
      }
      if (p == NULL) return false;        // i 值不合法
      LNode *s = (LNode *)malloc(sizeof(LNode));
      s->data = e;
      s->next = p->next;
      p->next = s;
      return true;        // 插入成功
  }
  

• 指定结点的后插操作

  bool InsertNextNode(LNode *p, int e) {
      if (p == NULL) return false;
      LNode *s = (LNode *)malloc(sizeof(LNode));
      if (s == NULL) return false;    // 内存分配失败
      s->data = e;                    // 用结点 s 保存数据元素 e
      s->next = p->next;
      p->next = s;                    // 将结点 s 连到 p 之后
      return true;
  }
  

• 指定结点的前插操作：偷天换日

  bool InsertPriorNode(LNode *node_p, int data) {
      if (node_p == NULL) return false;
      LNode *new_node = (LNode *)malloc(sizeof(LNode));
      if (new_node == NULL) return false; // 内存分配失败
      new_node->next = node_p->next;
      node_p->next = new_node;            // 新结点 new_node 连到 node_p 之后
      new_node->data = node_p->data;      // 将 node_p 中元素复制到 new_node 中
      node_p->data = data;                // node_p 中元素覆盖为 data
      return true;
  }
  

4. 单链表的删除

• 带头结点按位序删除：平均时间复杂度 O(n)

  bool ListDelete(LinkList &L, int i, int &e) {
      if (i < 1) return false;
      LNode *p;
      int j = 0;
      p = L;
      while (p->next != NULL && j < i - 1) {
          p = p->next;
          j++;
      }
      if (p == NULL) return false;        // i 值不合法
      if (p->next == NULL) return false;  // 第 i-1 个结点之后已无其他结点
      LNode *q = p->next;     // 令 q 指向被删除的结点
      e = q->data;            // 用 e 返回元素的值
      p->next = q->next;      // 将 *q 结点从链中断开
      free(q);                // 释放结点的存储空间
      return true;            // 删除成功
  }
  

• 删除指定结点：偷天换日
  但是如果要删除最后一个结点，只能从链头开始查找

  bool DeleteNode(LNode *p) {
      if (p == NULL) return false;
      LNode *q = p->next;     // 另 q 指向 *p 的后继结点
      p->data = p->next->data;// 和后继结点交换数据域
      p->next = q->next;      // 将 *q 结点从链中断开
      free(q);                // 释放后继结点的存储空间
      return true;
  }
  

5. 单链表的查找

• 按位查找：平均时间复杂度 O(n)

  LNode * GetElem(LinkList L, int i) {
      if (i < 0) return NULL;
      LNode *p;
      int j = 0;
      p = L;
      while (p != NULL && j < i) {	// 循环找到第 i 个结点
          p = p->next;
          j++;
      }
      return p;
  }
  

• 按值查找：平均时间复杂度 O(n)

  LNode *LocateElem(LinkList L, int e) {
      LNode *p = L->next;
      // 从第一个结点开始查找数据域为 e 的结点
      while (p != NULL && p->data != e) {
          p = p->next;
      }
      return p;   // 找到后返回该结点指针，否则返回 NULL
  }
  

6. 单链表的建立

• 尾插法：平均时间复杂度 O(n)

  LinkList List_TaiInsert(LinkList &L) {		// 正向建立单链表
      int x;
      L = (LinkList)malloc(sizeof(LNode));	// 建立头结点
      LNode *s, *r = L;						// r 为表尾指针
      scanf("%d", &x);
      while (x != 9999) {						// 输入 9999 表示结束
          s = (LNode *)malloc(sizeof(LNode));
          s->data = x;
          r->next = s;
          r = s;                              // r 指向新的表尾结点
          scanf("%d", &x);
      }
      r->next = NULL;                         // 表尾结点指针置空
      return L;
  }
  

• 头插法：用于链表的逆置

  LinkList List_HeadInsert(LinkList &L) {		// 逆向建立单链表
      LNode *s;
      int x;
      L = (LinkList)malloc(sizeof(LNode));    // 建立头结点
      L->next = NULL;                         // 初始为空链表
      scanf("%d", &x);
      while (x != 9999) {
          s = (LNode *)malloc(sizeof(LNode)); // 创建新结点
          s->data = x;
          s->next = L->next;
          L->next = s;                        // 将新结点插入表中，L 为头指针
          scanf("%d", &x);
      }
      return L;
  }
  

四、双链表

• 双链表：在单链表的基础上，再增加一个指向前驱结点的指针域。

• 双链表的实现

   typedef struct DNode {
       ElemType data;
       struct DNode *prior, *next;
   } DNode, *DLinklist;
  

• 双链表的初始化

  bool InitDLinkList(DLinklist &L) {
      L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
      if (L == NULL) return false;            // 内存不足，分配失败
      L->prior = NULL;    // 头结点的 prior 永远指向 NULL
      L->next = NULL;     // 头结点之后暂时还没有结点
      return true;
  }
  

• 双链表的后插操作

  bool InsertNextDNode(DNode *p, DNode *s) {
      if (p == NULL || s == NULL) return false;
      s->next = p->next;
      if (p->next != NULL) {      // 如果 p 结点有后继结点
          p->next->prior = s;
      }
      s->prior = p;
      p->next = s;
      return true;
  }
  

• 双链表的后删操作

  bool DeleteNextDNode(DNode *p) {
      if (p == NULL) return false;
      DNode *q = p->next;             // 找到 p 的后继节点 q
      if (q == NULL) return false;    // p 没有后继结点
      p->next = q->next;
      if (q->next != NULL) {          // q 结点不是最后一个结点
          q->next->prior = p;
      }
      free(q);
      return true;
  }
  

• 双链表的销毁操作

  void DestoryDLinklist(DLinklist &L) {
      while (L->next != NULL) {   // 循环释放各个数据结点
          DeleteNextDNode(L);
      }
      free(L);    // 释放头结点
      L = NULL;   // 头指针指向 NULL
  }
  

• 双链表的遍历：链表不具备随机存取特性，查找操作只能通过顺序遍历实现，平均时间复杂度为 O(n)

五、循环链表

• 在单链表和双链表的基础上进行改进，实现循环单链表和循环双链表。

1. 循环单链表

• 循环单链表：表尾结点的 next 指针指向头结点。
  从一个结点触发可以找到其他任何一个结点。

• 循环单链表初始化

  typedef struct LNode {
      int data;
      struct LNode *next;
  } LNode, *LinkList;
  
  bool InitList(LinkList &L) {
      L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
      if (L == NULL) return false;    // 内存不足，分配失败
      L->next = L;    // 头结点 next 指向头结点
      return true;
  }
  

• 循环单链表判断是否为空

  // 判断循环单链表是否为空
  bool Empty(LinkList L) {
      return L->next == L;
  }
  

• 循环单链表判断结点是否为尾结点

  bool isTail(LinkList L, LNode *p) {
      return p->next == L;
  }
  

2. 循环双链表

• 循环双链表：表头结点的 prior 指向表尾结点；表尾结点的 next 指向头结点。

• 循环双链表初始化

  typedef struct DNode {
      int data;
      struct DNode *next,*prior;
  } DNode, *DLinklist;
  
  bool InitDLinkList(DLinklist &L) {
      L = (DNode *) malloc(sizeof(DLinklist));
      if (L == NULL) return false;
      L->next = L;    // 头结点的 next 指向头结点
      L->prior = L;   // 头结点的 prior 指向头结点
      return true;
  }
  

• 循环双链表的判空和判尾和循环单链表一样。

• 循环双链表的后插和后删操作相较于双链表，不需要考虑前驱和后继是否为 NULL 的情况

六、静态链表

1. 静态链表的定义

• 静态链表：用数组的方式实现的链表。分配一整片连续的内存空间，各个结点集中安置。在结点中存放数据元素和游标（下一个结点的数组下标）。
• 0 号结点充当 “头结点”，游标为 -1 表示已经到达表尾。
• 若每个数据元素 4B，每个游标 4B，每个结点共 8B，起始地址为 addr，则 $e_i$ 的存放地址为 addr + 8 * (i + 1)

#define MaxSize 10
typedef struct {
	ElemType data;
	int next;
} SLinkList[MaxSize];

• 应用场景：不支持指针的低级语言；数据元素数量固定不变的场景（如文件分配表 FAT）
• 优点：增删操作不需要大量移动元素
• 缺点：不能随机存取，只能从头结点开始一次往后查找；容量固定不变

2. 静态链表的初始化

1. 把第一个结点的 next 设为 -1
2. 把其他结点的 next 设为一个特殊值表示结点空闲

bool InitSLinkList(SLinkList L) {
    L[0].next = -1;
    for (int i = 1; i < MaxSize; i++) {
        L[i].next = -2;
    }
    return true;
}

3. 静态链表的插入

• 插入位序为 i 的结点
  1. 找到一个空的结点，存入数据元素
  2. 从头结点出发找到位序为 i-1 的结点
  3. 修改新结点的 next
  4. 修改 i-1 号结点的 next

4. 静态链表的删除

1. 从头结点出发找到前驱结点
2. 修改前驱结点的游标
3. 被删除结点 next 设为特殊值

七、顺序表和链表对比

	顺序表（顺序存储）	链表（链式存储）
逻辑结构	都属于线性表，都是线性结构
创建	需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源	只需分配一个头结点或头指针，之后方便拓展
销毁	静态分配系统自动回收空间，动态分配需要手动free	依次删除各个结点
插入和删除	需要将后续元素都后移 / 前移	只需修改指针即可
查找	按位查找T(n)=O(1),按值查找T(n)=O(n)	按位查找和按值查找T(n)=O(n)
优点	支持随机存取、存储密度高	离散的小空间分配方便，改变容量方便
缺点	大片连续空间分配不方便，改变容量不方便	不可随机存取，存储密度低

• 表长难以预估、经常要增加 / 删除元素，选择使用链表。
• 表长可预估、查询（搜索）操作较多，选择使用顺序表。

第三章：栈和队列

一、栈

1. 栈的定义

• 栈（Stack）是只允许在一端进行插入或删除操作的线性表。
• 空栈：空的线性表。
• 栈顶：允许插入和删除的一端，也称栈顶元素。
• 栈底：不允许插入和删除的一端，也称栈底元素。
• 特点：后进先出（Last In First Out）LIFO
• n 个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n+1}{C}_{2n}^n$

2. 栈的基本操作

1. InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间
2. DestroyStack(&L)：销毁栈。销毁并释放栈 S 所占用的内存空间。
3. Push(&S,x)：进栈，若栈 S 未满，则将 x 加入使之称为新栈顶。
4. Pop(&S,&x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
5. GetTop(S,&x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。

二、顺序栈

1. 顺序栈的实现

• 缺点：栈的大小不可变

• 定义

  #define MaxSize 10
  typedef struct {
      int data[MaxSize];  // 静态数组存放栈中元素
      int top;            // 栈顶指针
  } SqStack;
  

• 初始化

  void InitStack(SqStack &S) {
      S.top = -1;     // 初始化栈顶指针
  }
  

• 判空

  bool StackEmpty(SqStack S) {
      return S.top == -1;
  }
  

2. 顺序栈的基本操作

• 进栈（增）

  bool Push(SqStack &S, int x) {
      if (S.top == MaxSize - 1)
          return false;       // 栈满，报错
      S.top = S.top + 1;      // 指针先加 1
      S.data[S.top] = x;      // 新元素入栈
      return true;
  }
  

• 出栈（删），只是逻辑上删除

  bool Pop(SqStack &S, int &x) {
      if (S.top == -1)
          return false;   // 栈空，报错
      x = S.data[S.top];  // 栈顶元素先出栈
      S.top = S.top - 1;  // 指针再减 1
      return true;
  }
  

• 读栈顶元素（查）

  bool GetTop(SqStack &S, int &x) {
      if (S.top == -1)
          return false;   // 栈空，报错
      x = S.data[S.top];
      return true;
  }
  

3. 两种实现方式对比

• 两种实现方式分别是
  1. 初始化时 top=-1，指向当前可以插入的位置
  2. 初始化时 top=0，指向下一个可以插入的位置

	方式一	方式二
初始化时 / 栈空条件	top = -1	top = 0
入栈	S.data[++S.top] = x	S.data[S.top++] = x
出栈	x = S.data[S.top--]	x = S.data[--S.top]
获得栈顶元素	x = S.data[S.top]	x = S.data[S.top - 1]
栈满条件	top == MaxSize - 1	top == MaxSize

4. 共享栈

• 为了提高内存空间利用率，让两个顺序栈共享同一片空间

• 实现

  #define MaxSize 10
  typedef struct {
  	int data[MaxSize];	// 静态数组存放栈中元素
  	int top0;			// 0 号栈栈顶指针
  	int top1;			// 1 号栈栈顶指针
  } ShStack;
  

• 初始化

  void InitStack(ShStack &S) {
  	S.top0 = -1;
  	S.top1 = MaxSize;
  }
  

• 栈满条件：top0 + 1 == top1

三、链栈

1. 链栈的实现

• 定义

  typedef struct LinkNode {
      int data;           // 数据域
      LinkNode *next;     // 指针域
  } LinkNode, *LiStack;   // 栈类型定义
  

2. 链栈的基本操作

• 基本操作和单链表类似。在链栈中，不带头结点的相对简单。

• 带头结点的链栈

  // 省略链栈定义...
  
  // 初始化
  bool InitStack(LiStack &L) {
      L = (LinkNode *)malloc(sizeof(LinkNode));
      if (!L) return false;
      L->next = NULL;
      return true;
  }
  
  // 销毁
  bool DestroyStack(LiStack &L) {
      LinkNode *p = L->next;
      while (p != NULL) {
          L->next = p->next;
          free(p);
          p = L->next;
      }
      free(L);
      return true;
  }
  
  // 入栈
  bool Push(LiStack &L, int x) {
      LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
      if (!p) return false;
      p->data = x;
      p->next = L->next;
      L->next = p;
      return true;
  }
  
  // 出栈
  bool Pop(LiStack &L, int &x) {
      LinkNode *p = L->next;
      if (!p) return false;
      x = p->data;
      L->next = p->next;
      free(p);
      return true;
  }
  
  // 读栈顶元素
  bool GetTop(LiStack &L, int &x) {
      LinkNode *p = L->next;
      if (!p) return false;
      x = p->data;
      return true;
  }
  
  // 判空
  bool StackEmpty(LiStack L) {
      return L->next == NULL;
  }
  

• 不带头结点的链栈

  // 省略链栈定义...
  
  // 初始化
  bool InitStack(LiStack &L) {
      L = NULL;
      return true;
  }
  
  // 销毁
  bool DestroyStack(LiStack &L) {
      while (L != NULL) {
          LinkNode *p = L;
          L = L->next;
          free(p);
      }
      return true;
  }
  
  // 入栈
  bool Push(LiStack &L, int x) {
      LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
      if (!p) return false;
      p->data = x;
      p->next = L;
      L = p;
      return true;
  }
  
  // 出栈
  bool Pop(LiStack &L, int &x) {
      if (!L) return false;
      x = L->data;
      LinkNode *p = L;
      L = L->next;
      free(p);
      return true;
  }
  
  // 读栈顶元素
  bool GetTop(LiStack &L, int &x) {
      if (!L) return false;
      x = L->data;
      return true;
  }
  

四、队列

1. 队列的定义

• 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表。
• 空队列：空的线性表。
• 队头：允许删除的一端，最靠近队头的元素称为队头元素。
• 队尾：允许插入的一端，最靠近队尾的元素称为队尾元素。
• 特点：先进先出（First In First Out）FIFO

2. 队列的基本操作

1. InitQueue(&Q)：初始化队列，构造一个空队列 Q。
2. DestroyQueue(&Q)：销毁队列，销毁并释放队列 Q 所占用的内存空间。
3. EnQueue(&Q,x)：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾。
4. DeQueue(&Q,&x)：出队，若队列 Q 非空，删除队头元素，并用 x 返回。
5. GetHead(Q,&x)：读队头元素，若队列 Q 非空，则将队头元素赋值给 x。

3. 双端队列

• 双端队列：只允许从两端插入、两端删除的线性表
• 输入受限的双端队列：只允许从一端插入、两端删除的线性表
• 输出首先的双端队列：只允许从两端插入、一端删除的线性表

五、顺序队列

1. 顺序队列的实现

• 定义有三种方式

  1. 队头和队尾指针初始化时都指向 0，但会浪费一个存储空间

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
     } SqQueue;
     

  2. 定义一个 size 变量存储队列当前长度，初始化时 size = 0，插入成功 size++，删除成功 size--

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
         int size;	// 队列当前长度
     } SqQueue;
     

  3. 定义一个 tag 变量存储最近进行的时删除还是插入，初始化时 tag = 0，插入成功 tag = 1，删除成功 tag = 0

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
         int tag;	// 最近进行的是删除 / 插入
     } SqQueue;
     

• 初始化，front 指向队头元素，rear 指向队尾元素的后一个位置

  void InitQueue(SqQueue &Q) {
      // 初始化时，队头、队尾指针指向 0
      Q.front = Q.rear = 0;
  }
  

  rear 也可以指向最后一个元素：front = 0; rear = n - 1;，类似于顺序栈的第二种实现方式。

• 判空

  bool QueueEmpty(SqQueue Q) {
      return Q.front == Q.rear;
  }
  

2. 顺序队列的基本操作

都是基于第一种实现方式

• 入队（增）

  bool EnQueue(SqQueue &Q, int x) {
      if ((Q.rear + 1) % MaxSze == Q.front)
          return false;                  // 队满报错
      Q.data[Q.rear] = x;                // 将 x 插入队尾
      Q.rear = (Q.rear + 1) % MaxSze;    // 队尾指针加 1 取模
      return true;
  }
  

• 出队（删）

  bool DeQueue(SqQueue &Q, int &x) {
      if (Q.front == Q.rear)
          return false;       // 队空报错
      x = Q.data[Q.front];
      Q.front = (Q.front + 1) % MaxSze;
      return true;
  }
  

• 读队头元素

  bool GetHead(SqQueue Q, int &x) {
      if (Q.front == Q.rear)
          return false;       // 队空报错
      x = Q.data[Q.front];
      return true;
  }
  

• 获取队列元素个数：(rear + MaxSize - front) % MaxSize

3. 三种实现方式对比

	初始化时	队空条件	队满条件
方式一		Q.rear == Q.front	(Q.rear + 1) % MaxSize == Q.front
方式二	size = 0;	size == 0	size == MaxSize
方式三	tag = 0;	front == rear && tag == 0	front == rear && tag == 1

六、链队列

1. 链队列的实现

• 定义

  typedef struct LinkNode {   // 链式队列结点
      int data;
      struct LinkNode *next;
  } LinkNode;
  
  typedef struct {            // 链式队列
      LinkNode *front, *rear; // 队列的队头和队尾指针
  } LinkQueue;
  

2. 链队列的基本操作

• 带头结点的链队列

  // 初始化
  void InitQueue(LinkQueue &Q) {
      Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
      Q.front->next = NULL;
  }
  
  // 判空
  bool QueueEmpty(LinkQueue Q) {
      return Q.front == Q.rear;
  }
  
  // 入队
  void EnQueue(LinkQueue &Q, int x) {
      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
      s->data = x;
      s->next = NULL;
      Q.rear->next = s;   // 新结点插入到 rear 之后
      Q.rear = s;         // 修改表尾指针
  }
  
  // 出队
  bool DeQueue(LinkQueue &Q, int &x) {
      if (Q.front == Q.rear)
          return false;           // 空队列
      LinkNode *p = Q.front->next;
      x = p->data;                // 用变量 x 返回队头元素
      Q.front->next = p->next;    // 修改头结点的 next 指针
      if (Q.rear == p)            // 此次时最后一个结点出队
          Q.rear = Q.front;       // 修改 rear 指针
      free(p);
      return true;
  }
  

• 不带头结点

  // 初始化
  void InitQueue(LinkQueue &Q) {
      Q.front = Q.rear = NULL;
  }
  
  // 判空
  bool QueueEmpty(LinkQueue Q) {
      return Q.front == NULL;
  }
  
  // 入队
  void EnQueue(LinkQueue &Q, int x) {
      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
      s->data = x;
      s->next = NULL;
      if (Q.front == NULL) {      // 在空队列中插入第一个元素
          Q.front = Q.rear = s;   // 插入队头队尾指针
      } else {
          Q.rear->next = s;       // 新结点插入到 rear 结点之后
          Q.rear = s;             // 修改 rear 指针
      }
  }
  
  // 出队
  bool DeQueue(LinkQueue &Q, int &x) {
      if (Q.front == NULL)
          return false;       // 空队列
      LinkNode *p = Q.front;  // p 指向此次出队的结点
      x = p->data;            // 用变量 x 返回队头元素
      Q.front = p->next;      // 修改 front 指针
      if (Q.rear == p) {      // 此次是最后一个结点出队
          Q.front = NULL;     // 修改队首指针
          Q.rear = NULL;      // 修改队尾指针
      }
      free(p);
      return true;
  }
  

七、栈的应用

1. 括号匹配

• 算法思路：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。
• 匹配失败的情况：
  1. 左括号单身
  2. 右括号单身
  3. 左右括号不匹配
• 流程图

• 算法实现

#include <stdio.h>
#include <string.h>

#define MaxSize 10

typedef struct {
    char data[MaxSize];
    int top;
} SqStack;

bool BracketCheck(char str[], int length) {
    // 定义栈
    SqStack stack;
    // 初始化栈
    stack.top = -1;
    // 遍历字符串
    for (int i = 0; i < length; i++) {
        // 如果是左括号入栈
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            stack.data[++stack.top] = str[i];
        }
        // 如果是右括号
        else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            // 栈空，右括号单身
            if (stack.top == -1) return false;
            // 出栈
            char symbol = stack.data[stack.top--];
            // 匹配失败
            if (str[i] == ')' && symbol != '(') return false;
            if (str[i] == ']' && symbol != '[') return false;
            if (str[i] == '}' && symbol != '{') return false;
        }
    }
    // 栈空则匹配成功，栈内如果还有元素，则左括号单身
    return stack.top == -1;
}

int main() {
    char str[20];
    gets(str);
    printf("%s", BracketCheck(str, (int)strlen(str)) ? "true" : "false");
}

2. 表达式求值

• 表达式由三部分组成：操作数、运算符、界限符，例如：1+2×(3-4)

• 三种表达式

  1. 中缀表达式：最常见的表达式，如 1+2
  2. 前缀表达式：也称波兰表达式（Polish Notation），如 +12
  3. 后缀表达式：也称逆波兰表达式（Reverse Polish Notation），如 12+

• 互转举例

  中缀表达式	前缀表达式	后缀表达式
  a+b	+ab	ab+
  a+b+c	-+abc	ab+c-
  a+b-c*d	-+ab*cd	ab+cd*-

• 中缀转后缀（手算）
  1. 确定中缀表达式中各个运算符的运算顺序（遵循左优先原则：只要左边的运算符能先计算，就优先算左边的）
  2. 选择下一个运算符，按照【左操作数 右操作数 运算符】的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，就继续 ②

• 中缀转后缀（机算）
  1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
  2. 从左到右处理各个元素，直到末尾。可能遇到三种情况：
     • ① 遇到操作数：直接加入后缀表达式
     • ② 遇到界限符：遇到 “(” 直接入栈，遇到 “)” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “(” 为止。注意：“(” 不加入后缀表达式
     • ③ 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “(” 或栈空则停止。之后再把当前运算符入栈
  3. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

• 后缀表达式的计算（机算）
  1. 从左往右扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数，则压入栈，并回到 ①；否则执行 ③
  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是右操作数），执行相应运算，运算结果压回栈顶，回到 ①
  4. 若表达式合法，则最后栈中只会留下一个元素，就是最终结果

• 中缀转前缀（手算）
  1. 确定中缀表达式中各个运算符的运算顺序（遵循右优先原则：只要右边的运算符能先计算，就优先算右边的）
  2. 选择下一个运算符，按照【运算符 左操作数 右操作数】的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，就继续 ②

• 前缀表达式的计算（机算）
  1. 从右往左扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数，则压入栈，并回到 ①；否则执行 ③
  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是左操作数），执行相应运算，运算结果压回栈顶，回到 ①
  4. 若表达式合法，则最后栈中只会留下一个元素，就是最终结果

• 中缀表达式的计算（中缀转后缀 + 后缀计算）
  1. 初始化两个栈，操作数栈和运算符栈
  2. 若扫描到操作数，压入操作数栈
  3. 若扫描到运算符或界限符，则按照 “中缀转后缀” 相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

• 中缀计算代码实现（仅实现算法，没做错误处理）

#include <cstdio>
#include <cstdlib>
#include <cstring>

// 操作数栈
typedef struct {
    float number[20];
    int top;
} OpStack;

// 运算符栈
typedef struct {
    char cal[20];
    int top;
} CalStack;

void test() {
    // 初始化栈
    OpStack op_stack;
    op_stack.top = -1;
    CalStack cal_stack;
    cal_stack.top = -1;

    // 输入
    char str[100];
    gets(str);

    // 数字寄存器
    char number[20];
    int index = 0;
    // 从左往右扫描
    for (int i = 0; i < strlen(str); i++) {
        // 如果是数字，包含小数点
        if (str[i] >= '0' && str[i] <= '9' || str[i] == '.') {
            // 存入数字寄存器
            number[index++] = str[i];
        } else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')') {
            // 如果数字寄存器有数字
            if (index > 0) {
                // 入操作数栈
                number[index] = '\0';
                op_stack.number[++op_stack.top] = atof(number);
                // 重置数字寄存器
                index = 0;
            }

            // 空运算符栈或遇到左括号，先压入运算符栈
            if (cal_stack.top == -1 || str[i] == '(') {
                cal_stack.cal[++cal_stack.top] = str[i];
                continue;
            }
            // 获取上一个运算符
            char cal = cal_stack.cal[cal_stack.top];
            // 如果前面是左括号，则直接压入运算符栈
            if (cal == '(') {
                cal_stack.cal[++cal_stack.top] = str[i];
                continue;
            }
            // 左右操作数
            float left = 0, right = 0;
            // 循环
            while (true) {
                // 栈空，跳出循环
                if (cal_stack.top == -1) break;
                // 先获取栈顶运算符
                cal = cal_stack.cal[cal_stack.top];
                // 如果遇到左括号，跳出循环
                if (cal == '(') {
                    if (str[i] == ')') cal_stack.top--;
                    break;
                }
                // 如果扫到加减，则弹完，如果扫到乘除，只弹乘除
                if ((str[i] == '*' || str[i] == '/') && (cal == '+' || cal == '-')) break;
                cal_stack.top--;
                // 获取左右操作数
                right = op_stack.number[op_stack.top--];
                left = op_stack.number[op_stack.top--];

                // 运算后压入操作数栈
                switch (cal) {
                    case '+':
                        op_stack.number[++op_stack.top] = left + right;
                        break;
                    case '-':
                        op_stack.number[++op_stack.top] = left - right;
                        break;
                    case '*':
                        op_stack.number[++op_stack.top] = left * right;
                        break;
                    case '/':
                        op_stack.number[++op_stack.top] = left / right;
                        break;
                    default: break;
                }
            }
            // 如果扫到的是不是右括号，则把当前运算符压入运算符栈
            if (str[i] != ')') {
                cal_stack.cal[++cal_stack.top] = str[i];
            }
        }
    }

    // 把表达式最后一个数放入操作数栈
    if (index > 0) {
        number[index] = '\0';
        op_stack.number[++op_stack.top] = atof(number);
    }
    // 扫描结束，把剩余的运算符栈清空
    while (cal_stack.top != -1) {
        char cal = cal_stack.cal[cal_stack.top--];
        float right = op_stack.number[op_stack.top--];
        float left = op_stack.number[op_stack.top--];
        switch (cal) {
            case '+':
                op_stack.number[++op_stack.top] = left + right;
                break;
            case '-':
                op_stack.number[++op_stack.top] = left - right;
                break;
            case '*':
                op_stack.number[++op_stack.top] = left * right;
                break;
            case '/':
                op_stack.number[++op_stack.top] = left / right;
                break;
            default: break;
        }
    }

    // 输出
    for (int i = 0; i <= op_stack.top; i++) {
        printf("%f\n", op_stack.number[i]);
    }
}

int main() {
    test();
    return 0;
}

3. 递归

• 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
• 函数调用时，需要用一个栈存储：
  1. 调用返回地址
  2. 实参
  3. 局部变量
• 适合用递归算法解决：可以把原始问题转换成属性相同，但规模较小的问题
• 递归调用时，函数调用栈可称为 “递归调用栈”
  • 每进入一层递归，就将递归调用所需信息压入栈顶
  • 每退出一层递归，就从栈顶弹出相应信息
• 递归缺点：效率低；太多层递归可能会导致栈溢出；可能包含很多重复计算
• 可以自定义栈将递归算法改造成非递归算法

八、队列的应用

1. 树的层次遍历：在 “树” 章节中会提到
2. 图的广度优先遍历：在 “图” 章节中会提到
3. 处理机调度的先来先服务（FCFS）策略。

九、特殊矩阵的压缩存储

1. 数组的存储结构

1. 一维数组：
   • 各数组元素大小相同，且物理上连续存放
   • 数组元素 a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0 ≤ i）
2. 二维数组：
   • 行优先存储：M 行 N 列的二维数组 b[M][N] 中，b[i][j] 的存储地址 = LOC + (i * N + j) * sizeof(ElemType)
   • 列优先存储：M 行 N 列的二维数组 b[M][N] 中，b[i][j] 的存储地址 = LOC + (j * N + i) * sizeof(ElemType)

2. 特殊矩阵

$$\left(\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,n-1}& a_{1,n}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,n-1}& a_{2,n}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{n-1,1}& a_{n-1,2}& \cdots & a_{n-1,n-1}& a_{n,-1n}\\ a_{n,1}& a_{n,2}& \cdots & a_{n,n-1}& a_{n,n}\end{array}\right)$$

1. 对称矩阵
   • 若 n 阶方阵中任意一个元素 $a_{i,j}$ 都有 $a_{i,j}=a_{j,i}$，则该矩阵为对称矩阵。
   • 三个区域 $\{\begin{array}{l}i<j，上三角区\\ i=j，主对角线\\ i>j，下三角区\end{array}$
   • 存储策略：只存储主对角线 + 下三角区（或主对角线 + 上三角区）
   • 数组长度（从 1 开始）：$\frac{(1+n)\times n}{2}$
   • 按行优先的原则，$a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{l}\frac{i\times (i-1)}{2}+j-1，i\ge j（下三角区和主对角线元素）\\ \frac{j\times (j-1)}{2}+i-1，i<j（上三角区元素a_{i,j}=a_{j,i}）\end{array}$$
2. 三角矩阵
   • 上三角矩阵：除了主对角线和上三角区，其余元素都相同。
   • 下三角矩阵：除了主对角线和下三角区，其余元素都相同。
   • 存储策略：和对称矩阵相似，并在最后一个位置存储常量 C。
   • 数组长度（从 1 开始）：$\frac{(1+n)\times n}{2}+1$
   • 按行优先的原则，下三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}\frac{i\times (i-1)}{2}+j-1,& \text{i≥j（下三角区和主对角线元素）}\\ \frac{n\times (n+1)}{2},& \text{i<j（上三角区元素都是 C）}\end{array}$$
   • 按行优先的原则，上三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}\frac{(i-1)\times (2n-i+2)}{2}+(j-i),& \text{i≥j（下三角区和主对角线元素）}\\ \frac{n\times (n+1)}{2},& \text{i<j（上三角区元素都是 C）}\end{array}$$
3. 三对角矩阵
   • 又称带状矩阵，当 $|i-j|>1$ 时，有 $a_{i,j}=0（1\le i,j\le n）$
   • 存储策略：只存储带状部分。
   • 数组大小：$3n-2$
   • 按行优先的原则，下三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}2i+j-3,& \text{|i-j|≤1（带状部分）}\\ 0,& \text{|i-j|>1}\end{array}$$
   • 已知数组下标 $k$，求 $i,j$：
     $$(i,j)\{\begin{array}{l}i=\lceil \frac{(k+2)}{3}\rceil \\ j=k-2i+3\end{array}$$
4. 稀疏矩阵
   • 非零元素远远少于矩阵元素的个数
   • 存储策略：
     • ① 顺序存储——三元组 <行，列，值>
     • ② 链式存储——十字链表法：定义行指针数组和列指针数组，指向向下域或向右域的非零元素，每个非零数据节点包含 <行，列，值，指向同列的下一个元素，指向同行的下一个元素>

第四章：串

一、串的定义

• 串，即字符串（String）是由零个或多个字符组成的有限序列（特殊的线性表），数据元素之间呈线性关系。一般记为 $$S{=}^{\prime }{a}_1{a}_2......a_n^{\prime }(n\ge 0)$$其中，$S$ 是串名，单引号括起来的字符序列是串的值；
  $a_i$ 可以是字母、数字或其他字符；
  串中字符的个数 $n$ 称为串的长度。$n=0$ 时的串称为空串（用 $Ø$ 表示）。
• 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
• 子串：串中任意个连续的字符组成的子序列。
• 主串：包含子串的串。
• 字符在主串中的位置：字符在串中的序号。
• 子串在主串中的位置：子串的第一个字符在主串中的位置。

二、串的存储结构

1. 串的顺序存储

• 静态数组实现（定长顺序存储）

  #define MAXLEN 255      // 预定义最大串长为255
  typedef struct {
      char ch[MAXLEN];    // 每个分量存储一个字符
      int length;         // 串的实际长度
  } SString;
  

• 动态数组实现（堆分配存储）

  typedef struct {
      char *ch;       // 按串长分配存储区，ch指向串的基地址
      int length;     // 串的长度
  }HString;
  

2. 串的链式存储

• 定义

  typedef struct StringNode {
      char ch[4];    // 每个结点存4个字符
      struct StringNode *next;
  } StringNode, * String;
  

三、串的基本操作

1. 举例

• 串的基本操作，如增删改查等通常以子串为操作对象。
• StrAssign(&T,chars)：赋值操作，把串 T 赋值为 chars。
• StrCopy(&T,S)：复制操作，有串 S 复制得到串 T。
• StrEmpty(S)：判空操作，空串返回 TRUE，否则返回 FALSE。
• StrLength(S)：求串长，返回串 S 的元素个数。
• ClearString(&S)：清空操作，将 S 清为空串。
• DestroyString(&S)：销毁串，将串 S 销毁（回收存储空间）。
• Concat(&T,S1,S2)：串联接，用 T 返回由 S1 和 S2 联接而成的新串。
• SubString(&Sub,S,pos,len)：求子串，用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
• Index(S,T)：定位操作，若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置，否则函数值为 0。
• StrCompare(S,T)：比较操作，若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。

2. 实现

#include <cstdio>
#define MAXLEN 10      // 预定义最大串长为10

// 0下标舍弃不用，从1开始，因此只能存放MAXLEN-1个字符
typedef struct {
    char ch[MAXLEN]; // 每个分量存储一个字符
    int length; // 串的实际长度
} SString;

// 初始化
bool InitSString(SString &s) {
    s.length = 0;
    return true;
}

// 赋值操作
bool StrAssign(SString &s, char *str) {
    int i, flag = 0;
    for (i = 0; *(str + i) != '\0'; i++) {
        if (i >= MAXLEN - 1) {
            flag = 1;
            break;
        }
        s.ch[i + 1] = str[i];
    }
    if (flag) {
        s.length = 0;
        return false;
    }
    s.length = i;
    return true;
}

// 复制操作
bool StrCopy(SString &T, SString S) {
    T.length = S.length;
    for (int i = 1; i <= T.length; i++) {
        T.ch[i] = S.ch[i];
    }
    return true;
}

// 判空
bool StrEmpty(SString S) {
    return S.length;
}

// 求串长
int StrLength(SString S) {
    return S.length;
}

// 清空操作
bool ClearString(SString &S) {
    S.length = 0;
    return true;
}

// 串联接
bool Concat(SString &S, SString s1, SString s2) {
    if (s1.length + s2.length > MAXLEN - 1)
        return false;
    S.length = s1.length + s2.length;
    int i;
    for (i = 1; i <= s1.length; i++) {
        S.ch[i] = s1.ch[i];
    }
    for (; i <= S.length; i++) {
        S.ch[i] = s2.ch[i - s1.length];
    }
    return true;
}

// 求子串
bool SubString(SString &Sub, SString S, int pos, int len) {
    if (pos + len - 1 > S.length)
        return false;
    for (int i = pos; i < pos + len; i++)
        Sub.ch[i - pos + 1] = S.ch[i];
    Sub.length = len;
    return true;
}

// 比较操作
int StrCompare(SString S, SString T) {
    for (int i = 1; i <= S.length && i <= T.length; i++) {
        if (S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    // 扫描过的所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

// 定位操作
int Index(SString S, SString T) {
    int i = 1, n = StrLength(S), m = StrLength(T);
    SString sub;        // 用于暂存子串
    while (i <= n - m + 1) {
        SubString(sub, S, i, m);
        if (StrCompare(S, sub) != 0) ++i;
        else return i;  // 返回子串在主串中的位置
    }
    return 0;           // S中不存在与T相等的子串
}

// 输出字符串
void ShowStr(SString s) {
    for (int i = 1; i <= s.length; i++) {
        printf("%c", s.ch[i]);
    }
    printf("\t 字符长度：%d\n", s.length);
}

四、模式匹配

• 字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

1. 朴素模式匹配算法

• 算法思想：

  • 设主串长度为 n，模式串长度为 m，主串指针 i，模式串指针 j
  • 将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。（最多对比 n-m+1 个子串）
  • 若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置

• 时间复杂度 —— 设主串长度为 n，模式串长度为 m，最坏时间复杂度：O(nm)

• 算法实现

  int index(SString S, SString T) {
      int i = 1, j = 1;
      while (i <= S.length && j <= T.length) {
          if (S.ch[i] == T.ch[j]) {
              ++i; ++j;       // 继续比较后继字符
          } else {
              i = i - j + 2;
              j = 1;          // 指针后退重新开始匹配
          }
      }
      if (j > T.length)
          return i - T.length;
      else
          return 0;
  }
  

2. KMP算法

• 步骤：
  1. 根据模式串 T，求出 next 数组（next 数组只和模式串有关，与主串无关）
  2. 利用 next 数组进行匹配（主串指针不回溯）
• 最坏时间复杂度：O(m+n)，其中
  • 求 next 数组时间复杂度 O(m)
  • 模式匹配过程最坏时间复杂度 O(n)

例如：对于模式串 T=‘abaabc’

• 当第6个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=3
• 当第5个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
• 当第4个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
• 当第3个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
• 当第2个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
• 当第1个元素匹配失败时，匹配下一个相邻子串，令 j=0, i++, j++

• 实现基本原理

  int Index_KMP(SString S, SString T, int next[]) {
      int i = 1, j = 1;
      while (i <= S.length && j <= T.length) {
          if (j == 0 || S.ch[i] == T.ch[j]) {
              ++i; ++j;           // 继续比较后继字符
          } else
              j = next[j];        // 模式串向右移动
      }
      if (j > T.length)
          return i - T.length;    // 匹配成功
      else
          return 0;
  }
  

• 求 next 数组
  1. next[1] 都无脑写 0
  2. next[2] 都无脑写 1
  3. 其他 next：在不配的位置前，划一根分界线，模式串一步一步往后退，直到分界线之前能对上，或模式串完全跨过分界线为止。此时 j 指向哪儿，next 数组值就是多少
• next 数组优化为 nextval 数组
  1. 先求 next 数组
  2. nextval[1] 固定为 0
  3. 若 next[j] 所对应的模式串字符等于模式串第 j 个字符（意思是即使移动了指针也会匹配失败） T.ch[next[j]] == T.ch[j]，则 nextval[j] = nextval[next[j]]
  4. 否则不变：nextval[j] = next[j]

第五章：树与二叉树

一、树的定义

1. 基本概念

• 树是 n（n≥0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：
  1. 有且仅有一个特定的称为根的结点。
  2. 当 n > 1 时，其余结点可分为 m（m>0）个互不相交的有限集合 $T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根节点的子树。
• 非空树的特性：
  1. 有且只有一个根节点
  2. 没有后继的结点称为 “叶子结点”（或终端结点）
  3. 有后继的结点称为 “分支节点”（或非终端结点）
  4. 除了根节点外，任何一个结点都有且仅有一个前驱
  5. 每个结点可以有 0 个或多个后继

2. 基本术语

• 结点之间的关系描述：祖先结点和子孙结点、父结点（双亲结点）和子结点、兄弟结点和堂兄弟结点；
• 结点之间的路径：经过了哪些结点（只能从上往下）；
• 结点之间的路径长度：路径上经过多少条边；
• 结点的层次（深度）：从上往下数第几层（默认从 1 开始）；
• 结点的高度：从下往上数第几层；
• 树的高度（深度）：总共多少层；
• 结点的度：该结点有几个分支；
  • 非叶子结点的度 > 0
  • 叶子结点的度 = 0
• 树的度：各结点的度的最大值；
• 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换；
• 无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换；
• 森林：是 m（m≥0）颗互不相交的树的集合。

3. 常见性质

• 结点数 = 总度数 + 1

• 度为 m 的树和 m 叉树

  度为 m 的树	m 叉树
  数的度 —— 各结点的度的最大值	每个结点最多只能有 m 个孩子的树
  任意结点的度 ≤ m（最多 m 个孩子）	任意结点的度 ≤ m（最多 m 个孩子）
  至少有一个结点度 = m（有 m 个孩子）	允许所有结点的度都 ≤ m
  一定是非空树，至少有 m+1 个结点	可以是空树

• 度为 m 的树和 m 叉树第 i 层至多有 $m^{i-1}$ 个结点（i≥1）

• 高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点

• 高度为 h 的 m 叉树至少有 h 个结点，高度为 h，度为 m 的树至少有 $h+m-1$ 个结点

• 具有 n 个结点的 m 叉树的最小高度为 $\lceil lo{g}_m(n(m-1)+1)\rceil$

二、二叉树的定义

1. 基本概念

• 二叉树是 n（n ≥ 0）个结点的有限集合：
  1. 或者为空二叉树，即 n = 0
  2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
• 特点：
  1. 每个结点至多只有两颗子树
  2. 左右子树不能颠倒（二叉树是有序树）
• 二叉树的五种状态：
  1. 空二叉树
  2. 只有左子树
  3. 只有右子树
  4. 只有根节点
  5. 左右子树都有

2. 特殊二叉树

• 满二叉树：除了叶子结点以外的每个结点都有两个分支。
  
  一颗高度为 h，且含有 $2^h-1$ 个结点的二叉树特点：
  1. 只有最后一层有叶子结点
  2. 不存在度为 1 的结点
  3. 按层序从 1 开始编号，结点 i 的左结点为 $2i$，右结点为 $2i+1$；结点 i 的父结点为 $\lfloor i/2\rfloor$（如果有的话）
• 完全二叉树：当且仅当其每个结点都与高度为 h 的满二叉树中编号 1~n 的结点一一对应时，称为完全二叉树。
  
  特点：
  1. 只有最后两层可能有叶子结点
  2. 最多只有一个度为 1 的结点
  3. 按层序从 1 开始编号，结点 i 的左结点为 $2i$，右结点为 $2i+1$；结点 i 的父结点为 $\lfloor i/2\rfloor$（如果有的话）
  4. $i\le \lfloor n/2\rfloor$ 为分支结点，$i>\lfloor n/2\rfloor$ 为叶子结点（$i$ 为当前结点编号，$n$ 为总共有多少结点）
• 二叉排序树：用于元素的排序和搜索。
  
  特点：
  1. 左子树上所有结点的关键字均小于根节点的关键字
  2. 右子树上所有结点的关键字均大于根节点的关键字
  3. 左子树和右子树又各是一颗二叉排序树
• 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过 1。
  

3. 常见性质

• 二叉树：
  1. 设非空二叉树中度为 0、1、2 的结点个数分别为 $n_0、n_1、n_2$，则 $n_0=n_2+1$（叶子结点比二分支结点多一个）
  2. 二叉树第 i 层最多有 $2^{i-1}$ 个结点（i≥1）
  3. 高度为 h 的二叉树最多有 $2^h-1$ 个结点（满二叉树）
• 完全二叉树：
  1. 第 i 个结点所在层次 和 具有 n 个（n>0）结点的完全二叉树的高度 h 都为 $\lceil lo{g}_2(n+1)\rceil$ 或 $\lfloor lo{g}_{2}n\rfloor +1$
  2. 可以由结点数 n 推出度为 0、1、2 的结点个数 $n_0、n_1、n_2$：
     若完全二叉树有 2k（偶数）个结点，则必有 $n_1=1，n_0=k，n_2=k-1$；
     若完全二叉树有 2k-1（奇数）个结点，则必有 $n_1=0，n_0=k，n_2=k-1$。

三、二叉树的存储结构

1. 顺序存储

• 二叉树的顺序存储结构，只适合存储完全二叉树，且一定要把二叉树的节点编号和完全二叉树对应起来。

  #define MaxSize 100
  
  // 让第一个为止空缺，保证数组下标和结点编号一直，因此能存储 MaxSize-1 个结点
  struct TreeNode {
      int value;      // 节点中的数据元素
      bool isEmpty;   // 结点是否为空
  };
  
  // 定义一个数组存储二叉树中的结点
  TreeNode t[MaxSize];
  
  // 初始化时所有结点标记为空
  void InitTree(TreeNode * t) {
      for (int i = 0; i < MaxSize; i++) {
          t[i].isEmpty = true;
      }
  }
  

• 基本操作：
  1. i 结点的左结点 —— $2i$
  2. i 结点的右节点 —— $2i+1$
  3. i 结点的父结点 —— $\lfloor i/2\rfloor$
  4. i 结点所在的层次 —— $\lceil lo{g}_2(i+1)\rceil$ 或 $\lfloor lo{g}_{2}i\rfloor +1$

• 若完全二叉树中共有 n 个结点，则：
  • 判断 i 结点是否有左孩子 —— $2i\le n$
  • 判断 i 结点是否有右孩子 —— $2i+1\le n$
  • 判断 i 结点是否有叶子 / 分支结点 —— $i>\lfloor n/2\rfloor$

2. 链式存储

• 实现

  typedef struct BiTNode {
      int data;       // 数据域
      struct BiTNode *lchild, *rchild;    // 左右孩子指针
  } BiTNode, *BiTree;
  
  // 插入根结点
  bool InsertRootNode(BiTree *T) {
      BiTree root = (BiTree)malloc(sizeof(BiTree));
      if (T == NULL) return false;
      root->data = 1;
      root->lchild = root->rchild = NULL;
      return true;
  }
  
  // 插入左结点
  bool InsertLeftBiTNode(BiTNode *T, int data) {
      BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
      if (p == NULL) return false;
      p->data = data;
      p->lchild = p->rchild = NULL;
      T->lchild = p;
      return true;
  }
  

• 性质：n 个结点的二叉链表共有 n+1 个空链域
• 如果需要频繁搜索父结点可使用三叉链表

四、二叉树的遍历

• 二叉树的递归特性：
  1. 要么是个空树
  2. 要么就是由 “根结点 + 左子树 + 右子树” 组成的二叉树

1. 先序遍历

• 也叫先根遍历（PreOrder），遍历顺序为：根左右（NLR）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 访问根结点
     2. 先序遍历左子树
     3. 先序遍历右子树

• 实现：第一次路过时访问

  void PreOrder(BiTree T){
  	if (T != NULL){
  		visit(T);				// 访问根结点
  		PreOrder(T->lchild);	// 递归遍历左子树
  		PreOrder(T->rchild);	// 递归遍历右子树
  	}
  }
  

2. 中序遍历

• 也叫中根遍历（InOrder），遍历顺序为：左根右（LNR）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 中序遍历左子树
     2. 访问根结点
     3. 中序遍历右子树

• 实现：第二次路过时访问

  void InOrder(BiTree T){
  	if (T != NULL){
  		InOrder(T->lchild);	// 递归遍历左子树
  		visit(T);			// 访问根结点
  		InOrder(T->rchild);	// 递归遍历右子树
  	}
  }
  

3. 后序遍历

• 也叫后根遍历（PostOrder），遍历顺序为：左右根（LRN）

• 操作过程：
  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 后序遍历左子树
     2. 后序遍历右子树
     3. 访问根结点

• 实现：第三次路过时访问

  void PostOrder(BiTree T){
  	if (T != NULL){
  		PostOrder(T->lchild);	// 递归遍历左子树
  		PostOrder(T->rchild);	// 递归遍历右子树
  		visit(T);				// 访问根结点
  	}
  }
  

• 求树的深度

  int TreeDepth(Bitree T){
  	if (T == NULL) return 0;
  	else {
  		int l = TreeDepth(T->lchild);
  		int r = TreeDepth(T->rchild);
  		// 树的深度=Max(左子树深度, 右子树深度)+1
  		return l > r ? l + 1 : r + 1;
  	}
  }
  

4. 层序遍历

• 层序遍历（LevelOrder）算法思想：
  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左、右结点插入队尾（如果有的话）
  4. 重复第三步，直到队列为空
• 实现

  typedef struct BiTNode{
  	int data;
  	struct BitNode *lchild, *rchild;
  } BiTNode, *BiTree;
  
  typedef struct LinkNode{
  	BiTNode * data;
  	LinkNode *front, *rear;
  } LinkNode, *LinkQueue;
  
  void LevelOrder(BiTree T){
  	LinkQueue Q;
  	InitQueue(Q);			// 初始化辅助队列
  	BiTree P;
  	EnQueue(Q, T);			// 根结点入队
  	while (!IsEmpty(Q)){	// 队列不空则循环
  		DeQueue(Q, p);		// 队头结点出队
  		visit(p);			// 访问出队结点
  		if (p->lchild != NULL)
  			EnQueue(Q, p->lchild);	// 左结点入队
  		if (p->rchild != NULL)
  			EnQueue(Q, p->rchild);	// 右结点入队
  	}
  }
  

5. 由遍历序列构造二叉树

• 若只给出一颗二叉树的前、中、后、层序序列的一种，不能唯一确定一棵二叉树。
• 前序、后序、层序序列的两两组合，不能唯一确定一颗二叉树。
• 若给出中序序列和其他任意一种序列，可以唯一确定一颗二叉树：
  1. 前序 + 中序
  2. 后序 + 中序
  3. 层序 + 中序
• 首先找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点。

五、线索二叉树

1. 基本概念

• n 个结点的二叉树，有 n+1 个空链域，这些空链域可用来记录前驱、后继的信息

• 指向前驱、后继的指针称为 “线索”，分别为：前驱线索、后继线索

• 作用：方便从一个指定结点出发，找到其前驱、后继；方便遍历

• 实现：
  tag 为 0 时，表示指针指向子结点；
  tag 为 1 时，表示指针是 “线索”。

  typedef struct ThreadNode {
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  }
  

2. 三种线索二叉树

• 中序线索二叉树：以中序遍历序列为依据进行线索化，线索指向中序前驱、中序后继
  
• 先序线索二叉树：以先序遍历序列为依据进行线索化，线索指向先序前驱、先序后继
  
• 后序线索二叉树：以后序遍历序列为依据进行线索化，线索指向后序前驱、后序后继
  

3. 二叉树的线索化

• 算法核心：是对遍历算法的改造，用一个指针 pre 记录当前访问节点的前驱结点，当访问一个结点时，连接该结点与前驱节点的线索信息。
• 注意最后一个结点的 rchild、rtag 的处理
• 中序线索化

  // 定义线索二叉树结点
  typedef struct ThreadNode{
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  } ThreadNode, *ThreadTree;
  
  // 定义全局变量 pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  
  // 中序线索化二叉树 T
  void CreateInThread(ThreadTree T){
  	pre = NULL;				// pre 初始为 NULL
  	if (T != NULL){			// 非空二叉树才能线索化
  		InThread(T);		// 中序线索化二叉树
  		if (pre->rchild == NULL)
  			pre->rtag = 1;	// 处理遍历的最后一个结点
  	}
  }
  
  // 改造中序遍历算法，一边遍历一边线索化
  void InThread(ThreadTree T){
  	if (T != NULL){
  		InThread(T->lchild);	// 中序遍历左子树
  		Visit(T);				// 访问根结点
  		InThread(T->rchild);	// 中序遍历右子树
  	}
  }
  
  void Visit(ThreadNode *q){
  	// 左子树为空，建立前驱线索
  	if (q->lchild == NULL){
  		q->lchild = pre;
  		q->ltag = 1;
  	}
  	// 建立前驱节点的后继线索
  	if (pre != NULL && pre->rchild == NULL){
  		pre->rchild = q;
  		pre->rtag = 1;
  	}
  	pre = q;
  }
  

• 先序线索化：注意处理死循环问题，当 ltag == 0 时，才能对左子树先序线索化。

  // 定义线索二叉树结点
  typedef struct ThreadNode{
  	int data;
  	ThreadNode *lchild, *rchild;
  	int ltag, rtag;		// 左、右线索标志
  } ThreadNode, *ThreadTree;
  
  // 定义全局变量 pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  
  // 先序线索化二叉树 T
  void CreatePreThread(ThreadTree T){
  	pre = NULL;				// pre 初始为 NULL
  	if (T != NULL){			// 非空二叉树才能线索化
  		PreThread(T);		// 先序线索化二叉树
  		if (pre->rchild == NULL)
  			pre->rtag = 1;	// 处理遍历的最后一个结点
  	}
  }
  
  // 改造先序遍历算法，一边遍历一边线索化
  void PreThread(ThreadTree T){
  	if (T != NULL){
  		Visit(T);				// 先访问根结点
  		if (T->ltag == 0)		// lchild 不是前驱线索
  			PreThread(T->lchild);
  		PreThread(T->rchild);
  	}
  }
  
  void Visit(ThreadNode *q){
  	// 左子树为空，建立前驱线索
  	if (q->lchild == NULL){
  		q->lchild = pre;
  		q->ltag = 1;
  	}
  	// 建立前驱节点的后继线索
  	if (pre != NULL && pre->rchild == NULL){
  		pre->rchild = q;
  		pre->rtag = 1;
  	}
  	pre = q;
  }
  

• 后序线索化

  ...重复代码省略...
  
  // 改造后序遍历算法，一边遍历一边线索化
  void PostThread(ThreadTree T){
  	if (T != NULL){
  		PostThread(T->lchild);
  		PostThread(T->rchild);
  		Visit(T);
  	}
  }
  
  ...重复代码省略...
  

4. 中序线索二叉树找前驱 / 后继

• 中序找后继，两种情况：
  1. 若 p->rtag == 1，则 next = p->rchild
  2. 若 p->rtag == 0，则 next 为 p 的右子树中最左下结点（往右走一步，往左走到底）

  // 找到以 P 为根的子树中，第一个被中序遍历的结点
  ThreadNode *FirstNode(ThreadNode *p){
  	// 循环找到最左下结点（不一定是叶子结点）
  	while (p->ltag == 0)
  		p = p->lchild;
  	return p;
  }
  
  // 在中序线索二叉树中找到结点 p 的后继结点
  ThreadNode *NextNode(ThreadNode *p){
  	// 右子树中最左下结点
  	if (p->rtag == 0)
  		return FirstNode(p->rchild);
  	else
  		return p->rchild;	// rtag == 1 直接返回后继线索
  }
  
  // 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
  void InOrder(ThreadNode *T){
  	for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
  		Visit(p);
  }
  

• 中序找前驱，两种情况：
  1. 若 p->ltag == 1，则 pre = p->lchild
  2. 若 p->ltag == 0，则 pre 为 p 的左子树中最右下结点（往左走一步，往右走到底）

  // 找到以 P 为根的子树中，最后一个被中序遍历的结点
  ThreadNode *LastNode(ThreadNode *p){
  	// 循环找到最右下结点（不一定是叶子结点）
  	while (p->rtag == 0)
  		p = p->rchild;
  	return p;
  }
  
  // 在中序线索二叉树中找到结点 p 的前驱结点
  ThreadNode *PreNode(ThreadNode *p){
  	// 左子树中最右下结点
  	if (p->ltag == 0)
  		return LastNode(p->lchild);
  	else
  		return p->lchild;	// ltag == 1 直接返回前驱线索
  }
  
  // 对中序线索二叉树进行逆向中序遍历
  void RevInOrder(ThreadNode *T){
  	for (ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p))
  		Visit(p);
  }
  

5. 先序线索二叉树找前驱 / 后继

• 先序找后继，两种情况：
  1. 若 p->rtag == 1，则 next = p->rchild
  2. 若 p->rtag == 0，则又分为两种情况：
     1. 若 p 有左结点，则先序后继为左结点
     2. 若 p 没有左结点，则先序后继为右结点

  // 在先序线索二叉树中找到结点 p 的后继结点
  ThreadNode *NextNode(ThreadNode *p){
  	if (p->rtag == 0)
  		return p->ltag == 0 ? p->lchild : p->rchild;
  	else
  		return p->rchild;	// rtag == 1 直接返回后继线索
  }
  
  // 对先序线索二叉树进行先序遍历
  void PreOrder(ThreadNode *T){
  	for (ThreadNode *p = T; p != NULL; p = NextNode(p))
  		Visit(p);
  }
  

• 先序找前驱，需使用三叉链表，两种情况
  1. 若 p->ltag == 1，则 pre = p->lchild
  2. 若 p->ltag == 0，则又分为四种情况：
     1. 若能找到 p 的父结点，且 p 为父结点的左结点，则 p 的父结点为其前驱
     2. 若能找到 p 的父结点，且 p 为父结点的右节点（左结点为空），则 p 的父结点为其前驱
     3. 若能找到 p 的父结点，且 p 为父结点的右节点（左结点非空），则 p 的前驱为左兄弟子树中最后一个被先序遍历的结点（优先往右走）
     4. 若 p 为根结点，则 p 没有先序前驱

6. 后序线索二叉树找前驱 / 后继

• 后序找前驱（类似于先序找后继），两种情况：
  1. 若 p->ltag == 1，则 pre = lchild
  2. 若 p->ltag == 0，则又分为两种情况：
     1. 若 p 有右结点，则后序前驱为右结点
     2. 若 p 没有右结点，则后序前驱为左结点
• 后序找后继（类似于先序找前驱），需使用三叉链表，两种情况：
  1. 若 p->rtag == 1，则 next = rchild
  2. 若 p->rtag == 0，则又分为四种情况：
     1. 若能找到 p 的父结点，且 p 为父结点的右结点，则 p 的父结点为其后继
     2. 若能找到 p 的父结点，且 p 为父结点的左结点（右结点为空），则 p 的父结点为其后继
     3. 若能找到 p 的父结点，且 p 为父结点的左结点（右结点非空），则 p 的后继为右兄弟子树中第一个被后序遍历的结点（优先往左走）
     4. 若 p 为根结点，则 p 没有后序后继

六、树的存储结构

1. 顺序存储

• 顺序存储，也叫双亲表示法，每个结点中保存指向父结点的数组索引号。
• 根结点固定存储在 0，-1 表示没有父结点。

#define MAX_TREE_SIZE 100   // 树中最多结点数

typedef struct {            // 树的结点定义
    int data;               // 数据元素
    int parent;             // 父结点位置域
} PTNode;

typedef struct {                    // 树的类型定义
    PTNode nodes[MAX_TREE_SIZE];    // 双亲表示法
    int n;                          // 结点数
} PTree;

• 添加结点：无需按逻辑上的次序存储，直接插入进数组。
• 删除结点：
  1. 如果是叶子结点，删除结点后将数组中最后一个结点数据放到删除结点所在的位置。
  2. 如果是分支结点，删除结点子树中所有的结点。
• 优点：查指定结点的父结点很方便。
• 缺点：差指定结点的子结点只能从头遍历。

2. 顺序 + 链式存储

• 也叫孩子表示法，顺序存储各个结点，每个结点中保存孩子链表头指针。

#define MAX_TREE_SIZE 100

// 定义孩子结点链表
struct CTNode {
    int child;      // 孩子结点在数组中的位置
    CTNode *next;   // 下一个孩子
};

// 定义结点
typedef struct {
    int data;               // 数据元素
    CTNode *first_child;    // 第一个孩子
} CTBox;

// 顺序存储所有结点
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;       // 结点数 和 根的位置
} CTree;

3. 链式存储

• 也叫孩子兄弟表示法，用纯链式的方式存储一棵树。
• 用二叉链表存储树：左孩子右兄弟

// 链式存储，类似于二叉链表
typedef struct CSNode {
    int data;                               // 数据域
    CSNode *first_child, *next_sibling;     // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

• 优点：可以实现树和二叉树的转换，可以用二叉树操作来处理树。
  

七、树和森林的遍历

1. 树的遍历

• 先根遍历：若树非空，先访问根结点，再依次对每颗子树进行先根遍历。
  树的先根遍历序列与这棵树相应二叉树的先序序列相同。

  // 树的先根遍历
  void PreOrder(TreeNode *R){
  	if (R != NULL){
  		visit(R);			// 访问根结点
  		while(R还有下一个子树T)
  			PreOrder(T);	// 先根遍历下一颗子树	
  	}
  }
  

• 后根遍历：若树非空，先依次对每颗子树进行后根遍历，最后再访问根结点。
  树的后根遍历序列与这棵树相应二叉树的中序序列相同。

  // 树的后根遍历
  void PostOrder(TreeNode *R){
  	if (R != NULL){
  		while(R还有下一个子树T)
  			PostOrder(T);	// 后根遍历下一颗子树
  		visit(R);			// 访问根结点
  	}
  }
  

• 层序遍历（用队列实现）：

  1. 若树非空，则根结点入队
  2. 若队列非空，队头元素出队并访问，同时将该元素的子结点依次入队
  3. 重复 2 直到队列为空

2. 森林的遍历

• 先序遍历，效果等同于依次对各个树进行先根遍历：
  1. 若森林非空，则访问森林中第一棵树的根结点。
  2. 先序遍历第一棵树中根结点的子树森林。
  3. 先序遍历除去第一棵树之后剩余的树构成的森林。

• 中序遍历，效果等同于依次对各个树进行后根遍历：
  1. 若森林非空，则中序遍历森林中第一棵树的根结点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林。

3. 遍历方式对比

• 同一排的遍历方式可互相转换

  树	森林	二叉树
  先根遍历	先序遍历	先序遍历
  后根遍历	中序遍历	中序遍历

八、哈夫曼树

1. 哈夫曼树的定义

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等）

• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

• 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Weighted Path Length）$$WPL=\sum _{i=1}^n{w}_i{l}_i$$

• 哈夫曼树：也称最优二叉树，在含有 n 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树。

2. 哈夫曼树的构造

• 给定 n 个权值分别为 $w_1,w_2,...,w_n$ 的结点，构造哈夫曼树的算法描述如下：
  1. 将这 n 个结点分别作为 n 颗仅含一个结点的二叉树，构成森林 F；
  2. 构造一个新节点，从 F 中选取两颗根结点权值最小的树作为新节点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和；
  3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中；
  4. 重复步骤 ② 和 ③，直至 F 中只剩下一棵树为止。

• 构造哈夫曼树的特点：
  1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
  2. 哈夫曼树的结点总数为 $2n-1$
  3. 哈夫曼树中不存在度为 1 的结点
  4. 哈夫曼树并不唯一，但 WPL 必然相同且为最优

3. 哈夫曼编码

• 固定长度编码：每个字符用相等长度的二进制位表示（如 ASCII 码）
• 可变长度编码：允许对不同字符用不等长的二进制位表示（如 哈夫曼编码）
• 前缀编码：若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码（前缀编码解码无歧义）
• 哈夫曼编码：由哈夫曼树得到，字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据构造算法构造哈夫曼树，即可得到哈夫曼编码，可用于数据压缩（哈夫曼树不唯一，因此哈夫曼编码也不唯一）

九、并查集

1. 逻辑结构

• 并查集，逻辑上是将各个元素划分为若干个互不相交的子集。
• 因此，本质上是集合的逻辑结构。
  

2. 存储结构

• 适合采用树的顺序存储（双亲表示法）：每个结点中保存指向父结点的数组索引号。

  #define MAX_TREE_SIZE 100			// 树中最多结点数
  
  typedef struct {					// 树的结点定义
  	ELemType data;					// 数据元素
  	int parent;						// 父结点位置域
  } PTNode;
  
  typedef struct {					// 树的类型定义（顺序存储）
  	PTNode nodes[MAX_TREE_SIZE];	// 双亲表示法
  	int n;							// 结点数
  } PTree;
  

3. 基本操作

• 初始化：初始化并查集，将所有数组元素初始化为 -1

  void Initial(PTree &T){
  	for (int i = 0; i < T.n; i++)
  		T.nodes[i] = -1;
  }
  

• 查：确定一个指定元素 x 所属集合，最坏时间复杂度 O(n)

  // Find 查操作，找到下标为 x 的元素所属集合（返回 x 所属根结点）
  int Find(PTree &T, int x){
  	while (T.nodes[x] >= 0)		// 循环寻找根结点
  		x = T.nodes[x];
  	return x;					// 根的父节点位置域小于 0
  }
  

• 并：将两个不相交的集合合并为一个集合，时间复杂度 O(1)。将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(n^2)$

  // Union 并操作，将两个集合合并为一个
  void Union(PTree &T, int root_1, int root_2){
  	// 要求 root_1 和 root_2 是不同的集合
  	if (root_1 == root_2) return;
  	// 将根 root_2 连接到另一根 root_1 下面
  	T.nodes[root_2] = root_1;
  }
  

4. 优化 “并” 操作

• 优化思路：在每次 Union 操作构建树时，尽可能让树不长高
  1. 用根结点的绝对值表示树的结点总数（如 -6 表示有 6 个结点）
  2. Union 操作，让小树合并到大树

// Union 并操作，小树合并到大树
void Union(PTree &T, int root_1, int root_2){
	if (root_1 == root_2) return;
	if (T.nodes[root_2] > T.nodes[root_1]) {	// root_2 结点数更少
		T.nodes[root_1] += T.nodes[root_2];		// 累加结点总数
		T.nodes[root_2] = root_1;				// 小树合并到大树
	}else{
		T.nodes[root_2] += T.nodes[root_1];		// 累加结点总数
		T.nodes[root_1] = root_2;				// 小树合并到大树
	}
}

• 该方法构造的树高不超过 $\lfloor lo{g}_{2}n\rfloor +1$，Find 查操作最坏时间复杂度变为 $O(lo{g}_{2}n)$，将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(nlo{g}_{2}n)$

5. 优化 “查” 操作

• 核心思想：压缩路径，尽可能让树变矮。
• 压缩路径：Find 操作，先找到根结点，再将查找路径上所有结点都挂到根结点下。

// Find 查操作优化，先找到根结点，再进行 压缩路径
int Find(PTree &T, int x){
	int root = x;
	while (T.nodes[root] >= 0)
		root = T.nodes[root];	// 循环找到根
	while (x != root){			// 压缩路径
		int temp = T.nodes[x];	// temp 指向 x 的父结点
		T.nodes[x] = root;		// x 直接挂到根结点下
		x = temp;
	}
	return root;				// 返回根结点编号
}

• 设 $\alpha (n)$ 是一个增长很缓慢的函数，对于常见的 $n$ 值，通常 $\alpha (n)\le 4$。
• 优化查操作后，树的高度不超过 $\alpha (n)$，时间复杂度 $O(\alpha (n))$，将 n 个独立元素通过多次 Union 合并为一个集合的时间复杂度为 $O(n\alpha (n))$

第六章：图

一、图的定义

1. 基本概念

• 图的概念：
  • 图 G（Graph）由顶点集 V（Vertex）和边集 E（Edge）组成，记为 $G=(V,E)$；
  • 其中 $V(G)$ 表示图 G 中顶点的有限非空集；$E(G)$ 表示图 G 中顶点之间的关系（边）的集合。
  • 若 V = { v 1 , v 2 , v 3 , . . . , v n } V=\{v_1,v_2,v_3,...,v_n\} V={v1​,v2​,v3​,...,vn​}，则用 $|V|$ 表示图 G 中 顶点的个数，也称图 G 的阶；
  • 若 $E=\{(u,v)|u\in V,v\in V\}$，用 |E| 表示图 G 中边的条数；
  • 注意：线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集，但 E 可以是空集。

• 有向图：
  • 若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。
  • 弧是顶点的有序对，记为 $<v,w>$，其中 $v、w$ 是顶点，$v$ 称为弧尾，$w$ 称为弧头，$<v,w>$ 称为从顶点 $v$ 到顶点 $w$ 的弧，也称 $v$ 邻接到 $w$，或 $w$ 邻接自 $v$。
  • $<v,w>\ne <w,v>$

  • $G_1=(V_1,E_1)$
  • V 1 = { A , B , C , D , E } V_1=\{A,B,C,D,E\} V1​={A,B,C,D,E}
  • E 1 = { < A , B > , < A , C > , < A , D > , < A , E > , < B , A > , < B , C > , < B , E > , < C , D > } E_1=\{<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>\} E1​={<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

• 无向图：

  • 若 E 是无向边（简称边）的有限集合时，则图 G 为无向图；
  • 边是顶点的无序对，记为 $(v,w)$ 或 $(w,v)$，其中 $v、w$ 是顶点；
  • 可以说顶点 $w$ 和顶点 $v$ 互为邻接点
  • 边 $(v,w)$ 依附于顶点 $w$ 和 $v$，或者说边 $(v,w)$ 和顶点 $v、w$ 相关联。

  

  • $G_2=(V_2,E_2)$
  • V 2 = { A , B , C , D , E } V_2=\{A,B,C,D,E\} V2​={A,B,C,D,E}
  • $E_2=\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}$

• 简单图：是指不存在重复边，且不存在顶点到自身的边。又可分为简单无向图和简单有向图。
  

• 多重图：图 G 中某两个结点之间的边数多于一条，有允许顶点通过另一条边和自己关联，则 G 为多重图。又可分为多重无向图和多重有向图。
  

• 无向图的度：
  • 顶点 $v$ 的度是指依附于该顶点的边的条数，记为 $TD(v)$
  • 在具有 n 个顶点，e 条边的无向图中，无向图的全部顶点的度之和等于边数的 2 倍，即$$\sum _{i=1}^{n}TD(v_i)=2e$$

• 有向图的度：
  • 入度是以顶点 $v$ 为终点的有向边的数目，记为 $ID(v)$
  • 出度是以顶点 $v$ 为起点的有向边的数目，记为 $OD(v)$
  • 顶点 $v$ 的度等于其入度和出度之和，即 $TD(v)=ID(v)+OD(v)$
  • 在具有 n 个顶点，e 条边的有向图中，有向图的全部顶点的入度之等于出度之和等于弧数，即$$\sum _{i=1}^{n}ID(v_i)=\sum _{i=1}^{n}OD(v_i)=e$$

• 顶点-顶点的关系描述
  • 路径 —— 顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列（$v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q$）
  • 回路 —— 第一个顶点和最后一个顶点相同的路径称为回路或环
  • 简单路径 —— 在路径序列中，顶点不重复出现的路径称为简单路径
  • 简单回路 —— 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
  • 路径长度 —— 路径上边的数目
  • 点到点的距离 —— 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）

• 连通
  • 在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的，反之为非连通
  • 若无向图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图
  • 若图 G 是连通图，对于 n 个顶点，则最少有 $n-1$ 条边
  • 若图 G 是非连通图，对于 n 个顶点，则最多可能有 $C_{n-1}^2$ 条边
  • 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）称为连通分量
  • 生成树：连通图的生成树是包含图中所有顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
  • 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

• 强连通
  • 在有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的
  • 若图中任意一对顶点都是强连通的，则称此图为强连通图
  • 若图 G 是强连通图，对于 n 个顶点，则最少有 n 条边（形成回路）
  • 有向图中的极大强连通子图称为有向图的强连通分量

• 子图（图的局部）
  • 设有两个图 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$ 是 $V$ 的子集，且 $E^{\prime }$ 是 $E$ 的子集，则称 $G^{\prime }$ 是 $G$ 的子图
  • 若满足 $V(G^{\prime })=V(G)$ 的子图 $G^{\prime }$（顶点都有，边不一定有），则称其为 $G$ 的生成子图

• 权值
  • 边的权 —— 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
  • 带权图 / 网 —— 边上带有权值的图称为带权图，也称网。
  • 带权路径长度 —— 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

2. 特殊的图

• 无向完全图
  • 无向图中任意两个顶点之间都存在边
  • 若无向图的顶点数 $|V|=n$，则 $|E|\in [0,C_n^2]=[0,n(n-1)/2]$
• 有向完全图
  • 有向图中任意两个顶点之间都存在方向相反的两条弧
  • 若有向图的顶点数 $|V|=n$，则 $|E|\in [0,2C_n^2]=[0,n(n-1)]$
• 边数很少的图（没有绝对的界限，一般来说 $|E|<|V|log|V|$ 时）称为稀疏图，反之称为稠密图。
• 树
  • 不存在回路，且连通的无向图。
  • n 个顶点的树，必有 $n-1$ 条边。
  • n 个顶点的图，若 $|E|>n-1$，则一定有回路
• 有向树
  • 一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。
  • 有向树不是一个强连通图。

二、图的存储结构

1. 邻接矩阵

• 结点数为 $n$ 的图 $G=(V,E)$ 的邻接矩阵 $A$ 是 $n\times n$ 的。将 $G$ 的顶点编号为 $v_1,v_2,...,v_n$，则$$A[i][j]=\{\begin{array}{ll}1,& \text{若(vi,vj)或<vi,vj>是 E(G) 中的边}\\ 0,& \text{若(vi,vj)或<vi,vj>不是 E(G) 中的边}\end{array}$$

#define MaxVertexNum 100					// 顶点数目的最大值

typedef struct {
	char Vex[MaxVertexNum];					// 顶点表
	int Edge[MaxVertexNum][MaxVertexNum];	// 邻接矩阵，边表
	int vexnum, arcnum;						// 图的当前顶点数和边数 / 弧数
} MGraph;

• 对于无向图，第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数
• 对于有向图：
  • 第 i 个结点的出度 = 第 i 行的非零元素个数
  • 第 i 个结点的入度 = 第 i 列的非零元素个数
  • 第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数之和
• 对于带权图（网）使用邻接矩阵存储，在之前的基础上，将 1 改为权值，将 0 改为无穷（∞）

---

• 邻接矩阵法的性能分析：
  • 邻接矩阵法求顶点的度 / 入度 / 出度的时间复杂度为 $O(|V|)$
  • 邻接矩阵法的空间复杂度只和顶点数有关，与实际的边数无关，因此空间复杂度为 $O(|V^2|)$
  • 邻接矩阵法只适合用于存储稠密图
  • 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区 / 下三角区）

---

• 邻接矩阵法的性质：
  设图 G 的邻接矩阵 $A$（矩阵元素不带权值，为 0 / 1），则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。
  $$例如：\left|\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right|\times \left|\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right|=\left|\begin{array}{cccc}1& 0& 1& 1\\ 0& 3& 1& 1\\ 1& 1& 2& 1\\ 1& 1& 1& 2\end{array}\right|$$$$A^2[2][2]=3：表示由顶点B到顶点B长度为2的路径数目有3条$$

2. 邻接表

• 使用顺序 + 链式存储

#define MaxVertexNum 100	// 最大顶点数

typedef struct {			// 用邻接表存储的图
	AdjList vertices;		// 顺序表结构存储顶点
	int vexnum, arcnum;		// 当前顶点数和边数
} ALGraph;

typedef struct VNode {		// 顶点
	char data;				// 顶点信息
	ArcNode *frist;			// 第一条边 / 弧的指针
} VNode, AdjList[MaxVertexNum];

typedef struct ArcNode{		// 边 / 弧
	int adjvex;				// 边 / 弧指向哪个结点
	ArcNode *next;			// 指向下一个边 / 弧的指针
	// InfoType info;		// 可选：权值
} ArcNode;

• 空间复杂度：
  • 对于无向图，边结点的数量是 2|E|，整体空间复杂度为 $O(|V|+2|E|)$
  • 对于有向图，边结点的数量是 |E|，整体空间复杂度为 $O(|V|+|E|)$
• 求度：
  • 对于无向图，遍历结点的链表
  • 对于有向图，度=入度+出度，求出度遍历链表，求入度遍历顺序表+链表。

3. 十字链表

• 只能用于存储有向图

#define MaxVertexNum 100	// 最大顶点数

typedef struct VNode{		// 顶点结点
	char data;				// 数据域
	ArcNode *firstin;		// 指向该顶点作为弧头的第一个弧结点
	ArcNode *firstout;		// 指向该顶点作为弧尾的第一个弧结点
} VNode, AdjList[MaxVertexNum];

typedef struct ArcNode {	// 弧结点
	int tailvex;			// 弧尾顶点索引编号
	int headvex;			// 弧头顶点索引编号
	// InfoType info;		// 可选：权值
	ArcNode *hlink;			// 弧头相同的下一条弧结点
	ArcNode *tlink;			// 弧尾相同的下一条弧结点
} ArcNode;

• 空间复杂度：$O(|V|+|E|)$

4. 邻接多重表

• 只能用于存储无向图，类似于十字链表
  

• 空间复杂度：$O(|V|+|E|)$

5. 四种存储结构对比

	邻接矩阵⚠️	邻接表⚠️	十字链表	邻接多重表
空间复杂度	$O(|V{|}^2)$	无向图 $O(|V|+2|E|)$；有向图 $O(|V|+|E|)$	$O(|V|+|E|)$	$O(|V|+|E|)$
适合用于	存储稠密图	存储稀疏图	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一
计算度 / 出度 / 入度	必须遍历对应行或列	计算有向图的度、入度不方便，其余很方便	很方便	很方便
找相邻的边	必须遍历对应行或列	找有向图的入边必须遍历整个邻接表，其余很方便	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点不方便	很方便	很方便

三、图的基本操作

1. Adjacent(G,x,y)：判断图 G 是否存在边 <x,y> 或 (x,y)

	邻接矩阵	邻接表
无向图	判断 $A[x][y]$ 是否为 1，时间复杂度 O(1) ✅	遍历边结点，时间复杂度 O(1) ~ O(|V|)
有向图	时间复杂度 O(1) ✅	时间复杂度 O(1) ~ O(|V|)

2. Neighbors(G,x)：列出图 G 中与结点 x 邻接的边

	邻接矩阵	邻接表
无向图	遍历第 x 行或第 x 列是否为 1，时间复杂度 O(|V|)	遍历边结点，时间复杂度 O(1) ~ O(|V|)✅
有向图	遍历第 x 行和第 x 列是否为 1，时间复杂度 O(|V|)✅	出边时间复杂度 O(1) ~ O(|V|) 入边时间复杂度 O(|E|)

3. InsertVertex(G,x)：在图 G 中插入顶点 x

	邻接矩阵	邻接表
无向图	仅写入顶点信息，时间复杂度 O(1)	仅写入顶点信息，时间复杂度 O(1)
有向图	同上	同上

4. DeleteVertex(G,x)：在图 G 中删除顶点 x

	邻接矩阵	邻接表
无向图	删除顶点信息，矩阵相应行列归零，时间复杂度 O(|V|)	删除顶点信息和所有边，时间复杂度 O(1) ~ O(|E|)
有向图	时间复杂度 O(|V|)	出边时间复杂度 O(1) ~ O(|V|) 入边时间复杂度 O(|E|)

5. AddEdge(G,x,y)：若无向边（x,y）或有向边 <x,y> 不存在，则向图 G 中添加该边

	邻接矩阵	邻接表
无向图	时间复杂度 O(1)	头插法时间复杂度 O(1) 尾插法时间复杂度 O(|V|)
有向图	同上	同上

6. RemoveEdge(G,x,y)：若无向边（x,y）或有向边 <x,y> 存在，则从图 G 中删除该边

	邻接矩阵	邻接表
无向图	时间复杂度 O(1)	头插法时间复杂度 O(1) 尾插法时间复杂度 O(|V|)
有向图	同上	同上

7. FirstNeighbor(G,x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1

	邻接矩阵	邻接表
无向图	遍历第 x 行或第 x 列，时间复杂度 O(1) ~ O(|V|)	时间复杂度 O(1)
有向图	遍历第 x 行和第 x 列，时间复杂度 O(1) ~ O(|V|)	出边时间复杂度 O(1) 入边时间复杂度 O(1) ~ O(|E|)

8. NextNeighbor(G,x,y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1

	邻接矩阵	邻接表
无向图	时间复杂度 O(1) ~ O(|V|)	时间复杂度 O(1)
有向图	同上	同上

9. GetEdgeValue(G,x,y)：获取图 G 中边（x,y）或 <x,y> 对应的权值
10. SetEdgeValue(G,x,y,v)：设置图 G 中边（x,y）或 <x,y> 对应的权值为 v

四、图的遍历算法

1. 广度优先遍历

• 广度优先遍历（Breadth-First-Search，BFS）算法要点：
  1. 需要一个辅助队列
  2. 找到与第一个顶点相邻的所有顶点（FirstNeighbor(G,x)，NextNeighbor(G,x,y)）
  3. 标记哪些顶点被访问过（visited数组防止重复访问）
  4. 对于非连通图，需遍历完所有顶点
• 算法实现：

  bool visited[MAX_VERTEX_NUM];				// 访问标记数组
  
  void BFSTraverse(Graph G){					// 对图 G 进行广度优先遍历
  	for (int i = 0; i < G.vexnum; i++)
  		visited[i] = false;					// 初始化访问标记数组
  	InitQueue(Q);							// 初始化辅助队列 Q
  	for (int i = 0; i < G.vexnum; i++){		// 从第一个顶点开始遍历
  		if (!visited[i])					// 对每个连通分量调用一次 BFS
  			BFS(G, i);						// 若 i 没被访问过，从 i 开始 BFS
  	}
  }
  // 广度优先遍历
  void BFS(Graph G, int v){					// 从顶点 v 出发，广度优先遍历图 G
  	visit(v);								// 访问初始顶点 v
  	visited[v] = true;						// 对 v 做已访问标记
  	Enqueue(Q, v);							// 顶点 v 入队列 Q
  	while (!isEmpty(Q)){
  		Dequeue(Q, v);						// 顶点 v 出队列
  		// 寻找顶点 v 的所有邻接点
  		for (int w = FirstNeighbor(G, v); w > 0; w = NextNeighbor(G, v, w)){
  			if (!visited[w]){				// w 为 v 的尚未访问的邻接顶点
  				visit(w);					// 访问顶点 w
  				visited[w] = true;			// 对 w 做已访问标记
  				EnQueue(Q, w);				// 顶点 w 入队列
  			}
  		}
  	}
  }
  

• 复杂度分析：
  • 对于无向图调用 BFS 函数的次数 = 连通分量数，对于有向图调用 BFS 函数的次数要具体问题具体分析
  • 空间复杂度：最坏情况，辅助队列大小为 O(|V|)
  • 时间复杂度：
    • 邻接矩阵：访问 |V| 个顶点需要 O(|V|) 的时间，查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有 |V| 个顶点，因此时间复杂度为 $O(|V{|}^2)$
    • 邻接表：访问 |V| 个顶点需要 O(|V|) 的时间，查找各个顶点的邻接点共需要 O(|E|) 的时间，因此时间复杂度为 O(|V|+|E|)
• 广度优先生成树：
  • 由广度优先遍历过程确定
  • 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一，基于邻接矩阵的广度优先生成树也唯一
  • 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一，基于邻接表的广度优先生成树也不唯一
  • 对于非连通图的广度优先遍历，可得到广度优先生成森林

2. 深度优先遍历

• 深度优先遍历（Depth-First-Search，DFS）算法要点：
  1. 递归地深入探索未被访问过的邻接点（类似于树的先根遍历）
  2. 找到与第一个顶点相邻的所有顶点（FirstNeighbor(G,x)，NextNeighbor(G,x,y)）
  3. 标记哪些顶点被访问过（visited数组防止重复访问）
  4. 对于非连通图，需遍历完所有顶点
• 算法实现：

  bool visited[MAX_VERTEX_NUM];				// 访问标记数组
  
  void DFSTraverse(Graph G){					// 对图 G 进行深度优先遍历
  	for (int v = 0; v < G.vexnum; v++)
  		visited[v] = false;					// 初始化以访问标记数据
  	for (for v = 0; v < G.vexnum; v++)		// 从第一个顶点开始遍历
  		if(!visited[v])
  			DFS(G, v);
  }
  
  void DFS(Graph G, int v){					// 从顶点 v 出发，深度优先遍历图 G
  	visit(v);								// 访问顶点 v
  	visited[v] = true;						// 对 v 做已访问标记
  	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
  		if (!visited[w])					// w 是 v 的尚未访问的邻接点
  			DFS(G, w);	
  }
  

• 复杂度分析：
  • 对于无向图调用 DFS 函数的次数 = 连通分量数，对于有向图调用 DFS 函数的次数要具体问题具体分析
  • 空间复杂度：最坏情况，递归深度为 O(|V|)；最好情况 O(1)
  • 时间复杂度：
    • 邻接矩阵：访问 |V| 个顶点需要 O(|V|) 的时间，查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有 |V| 个顶点，因此时间复杂度为 $O(|V{|}^2)$
    • 邻接表：访问 |V| 个顶点需要 O(|V|) 的时间，查找各个顶点的邻接点共需要 O(|E|) 的时间，因此时间复杂度为 O(|V|+|E|)
• 深度优先生成树：
  • 由深度优先遍历过程确定
  • 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，基于邻接矩阵的深度优先生成树也唯一
  • 同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，基于邻接表的深度优先生成树也不唯一
  • 对于非连通图的深度优先遍历，可得到深度优先生成森林

五、图的应用

1. 最小生成树

• 概念：对于一个带权连通无向图 $G=(V,E)$，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的生成树，则 T 称为 G 的最小生成树（Minimum-Spanning-Tree，MST）
• 性质：
  1. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
  2. 只有连通图才有生成树，非连通图只有生成森林
  3. 最小生成树可能有多个，但边的权值之和总是唯一且最小的
  4. 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通，增加一条则会出现回路
• Prim 算法（普里姆）：
  • 算法思想：从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
  • 时间复杂度：$O(|V{|}^2)$
  • 适用于边稠密图
• Kruskal 算法（克鲁斯卡尔）：
  • 算法思想：每次选择一条权值最小的边，是这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。
  • 时间复杂度：$O(|E|lo{g}_2|E|)$
  • 适用于边稀疏图

2. 最短路径问题

• 算法对比

  	BFS 算法	Dijkstra 算法	Floyd 算法
  无权图	✔️	✔️	✔️
  带权图	❌	✔️	✔️
  带负权值的图	❌	❌	✔️
  带负权回路的图	❌	❌	❌
  时间复杂度	$O(|V{|}^2)$ 或 $O(|V|+|E|)$	$O(|V{|}^2)$	$O(|V{|}^3)$
  通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

  注：也可用 Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度也是 $O(|V{|}^3)$

• BFS 实现代码

  void BFS_MIN_Distance(Graph G, int u){		// 求顶点 u 到其他顶点的最短路径
  	for (int i = 0; i < G.vexnum; i++){		// 初始化
  		d[i] = ∞;							// 初始化 d[i]，表示从 u 到 i 结点的最短路径
  		path[i] = -1;						// 初始化 path[i]，前驱顶点的索引
  	}
  	d[u] = 0;								// 源节点为 0
  	visited[u] = true;						// 标记为已访问
  	EnQueue(Q, u);							// 源节点 u 进入辅助队列
  	while (!isEmpty(Q)){
  		DeQueue(Q, u);						// 队首出队，赋值给 u
  		for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)){
  			if (!visited[w]){				// w 如果没被访问
  				d[w] = d[u] + 1;			// 源节点到当前结点的距离 = 上一个结点距离 + 1
  				path[w] = u;				// 前驱顶点索引
  				visited[w] = true;			// 设已访问标记
  				EnQueue(Q, w);				// 当前顶点入辅助队列
  			}	
  		}
  	}
  }
  

• Dijkstra（迪杰斯特拉）算法：
  • 三个辅助数组：

    bool final[vexnum];		// 标记各顶点是否已找到最短路径
    int dist[vexnum];		// 最短路径长度，distance
    int path[vexnum];		// 路径上的前驱顶点索引
    

  • 初始化：若从 $V_0$ 开始，令

    final[0] = true; 		// 源顶点标记为已找到最短路径
    dist[0] = 0; 			// 源顶点路径长度为 0
    path[0] = -1			// 源顶点没有前驱顶点
    

    其余顶点

    final[k] = false; 		// 标记为还没访问
    dist[k] = arcs[0][k]; 	// 从 k 顶点到源顶点的路径长度
    path[k] = (arcs[0][k] == ∞) ? -1 : 0;	// 前驱顶点要么是源顶点，要么还没访问
    

  • $n-1$ 轮处理：循环遍历所有顶点，找到还没确定最短路径，且 dist 最小的顶点 $V_i$，令

    final[i] = true		// i 顶点标记为已找到最短路径
    

    并检查所有邻接自 $V_i$ 的顶点，对于邻接自 $V_i$ 的顶点 $V_j$，若

    // j 顶点还没找到最短路径，且 i 顶点的路径长度 + i 到 j 的路径长度 < j 目前的路径长度
    final[j] == false && dist[i] + arcs[i][j] < dist[j]	
    

    则令

    dist[j] = dist[i] + arcs[i][j];		// 小于了就替换掉
    path[j] = i;						// 前驱顶点设为 i 顶点
    

    （注：arcs[i][j] 表示 $V_i$ 到 $V_j$ 的弧的权值）

• Floyd 算法：
  • 若$$A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j]$$则$$A^{(k-1)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j];$$$$pat{h}^{(k)}[i][j]=k;$$否则 $A^{(k)}$ 和 $pat{h}^{(k)}$ 保持原值。
  • 算法实现

    // 预处理：根据图的信息初始化矩阵 A 和 path
    for (int k = 0; k < n; k++){					// 以 k 作为中转点
    	for (int i = 0; i < n; i++){				// 遍历整个矩阵，i 为行号，j 为列号
    		for (int j = 0; j < n; j++){
    			if (A[i][j] > A[i][k] + A[k][j]){	// 若 k 为中转点的路径更短
    				A[i][j] = A[i][k] + A[k][j];	// 更新最短路径长度
    				path[i][j] = k;					// 中转点
    			}	
    		}	
    	}
    }
    

3. 有向无环图描述表达式

• 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 DAG 图（Directed Acyclic Graph）
• 顶点中不可能出现重复的操作数
• 描述表达式步骤：
  1. 把各个操作数不重复地排成一排
  2. 标出各个运算符的生效顺序
  3. 按顺序加入运算符，注意 “分层”
  4. 自底向上逐层检查同层的运算符是否可以合并

4. 有向无环图拓扑排序

• AOV 网（Activity On Vertex NetWork，用顶点表示活动的网）：用 DAG 图表示一个工程。顶点表示活动，有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行。
• 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
  1. 每个顶点出现且只出现一次。
  2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

也可定义为：拓扑结构是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。

• 拓扑排序性质：
  1. 每个 AOV 网都有一个或多个拓扑排序序列。
  2. 若图中有环，则不存在拓扑排序序列 / 逆拓扑排序序列。
• 拓扑排序的实现：
  1. 从 AOV 网中选择一个没有前驱（入度为 0）的顶点并输出
  2. 从网中删除该顶点和所有以它为起点（前驱）的有向边
  3. 重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止（即当前所有顶点入度 > 0，说明图存在回路）

  bool TopologicalSort(Graph G){
  	InitStack(S);					// 初始化栈，存储入度为 0 的顶点
  	for (int i = 0; i < G.vexnum; i++){
  		if (indegree[i] == 0)
  			Push(S, i);				// 将所有入度为 0 的顶点进栈
  	}
  	int count = 0;					// 计数，记录当前已经输出的顶点数
  	while (!IsEmpty(S)){			// 栈非空，则存在入度为 0 的顶点
  		Pop(S, i);					// 栈顶元素出栈
  		print[count++] = i;			// 输出顶点 i
  		// 查找遍历所有 i 的后继
  		for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc){
  			v = p->adjvex;			// 指向当前顶点 v
  			if (!(--indegree[v]))	// 入度减 1，减后若入度为 0 则压入栈 S
  				Push(S, v);	
  		}
  	}
  	return count == G.vexnum;		// 若计数器等于图的顶点数，则排序成功，否则存在回路排序失败
  }
  

• 逆拓扑排序的实现：
  1. 从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出
  2. 从网中删除该顶点和所有以它为终点（后继）的有向边
  3. 重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无后继的顶点为止（即当前所有顶点出度 > 0，说明图存在回路）

  // 使用 DFS 算法实现逆拓扑排序
  bool DFSTraverse(Graph G){
  	for(int v = 0; v < G.vexnum; v++) {
  		visited[v] = false;				// 初始化已访问标记数据
  		recursion[v] = false;			// 初始化递归栈标记数据
  	}
  	for (int v = 0; v < G.vexnum; v++)	// 从第一个顶点开始遍历
  		if (!visited[v])
  			if (DFS(G, v)) 				// 如果发现回路，排序失败返回 true
  				return true;
  	return false;						// 排序成功，返回 false
  }
  
  bool DFS(Graph G, int v){				// 从顶点 v 出发，深度优先遍历图 G
  	visited[v] = true;					// 标记已访问
  	recursion[v] = true;				// 标记已入递归栈
  	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
  		if (!visited[w]) {
  			if (DFS(G, w))				// 如果发现回路，返回 true
  				return true;
  		} else if (recursion[w])		// 邻接点已在递归栈中，则说明有回路，返回 true
  			return true;
  	}
  	print(v);							// 输出顶点
  	recursion[v] = false;				// 标记为已出栈
  	return false;						// 没有发现回路，返回 false
  }
  

5. 关键路径

• AOE 网（Activity On Edge Network）：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网。
• AOE 网的性质：
  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
  2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
• 关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
  • 源点：在 AOV 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始。
  • 汇点：也仅有一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。
  • 完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

事件 $v_k$ 的最早发生时间 $ve(k)$ —— 决定了所有从 $v_k$ 开始的活动能够开工的最早时间
活动 $a_i$ 的最早开始时间 $e(i)$ —— 指该活动弧的起点所表示的事件的最早发生时间

事件 $v_k$ 的最迟发生时间 $vl(k)$ —— 指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
活动 $a_i$ 的最迟开始时间 $l(i)$ —— 指该活动弧的终点所表示事件的最迟发生时间与该活动所需事件之差

活动 $a_i$ 的 时间余量 $d(i)=l(i)-e(i)$，表示在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。
若一个活动的时间余量为 0，则说明该活动必须要如期完成，$d(i)=0$ 即 $l(i)=e(i)$ 的活动 $a_i$ 是关键活动。由关键活动组成的路径就是关键路径。

• 关键活动、关键路径的特性：
  • 若关键活动耗时增加，则整个工程的工期将增长
  • 缩短关键活动的时间，可以缩短整个工程的工期
  • 当缩短到一定程度时，关键活动可能会变成非关键活动
  • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
• 求关键路径步骤：
  1. 求所有事件的最早发生时间 $ve()$：按拓扑排序序列，依次求各个顶点的 $ve(k)$： v e ( 源点 ) = 0 v e ( k ) = M a x { v e ( j ) + W e i g h t ( v j , v k ) } ， v j 为 v k 的任意前驱 \begin{align} ve(源点)&=0 \\[2ex] ve(k)&=Max\{ve(j)+Weight(v_j,v_k)\}，v_j为v_k的任意前驱 \\[2ex] \end{align} ve(源点)ve(k)​=0=Max{ve(j)+Weight(vj​,vk​)}，vj​为vk​的任意前驱​​
  2. 求所有事件的最迟发生时间 $vl()$：按逆拓扑排序序列，依次求各个顶点的 $vl(k)$： v l ( 汇点 ) = v e ( 汇点 ) v l ( k ) = M i n { v l ( j ) − W e i g h t ( v k , v j ) } ， v j 为 v k 的任意后继 \begin{align} vl(汇点)&=ve(汇点) \tag{1}\\[2ex] vl(k)&=Min\{vl(j)-Weight(v_k,v_j)\}，v_j为v_k的任意后继 \tag{2} \\[2ex] \end{align} vl(汇点)vl(k)​=ve(汇点)=Min{vl(j)−Weight(vk​,vj​)}，vj​为vk​的任意后继​(1)(2)​
  3. 求所有活动的最早发生时间 $e()$：若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $e(i)=ve(k)$
  4. 求所有活动的最迟发生时间 $l()$：若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $l(i)=vl(j)-Weight(v_k,v_j)$
  5. 求所有活动的时间余量 $d()$：$d(i)=l(i)-e(i)$。$d(i)=0$ 的活动就是关键活动

第七章：查找

一、基本概念

1. 概念

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
• 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
  • 静态查找表：只查找符合条件的数据元素
  • 动态查找表：在查找元素的基础上还要插入、删除。除了查找速度，也要关注插 / 删操作是否方便实现。
• 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

2. 查找算法的效率评价

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度
• 平均查找长度（ASL，Average Search Length）：所有查找过程中进行关键字的比较次数的平均值。
  • 令数据元素个数为 $n$，查找第 i 个元素的概率为 $P_i$，查找第 i 个元素的查找长度为 $C_i$，则$$ASL=\sum _{i=1}^n{P}_i{C}_i$$
  • ASL 的数量级反应了查找算法时间复杂度
  • 评价一个查找算法的效率时，通常考虑查找成功 / 查找失败两种情况的 ASL

二、顺序查找

1. 算法思想

• 顺序查找，又叫线性查找，通常用于线性表。
• 算法思想：从头到尾依次查找。
• 时间复杂度：O(n)

2. 算法实现

• 一般方法：

  typedef struct {		// 查找表的数据结构（顺序表）
  	ElemType *elem;		// 动态数组基址
  	int TableLen;		// 表的长度
  } SSTable;
  
  // 顺序查找
  int Search_Seq(SSTable ST, ElemType key){
  	int i;
  	for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);
  	// 查找成功，则返回元素下标
  	// 查找失败，则返回 -1
  	return i == ST.TableLen ? -1 : i;
  }
  

• 哨兵方法：无需判断是否越界，效率更高。

  typedef struct {
  	ElemType *elem;
  	int TableLen;
  } SSTable;
  
  int Search_Seq(SSTable ST, ELemType key){
  	ST.elem[0] = key;	// 0 号位置存 “哨兵”
  	int i;
  	// 从后往前查找
  	for (i = ST.TableLen; ST.elem[i] != key; i--);
  	// 查找成功，则返回元素下标
  	// 查找失败，则返回 0
  	return i;
  }
  

• $AS{L}_{成功}=\frac{1+2+3+...+n}{n}=\frac{n+1}{2}$

• $AS{L}_{失败}=n+1$

3. 算法优化

• 对有序表：
  • 当前关键字大于（或小于）目标关键字时，查找失败
  • 优点：查找失败时 ASL 更少，$AS{L}_{失败}=\frac{n}{2}+\frac{n}{n+1}$
  • 查找判定树：
    成功结点的关键字对比次数 = 结点所在层数；
    失败结点的关键字对比次数 = 其父节点所在层数。
• 若关键字被查概率不同：
  • 可按被查概率降序排列
  • 优点：查找成功时 ASL 更少

三、折半查找

1. 算法思想

• 折半查找：又称二分查找，仅适用于有序的顺序表。

2. 算法实现

typedef struct {		// 查找表的数据结构（顺序表）
	ElemType *elem;		// 动态数组基址
	int TableLen;		// 表的长度
} SSTable;

// 折半查找
int Binary_Search(SSTable L, ElemType key){
	int low = 0, high = L.TableLen - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;		// 取中间位置
		if (L.elem[mid] == key)
			return mid;				// 查找成功则返回所在位置
		else if (L.elem[mid] > key)
			high = mid - 1;			// 从前半部分继续查找
		else
			low = mid + 1;			// 从后半部分继续查找
	}
	return -1;						// 查找失败，返回 -1
}

3. 查找判定树

• 构造判定树：
  • 如果当前 low 和 high 之间有奇数个元素，则 mid 分割后，左右两部分元素个数相等
  • 如果当前 low 和 high 之间有偶数个元素，则 mid 分割后，左半部分比右半部分少一个元素
  • 若 $mid=\lfloor (low+high)/2\rfloor$，则对于任何一个结点，必有：右子树节点数 - 左子树节点数 = 0 或 1
  • 若 $mid=\lceil (low+high)/2\rceil$，则对于任何一个结点，必有：左子树节点数 - 右子树节点数 = 0 或 1
• 折半查找的判定树性质：
  1. 右子树节点数 - 左子树节点数 = 0 或 1
  2. 折半查找的判定树只有最下面一层是不满的，且一定是平衡二叉树，因此元素个数为 n 时树高 $h=\lceil lo{g}_2(n+1)\rceil$
  3. 判定树结点关键字：左 < 中 < 右，满足二叉排序树的定义。失败结点数量为 n+1 个（等于成功结点的空链域数量）

4. 折半查找效率

• 若有 n 个元素，则树高 $h=\lceil lo{g}_2(n+1)\rceil$
• 时间复杂度为 $O(lo{g}_{2}n)$

四、分块查找

1. 算法思想

• 分块查找，又称 索引顺序查找，算法过程如下：
  1. “索引表” 中保存每个分块的最大关键字和分块的存储区间，在索引表中确定待查记录所属的分块（可顺序、可折半）
     • 若采用折半查找索引表，索引表中不包含目标关键字，当 low > high 时，要在 low 所指分块中查找
     • 若采用折半查找索引表，low 超出索引表范围，则查找失败
  2. 在块内顺序查找
• 特点：块内无序，块间有序

2. 数据结构

• 顺序存储：

  typedef struct {		// 索引表
  	ElemType maxValue;	// 分块最大关键字
  	int low, high;		// 区间左右索引号
  } Index;
  
  ElemType List[100];		// 顺序表存储实际元素
  

• 若查找表是 “动态查找表”，则可以采用链式存储。

3. 查找效率分析

假设，长度为 n 的查找表被均匀地分为 b 块，每块 s 个元素。设索引查找和块内查找的平均查找长度分别为 $L_I、L_S$，则分块查找的平均查找长度为：$$ASL=L_I+L_S$$

• 用顺序查找查索引表，则 $L_I=\frac{1+2+...+b}{b}=\frac{b+1}{2}$，$L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$，则 $ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$，当 $s=\sqrt{n}时$，$AS{L}_{最小}=\sqrt{n}+1$
• 用折半查找查索引表，则 $L_I=\lceil lo{g}_2(b+1)\rceil ，L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$，则 $ASL=\lceil lo{g}_2(b+1)\rceil +\frac{s+1}{2}$

五、二叉排序树

1. 定义

• 二叉排序树，又称二叉查找树（BST，Binary Search Tree），具有以下性质：
  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一颗二叉排序树
• 二叉排序树可用于元素的有序组织、搜索，对一个二叉排序树进行中序遍历，可以得到一个递增的有序序列。
• 二叉排序树结点

  typedef struct BSTNode {
  	int key;
  	BSTNode *lchild, *rchild;
  } BSTNode, *BSTree;
  

2. 查找操作

• 若树非空，目标值与根结点的值比较：

  1. 若相等，则查找成功，返回结点指针
  2. 若小于根结点，则在左子树上查找，否则在右子树上查找
  3. 查找失败返回 NULL

• 在二叉排序树中查找值为 key 的结点，最坏空间复杂度 O(1)

  BSTnode *BST_Search(BSTree T, int key){
  	while (T != NULL && key != T->key){		// 若树空或等于根节点值，则结束循环
  		if (key < T->key)					//小于，在左子树上查找
  			T = T->lchild;
  		else								// 大于，在右子树上查找
  			T = T->rchild;	
  	}
  	return T;
  }
  

• 递归实现，最坏空间复杂度 O(h)

  BSTNode *BST_Search(BSTree T, int key){
  	if (T == NULL)
  		return NuLL;						// 查找失败
  	if (key == T->key)
  		return T;							// 查找成功
  	else if (key < T->key)
  		return BST_Search(T->lchild, key);	// 在左子树上查找
  	else
  		return BST_Search(T->rchild, key);	// 在右子树上查找
  }
  

3. 插入操作

• 插入：
  1. 若原二叉排序树为空，则直接插入结点
  2. 若非空，当关键字 k 小于根结点值，则插入到左子树；当关键字 k 大于根结点值，则插入到右子树
• 递归实现，最坏时间复杂度 O(h)

  int BST_Insert(BSTree &T, int k){
  	if (T == NULL){						// 原树为空，插入新节点
  		T = (BSTree)malloc(sizeof(BSTNode));
  		T->key = k;
  		T->lchild = T->rchild = NULL;
  		return 1;						// 插入成功，返回 1
  	}
  	else if (k == T->key)
  		return 0;						// 存在相同关键字的结点，插入失败
  	else if (k < T->key)
  		return BST_Insert(T->lchild, k);// 插入到 T 的左子树
  	else
  		return BST_Insert(T->rchild, k);// 插入到 T 的右子树
  }
  

• 构造二叉排序树，实际上就是一直插入

  void Creat_BST(BSTree &T, int str[], int n){
  	T == NULL;			// 初始时 T 为空树
  	int i = 0;
  	while (i < n) {		// 依次将每个关键字插入到二叉排序树中
  		BST_Insert(T, str[i]);
  		i++;	
  	}
  }
  

• 不同的关键字序列可能得到相同的二叉排序树，也可能得到不同的二叉排序树。

4. 删除操作

删除操作，三种情况：

1. 若被删除结点 z 是叶子结点，则直接删除，不会破坏二叉排序树的性质
2. 若结点 z 只有一颗左子树或右子树，则让 z 的子树成为 z 父节点的子树，替代 z 的位置。
3. 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个后继（或直接前驱），这样就转换成了第一或第二种情况。
   • z 的后继：z 的右子树最左下结点（该节点一定没有左子树）
   • z 的前驱：z 的左子树最右下结点（该节点一定没有右子树）

5. 查找效率分析

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
• 最好情况：n 个结点的二叉树最小高度为 $\lfloor lo{g}_{2}n\rfloor +1$，平均查找长度 = $O(lo{g}_{2}n)$
• 最坏情况：每个结点只有一个分支，树高 h = 节点数 n。平均查找长度 = $O(n)$

六、平衡二叉树

1. 定义

• 平衡二叉树（Balanced Binary Tree），简称平衡树（AVL 树）：树上任一结点的左子树和右子树的高度之差不超过 1（只可能是 -1、0、1）。
  • 结点的平衡因子 = 左子树高 - 右子树高。
• 平衡二叉树结点

  typedef struct AVLNode{
  	int key;		// 数据域
  	int balance;	// 平衡因子
  	AVLNode *lchild, *rchild;
  } AVLNode, *AVLTree;
  

2. 插入操作

• 在二叉排序树中插入新节点后，查找路径上的所有节点都有可能受到影响。
• 最小不平衡子树：从插入点往回找到的第一个不平衡结点，以该节点为根的子树。
• 在插入操作后，只要将不平衡子树调整平衡，则其他祖先节点都会回复平衡。

3. 调整不平衡问题

• 四种情况：
  1. LL：在 A 的左节点的左子树中插入导致不平衡
  2. RR：在 A 的右节点的右子树中插入导致不平衡
  3. LR：在 A 的左节点的右子树中插入导致不平衡
  4. RL：在 A 的右节点的左子树中插入导致不平衡

---

1. LL 平衡旋转（右单旋转）：
   

   • 由于在结点 A 的左节点（L）的左子树（L）上插入新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。
   • 将 A 的左孩子 B 向右上旋转代替 A 称为根结点，将 A 结点向右下旋转称为 B 的右子树的根结点，B 的原右子树则作为 A 结点的左子树。

   f->lchild = p->rchild;
   p->rchild = f;
   gf->lchild/rchild = p;
   

---

2. RR 平衡旋转（左单旋转）：
   

   • 由于在结点 A 的右节点（R）的右子树（R）上插入新节点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。
   • 将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，B 的原左子树则作为 A 结点的右子树。

   f->rchild = p->lchild;
   p->lchild = f;
   gf->lchild/rchild = p;
   

---

3. LR 平衡旋转（先左后右双旋转）：
   

   • 由于在 A 的左节点（L）的右子树（R）上插入新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
   • 先将 A 结点的左节点 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。

---

4. RL 平衡旋转（先右后左双旋转）：
   
   • 由于在 A 的右节点（R）的左子树（L）上插入新节点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
   • 先将 A 结点的右节点 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。

4. 查找效率分析

• 假设以 $n_h$ 表示深度为 h 的平衡树中含有的最少节点数，则有$$n_0=0,n_1=1,n_2=2$$并且有 $$n_h=n_{h-1}+n_{h-2}+1$$可以证明含有 n 个结点的平衡二叉树的最大深度为 $O(lo{g}_{2}n)$，平衡二叉树的平均查找长度为 $O(lo{g}_{2}n)$

5. 删除操作

1. 删除结点（方法同 “二叉排序树”）
   • 若删除的结点是叶子结点，直接删除
   • 若删除的结点只有一个子树，用子树顶替删除位置
   • 若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除
2. 一路向北找到最小不平衡子树，找不到就完结撒花
3. 找最小不平衡子树下，“个头” 最高的儿子、孙子
4. 根据孙子的位置，调整平衡（LL、RR、LR、RL）
   • 孙子在 LL：儿子右单旋
   • 孙子在 RR：儿子左单旋
   • 孙子在 LR：孙子先左旋，再右旋
   • 孙子再 RL：孙子先右旋，再左旋
5. 如果不平衡向上传导，继续 ②
   • 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）

七、红黑树

1. 定义和性质

• 红黑树（RBT）是一种二叉排序树（左根右），和普通的二叉排序树相比：
  1. 每个结点或是红色，或是黑色
  2. 根结点是黑色的
  3. 叶节点（外部节点、NULL结点、失败节点）均是黑色的（根叶黑）
  4. 不存在两个相邻的红节点（即红节点的父节点和孩子结点均是黑色）（不红红）
  5. 对每个结点，从该节点到任一叶节点的简单路径上，所含黑节点的数目相同（黑路同）
     • 结点的黑高 bh：从某节点出发（不含该节点）到达任一空叶节点的路径上黑节点总数
     • 若根结点黑高为 h，则内部节点数（关键字）最少有 $2^h-1$ 个（满树状态）
• 红黑树的性质：
  1. 从根结点到叶节点的最长路径不大于最短路径的 2 倍
  2. 有 n 个内部结点的红黑树高度 $h\le 2lo{g}_2(n+1)$
• 红黑树的结点定义

  struct RBNode {
  	int key;		// 关键字的值
  	RBNode *parent;	// 父节点指针
  	RBNode *lchild;	// 左孩子指针
  	RBNode *rchild;	// 右孩子指针
  	int color;		// 结点颜色
  }
  

2. 插入操作

1. 先查找，确定插入位置（原理同二叉排序树），插入新节点
2. 新节点是根，染为 黑色
3. 新节点非根，染为 红色
   • 若插入新节点后依然满足红黑树定义，则插入结束
   • 若插入新节点后不满足红黑树定义（违反不红红），则需要看新节点叔叔的颜色：
     • 叔叔是黑色：旋转+染色
       1. LL：右单旋，父换爷 + 染色
       2. RR：左单旋，父换爷 + 染色
       3. LR：左、右双旋，儿换爷 + 染色
       4. RL：右、左双旋，儿换爷 + 染色
     • 叔叔是红色：染色+变新
       1. 叔父爷染色，爷变为新节点

3. 删除操作

• 红黑树的删除操作时间复杂度为 $O(lo{g}_{2}n)$
• 在红黑树中删除结点的操作方式和 “二叉排序树的删除” 一样
• 按 ② 删除节点后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树特性。

八、B 树

1. 定义和性质

• B 树（Balance Tree），又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。一颗 m 阶 B 树或为空树，或为满足如下特性的 m 叉树：
  1. 树中每个结点最多有 $m$ 颗子树，即最多含有 $m-1$ 个关键字
  2. 若根结点不是终端结点，则至少有两颗子树。
  3. 除根结点外的所有非叶节点至少有 $\lceil m/2\rceil$ 颗子树，即至少含有 $\lceil m/2\rceil -1$ 个关键字
  4. 所有非叶节点的结构如下：$$n,P_0,K_1,P_1,K_2,P_2,...,K_n,P_n$$其中，$K_i(i=1,2,...,n)$ 为结点的关键字，且满足 $K_1<K_2<...<K_n$；$P_i(i=1,2,...,n)$ 为指向子树根结点的指针，且指针$P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$，$P_i$ 所指子树中所有的关键字均大于 $K_i$，$n（\lceil m/2\rceil -1\le n\le m-1）$为结点中关键字的个数。
  5. 所有的叶节点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
• m 阶 B 树的核心特性：
  1. 根结点的子树数 $\in [2,m]$，关键字数 $\in [1,m-1]$
     其他结点的子树数 $\in [\lceil m/2\rceil ,m]$，关键字数 $\in [\lceil m/1\rceil -1,m-1]$
  2. 对任一结点，其所有子树高度都相同
  3. 关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < …（类比二叉查找树 左 < 中 < 右）
• 含 n 个关键字的 m 阶 B 树
  • 最小高度：让每个结点尽可能的满，有 m-1 个关键字，m 个分叉，则有$$n\le (m-1)(1+m+m^2+m^3+...+m^{h-1})=m^h-1$$因此 $$h\ge lo{g}_m(n+1)$$
  • 最大高度：让各层的分叉尽可能的少，即根结点只有 2 个分叉，其他结点只有 $\lceil m/2\rceil$ 个分叉，n 个关键字的 B 树必有 n+1 个叶子结点，则 $$n+1\ge 2(\lceil m/2\rceil {)}^{h-1}$$即$$h\le lo{g}_{\lceil m/2\rceil }\frac{n+1}{2}+1$$
• n 阶 B 树的结点定义

  #define n 5
  
  struct Node {
  	ElemType keys[n - 1];	// 最多 n-1 个关键字
  	Node * child[n];		// 最多 n 个孩子
  	int num;				// 结点中有几个关键字
  }
  

2. 插入操作

• 核心要求：
  1. 对 m 阶 B 树 —— 除根节点外，结点关键字个数为 $\lceil m/2\rceil -1\le n\le m-1$
  2. 子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < …
• 插入步骤：
  1. 新元素一定是插入到最底层 “终端结点”，用 “查找” 来确定插入位置
  2. 在插入 key 后，若导致原结点关键字树超过上限，则从中间位置（$\lceil m/2\rceil$）将其中的关键字分为两部分：
     • 左部分包含的关键字放在原结点中
     • 右部分包含的关键字放在新节点中
     • 中间位置（$\lceil m/2\rceil$）的结点插入原结点的父节点
  3. 若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直到这个过程传到根结点位置，进而导致 B 树高度增 1。

3. 删除操作

• 核心要求和插入操作一样
• 删除的情况：
  1. 如果是非终端结点关键字：
     • 用其直接前驱（后继）代替其位置，转化为对 “终端结点” 的删除
  2. 如果是终端结点关键字：
     • 删除后结点关键字数未低于下限（$\lceil m/2\rceil -1$），无需任何处理
     • 删除后如果低于下限：
       1. 右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
       2. 左兄弟够借，则用当前节点的前驱、前驱的前驱依次顶替空缺
       3. 左（右）兄弟都不够借，则需要与父节点内的关键字、左（右）兄弟进行合并。合并后导致父节点关键字数量 -1，可能需要继续合并。

九、B+树

1. 定义

• 一颗 m 阶的 B+ 树需满足下列条件：
  1. 每个分支结点最多有 m 颗子树（孩子结点）
  2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\lceil m/2\rceil$ 颗子树
  3. 结点的子树个数和关键字个数相等（与 B 树的区别）
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）
  5. 所有分支结点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针（类似于分块查找）

2. 查找

• 在 B+ 树中，无论查找成功与否，最终一定都要走到最下面一层结点

3. 与 B 树对比

	m 阶 B 树	m 阶 B+ 树
类比	二叉查找树的进化 → m 叉查找树	分块查找的进化 → 多级分块查找
关键字与分叉	n 个关键字对应 n+1 个分叉（子树）	n 个关键字对应 n 个分叉
结点包含的信息	所有结点中都包含记录的信息	只有最下层叶子结点才包含记录的信息（可使树变矮）
查找方式	不支持顺序查找。查找成功时，可能停在任何一层结点，查找速度 “不稳定”	支持顺序查找。查找成功或失败都会到达最下一层结点，查找速度 “稳定”
相同点	除根结点外，最少 ⌈m/2⌉ 个分叉（确保结点不要太 "空"） 任何一个结点的子树都要一样高（确保 "绝对平衡"）

十、散列表

1. 定义和基本概念

• 散列表（哈希表，Hash Table）：是一种数据结构，特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址
• 散列函数（哈希函数）：Addr=H(Key) 建立了 “关键字”→“存储地址” 的映射关系
• 冲突（碰撞）：在散列表中插入一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为冲突（碰撞）
• 同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”

2. 构造散列函数

• 核心目标：散列函数要尽可能地减少 “冲突”
• 应注意的问题：
  1. 定义域必须涵盖所有可能出现的关键字
  2. 值域不能超出散列表的地址范围
  3. 尽可能减少冲突，散列函数计算出来的地址应尽可能均匀分布在整个地址空间
  4. 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址
• 常用散列函数构造方法
  1. 除留余数法
  2. 直接定址法
  3. 数字分析法
  4. 平方取中法

---

• 除留余数法：
  • 散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p。对质数取余，可以分布更均匀，从而减少冲突。
  • 适用场景：较为通用，只要关键字是整数即可
  • $H(key)=key$ % $p$
• 直接定址法
  • 计算最简单，且不会产生冲突
  • 若关键字分布不连续，空位较多，则会造成存储空间的浪费
  • 适用场景：关键字分布基本连续
  • $H(key)=key$ 或 $H(key)=a\times key+b$（$a$ 和 $b$ 是常数）
• 数字分析法
  • 设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。
  • 适用场景：关键字集合已知，且关键字的某几个数码位分布均匀
• 平方取中法
  • 具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀
  • 适用场景：关键字的每位取值都不够均匀

3. 处理冲突的方法

• 拉链法：
  • 又称链接法、链地址法，把所有同义词存储在一个链表中
  • 插入操作：
    1. 结合散列函数计算新元素的散列地址
    2. 将新元素插入散列地址对应的链表（默认头插法）
  • 查找操作：
    1. 结合散列函数计算新元素的散列地址
    2. 顺序查找链表，查找长度为在查找运算中，需要对比关键字的次数
  • 删除操作：
    1. 结合散列函数计算新元素的散列地址
    2. 顺序查找链表，删除目标元素
• 开放定址法
  • 开放定址：一个散列地址，既对同义词开放，也对非同义词开放
  • 基本思想：如果发生冲突，就给新元素找另一个空闲位置
  • 思路：需确定一个探测的顺序，从初始散列地址出发，取寻找下一个空闲位置
  • $H_i$ 表示第 $i$ 次冲突时的散列地址；
    $H(key)$ 表示初始散列地址；
    $d_i$ 表示第 $i$ 次发生冲突时，下一个探测地址与初始散列地址的相对偏移量，$d_0=0$；
    $m$ 表示散列表表长$$H_i=(H(key)+d_i)\%m\text{\hspace{1em}(0≤i≤m−1)}$$
  • 四种常用方法构造探测序列 $d_i$：
    1. 线性探测法：$d_i=0,1,2,3,...,m-1$
    2. 平方探测法：$d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2$
    3. 双散列法：$d_i=i\times has{h}_2(key)$
    4. 伪随机序列法：$d_i$ 是一个伪随机序列，假设 $d_i=0,5,3,11,...$
  • 查找操作：
    • 根据探测序列依次对比各存储单元内的关键字。
    • 若探测到目标关键字，则查找成功
    • 若探测到空单元，则查找失败
  • 删除操作：
    • 先根据散列函数算出散列地址，并对比关键字是否匹配。若匹配，则查找成功
    • 若关键字不匹配，则根据探测序列对比下一个地址的关键字，直至查找成功或查找失败
    • 若查找成功，则删除找到的元素
    • 注意：删除元素不能简单地删元素的空间置为空，否则将截断在它之后的探测路径，可以做一个 “已删除” 标记，进行逻辑删除

第八章：排序

• 文章太长，塞不下了，最后一章直接上传送门吧 【数据结构】第八章：排序