绪论

数据结构的基本概念

算法和算法评价

线性表

线性表的定义和基本操作

线性表的顺序表示

线性表的链式表示

栈和队列

栈

• 只允许在一端进行插入或删除 操作的 线性表
• 卡特兰数：n个不同元素进栈，出栈元素不同排列的个数为**$\frac{1}{n+1}{C}_{2n}^n$**

基本操作

// 初始化一个空栈
InitStack(&S)
          
// 判断一个栈是否为空，若栈S为空则返回true，否则返回false
StackEmpty(S)
          
// 进栈，若栈S未满，则将x加入使之成为新栈顶
Push(&S, x)
          
// 出栈，若栈S非空，则弹出栈顶元素，并用x返回
Pop(&S, &x)
          
// 读栈顶元素，若栈S非空，则用x返回栈顶元素
GetTop(S, &x)
          
// 销毁栈，并释放栈S占用的存储空间
DestroyStack(&S)

解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数

栈的顺序存储结构

• 顺序栈

  一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

// 定义栈中元素的最大个数
#define MaxSize 50
typedef struct {
	// 存放栈中元素
	Elemtype data[MaxSize];
	// 栈顶指针
	int top;
} SqStack;

初始时，设置 S.top = -1，栈顶元素 S.data[S.top]

进栈：栈不满时，栈顶指针先加1，再送值到栈顶元素
出栈：栈非空时，先取栈顶元素值，再将栈顶指针减1
栈空条件：S.top == -1

栈满条件：S.top == MaxSize - 1
栈长：S.top+1

• 共享栈
  • 利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个 栈的栈底 分别设置在共享空间的两端，两个 栈顶 向共享空间的中间延伸。
  • top0=-1时，0号栈为空，top1=MaxSize时，1号栈为空。仅当两个栈顶指针相邻时（top1-top0==1），判断栈满。

栈的链式存储

• 通常采用 单链表 实现，并规定所有操作都是在 单链表 的 表头 进行。规定链栈没有头结点。

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

• 出栈序列判断
  • 在原序列中，相对位置比它小的，必须是逆序
  • 在原序列中，相对位置比它大的，顺序没有要求
  • 以上两点可以穿插进行

队列

操作受限的线性表。只允许在表的一端进行插入，在表的另一端进行删除。

队头：允许删除的一端，又称 队首

队尾：允许插入的一端

队列常见的基本操作

• InitQueue(&Q)：初始化队列，构造一个空队列
• QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false
• EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾
• DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回
• GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x

栈和队列是操作受限的线性表，因此不是任何线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

队列的顺序存储结构

• 队列的顺序存储
  队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（不同教材的定义不同）。

  #define MaxSize 50
  typedef struct {
        ElemType data[MaxSize];
        int front, rear;
  } SqQueue;
  

  初始状态（队空条件）：Q.front == Q.rear == 0

  进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

  出队操作：队不空时，先取队头元素值，再将队头指针加1。

  如果出队之后，不及时移动元素到队头位置，即固定队头位置，则可能出现假溢出，也就是队尾指针等于MaxSize，但实际上还有空余位置。如下

  

• 循环队列

  解决上面顺序存储队列的问题。将顺序队列 臆造 为一个环状的空间，即把存储队列元素的表，从 逻辑上 视为一个环。当队首指针 Q.front = MaxSize - 1后，再前进一个位置就自动到0，这可以利用除法取余运算实现。

  初始时：Q.front = Q.rear = 0

  队首指针进1: Q.front = （Q.front + 1）% MaxSize

  队尾指针进1: Q.rear = （Q.rear + 1）% MaxSize

  队列长度：（Q.rear + MaxSize - Q.front）% MaxSize

  出队入队时：指针都按顺时针方向进1，如下图

  

队列的链式存储结构

• 队列的链式存储

  链队列，实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）

  队列的链式存储类型可描述为

  // 链式队列结点
  typedef struct {
        ElemType data;
        struct LinkNode *next;
  } LinkNode;
      
  // 链式队列
  typedef struct {
        LinkNode *front, *rear;
  } LinkQueue;
  

  当Q.front == NULL 且 Q.rear == NULL 时，队列为空。

  不带头结点的链式队列，在操作上，往往比较麻烦。因此通常设计成，带头结点的单链表。这样 插入 和 删除 就统一了。

  用单链表表示的链式队列特别适合于数据元素变动比较大的情况，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和溢出问题。

双端队列

• 指两端都可以进行入队和出队操作的队列。如图，其元素的逻辑结构还是线性结构。

• 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列

• 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列

若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

• 解对应的题目时，根据输入受限，或者输出受限，对着给定选项，从里面开始，模拟左边进，右边进。左边出，右边出。

栈和队列的应用

栈在括号匹配中的应用

栈在表达式求值中的应用

• 表达式求值，中缀表达式->后缀表达式 重要

栈在递归中的应用

• 递归模型不能是循环定义的
  • 递归表达式（递归体）
  • 边界条件（递归出口）
• 递归算法转换为非递归算法，通常需要栈来实现

队列在层次遍历中的应用

队列在计算机系统中的应用

• 解决主机与外部设备之间速度不匹配的问题
• 解决由多用户引起的资源竞争问题

特殊矩阵的压缩存储

数组的定义

• 每个数据元素称为一个数据元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界
• 数组与线性表的关系
  • 数组是线性表的推广，一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表
  • 数组一旦被定义，其维数和维界就不再改变
    • 除结构的初始化和销毁外，数组只会有存取、修改元素的操作

数组的存储结构

矩阵的压缩存储

• 压缩存储，指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间

• 特殊矩阵，指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵

  • 常见的有对称矩阵、上下三角矩阵、对角矩阵等

• 特殊矩阵的压缩存储方法，找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中

  • 对称矩阵

    • 若对一个n阶方阵A[1…n][1…n]中的任意一个元素$a_{i,j}$都有$a_{i,j}=a_{j,i}$(1 <= i, j <= n)，则称其为对称矩阵。对于一个n阶方阵，其中的元素可以划分为3个部分，即上三角区、主对角线、下三角区

    • 将对称矩阵A[1…n][1…n]存放在一维数组B[n(n+1)/2]中，即元素$a_{i,j}$存放在$b_k$中，只存放下三角区（含对角线）的元素

      

    • 元素**$a_{i,j}$在数组B中的下标$k=1+2+\cdots +(i-1)+j-1=i(i-1)/2+j-1$，数组下标从0**开始，因此，元素下标之间的对应关系如下
      $$k=\{\begin{array}{l}\frac{i(i-1)}{2}+j-1,i\ge j(下三角区和主对角线元素)\\ \frac{j(j-1)}{2}+i-1,i<j(上三角区元素a_{ij}=a_{ji})\end{array}$$

  • 三角矩阵

    • 下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵**A[1…n][1…n]压缩存储在B[n(n+1)/2+1]**中

      

    • 元素下标之间的对应关系为
      $$k=\{\begin{array}{l}\frac{i(i-1)}{2}+j-1,i\ge j(下三角区和主对角线元素)\\ \frac{n(n+1)}{2},i<j(上三角区元素)\end{array}$$

  • 三对角矩阵

    • 对角矩阵也称带状矩阵。对于n阶方阵A 中的任意元素**$a_{i,j}$，当$|i-j|>1$，有$a_{i,j}=0(1\le i,j\le n)$，则称为三对角矩阵**。

    • 所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为零

    • 三对角矩阵A也可以采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且**$a_{1,1}$**存放于B[0]中

      

      

  • 稀疏矩阵

    • 矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s >> t的矩阵称为稀疏矩阵

    • 将非零元素、相应的行、列构成一个三元组（行标，列标，值），如下图，然后按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性

      

    • 稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储

串

串的定义和实现

串的定义

• 串是由零个或多个字符组成的有限序列

串的存储结构

• 定长顺序存储表示

  • 用一组地址连续的存储单元存储串值的字符序列

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

• 堆分配存储表示

  • 用一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的

    C语言中，存在一个堆的自由存储区，并用malloc()和free()函数来完成动态存储管理。利用malloc()为每个新产生的串分配一块实际串长所需的存储空间

    • 若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由指针来指示
    • 若分配失败，则返回NULL，已分配的空间可用free()释放掉

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

• 块链存储表示

  • 类似于线性表的链式存储结构，也可采用链表方式存储串值

串的基本操作

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

串的模式匹配

简单的模式匹配算法

• 子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法

  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;
  }
  

改进的模式匹配算法——KMP算法

• 在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并从该位置开始继续比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

• 字符串的前缀、后缀、部分匹配值

  • 前缀指除最后一个字符以外，字符串的所有头部子串

  • 后缀指除第一个字符外，字符串的所有尾部子串

  • 部分匹配值指字符串的前缀和后缀的最长相等前后缀长度

    • 'a’的前缀、后缀都是空集，最长相等前后缀长度为0
    • 'ab’的前缀为{a}，后缀为{b}，{a}$\cap${b}=$\varnothing$，最长相等前缀后长度为0
    • 'aba’的前缀为{a, ab}，后缀为{a, ba}，{a, ab}$\cap${a, ba}={a}，最长相等前后缀长度为1
    • 'abab’的前缀为{a, ab, aba} $\cap$ 后缀{b, ab, bab} = {ab}，最长相等前后缀长度为2
    • 。。。最长相等前后缀长度为3
    • 所以字符串’ababa’的部分匹配值为00123

  • 利用上述方法，将部分匹配值写成数组形式，就得到了部分匹配值（Partial Match，PM）的表

    编号	1	2	3	4	5
    S	a	b	c	a	c
    PM	0	0	0	1	0

  • 匹配过程中，发现第3位不匹配，前面2个字符是匹配的，查表可知，最后一个匹配字符b对应的部分匹配值为0，因此按照下面的公式算出子串需要向后移动的位数

    • 移动位数 = 已匹配的字符数 - 对应的部分匹配值

  • 因为2 - 0 = 2，所以将子串向后移动2位，再进行匹配

• KMP算法的原理是什么

  • 太难啦

树与二叉树

树的基本概念

树的定义

• 树是n（n>=0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足
  • 有且仅有一个特定的称为根的结点
  • 当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1，T2…Tm，其中每个集合本身又是一棵树，并且称为根的子树
• 树作为一种逻辑结构，同时也是一种分层结构，具有以下特点
  • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
  • 树中所有结点可以有零个、多个后继

基本术语

• 结点关系
  • 根A到结点K的唯一路径上的任意结点，称为结点K的祖先
    • 结点B是结点K的祖先
    • 结点K是结点B的子孙
  • 路径上最接近结点K的结点E称为K的双亲，K为结点E的孩子
  • 根A是树中唯一没有双亲的结点
  • 有相同双亲的结点称为兄弟，如K和L
• 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度
• 度大于0的结点称为分支结点（又称非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结构中，每个结点的分支数就是该结点的度
• 结点的深度、高度、层次
  • 层次
    • 从树根开始定义，根结点为第1层，它的子结点为第2层
    • 双亲在同一层的结点互为堂兄弟
  • 深度
    • 从根结点开始自顶向下逐层累加的
  • 高度
    • 从叶结点开始自底向上逐层累加的
• 有序树和无序树
  • 树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称无序树
• 路径和路径长度
  • 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数
  • 由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径
• 森林
  • 森林是m（m>=0）棵互不相交的树和集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

树的性质

• 树中的结点数等于所有结点的度数之和加1
• 度为m的树中，第i层上至多有$m^{i-1}$个结点（i>=1)
• 高度为h的m叉树至多有**$(m^h-1)/(m-1)$**个结点
• 具有n个结点的m叉树的最小高度为**$\lceil lo{g}_m(n(m-1)+1)\rceil$**

二叉树的概念

二叉树的定义及其主要特性

• 二叉树的定义

  • 二叉树是n（n >= 0）个结点的有限集合
    • 或者为空二叉树，即n=0
    • 或者有一个根结点和两个互不相交的被称为根的左子树和右子树组成
  • 二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中只有一棵子树，也要区分它是左子树还是右子树

• 二叉树与度为2的有序树的区别

  • 度为2的树至少有3个结点，而二叉树可以为空
  • 度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子树是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言的，而是确定的

• 几个特殊的二叉树

  • 满二叉树

    • 一棵高度为h，且含有**$2^h-1$个结点的二叉树称为满二叉树**，即树中的每层都含有最多的结点，如下图，满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2

  • 完全二叉树

    • 高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

      • 若i <= $\lfloor n/2\rfloor$ ，则结点i为分支结点，否则为叶子结点
      • 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上
      • 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）
      • 按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
      • 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有

      

    • 完全二叉树就是对应相同高度的满二叉树缺失最下层、最右边的一些连续叶子结点

  • 二叉排序树

    • 左子树上所有结点的关键字均小于根结点的关键字
    • 右子树上所有结点的关键字均大于根结点的关键字
    • 左子树和右子树又各是一棵二叉排序树

  • 平衡二叉树

    • 树上任一结点的左子树和右子树的深度之差不超过1

• 二叉树的性质

  1. 非空二叉树上的叶子结点数等于度为2的结点数加1

     扩展到任意一棵树，若结点数量为n，则边的数量为n - 1

  2. 非空二叉树上第k层上至多有**$2^k-1$**个结点（k >= 1)

  3. 高度为h的二叉树最多有**$2^h-1$**个结点（h >= 1）

  4. 对完全二叉树按从上到下、从左到右的顺序依次编号1，2，…，n，则有以下关系

     • 当i > 1时，结点i的双亲的编号为$\lfloor i/2\rfloor$，即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；当i为奇数时，其双亲的编号为（i-1）/2，它是双亲的右孩子
     • 当2i <= n时，结点i的左孩子编号为2i，否则无左孩子
     • 当2i + 1 <= n时，结点i的右孩子编号为2i+1，否则无右孩子
     • 结点i所在层次（深度）为$\lfloor lo{g}_{2}i\rfloor +1$

  5. 具有n个（n > 0）结点的完全二叉树的高度为$\lceil lo{g}_2(n+1)\rceil$或$\lfloor lo{g}_{2}n\rfloor +1$

二叉树的存储结构

• 顺序存储结构

  • 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中
  • 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置、以及结点之间的关系
    • 对于一般的二叉树，为了让数组下标能反映出二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近**$2^h-1$**个存储单元
    • 这种存储结构建议从数组下标1开始存储树中的结点，若从数组下标0开始储存，则不满足性质4的描述（当结点存储在0下标位置上时，无法计算出其孩子结点在数组中的位置）

• 链式存储结构

  • 由于顺式存储空间利用率较低，因此二叉树一般采用链式存储结构。在二叉树中，结点结构至少包含3个域：数据域data、左指针域lchild、右指针域rchild

    typedef struct BiTNode {
        ElemType data;
        struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    

  • 容易验证，在含有n个结点的二叉链表中，含有n+1个空链域

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

二叉树的遍历

• 先序遍历

  • 访问根结点

  • 先序遍历访问左子树

  • 先序遍历访问右子树

    void PreOrder(BiTree T) {
        if (T != NULL) {
            visit(T);
            PreOrder(T -> lchild);
            PreOrder(T -> rchild);
        }
    }
    

• 中序遍历

  • 中序遍历左子树

  • 访问根结点

  • 中序遍历右子树

    void InOrder(BiTree T) {
        if (T != NULL) {
            InOrder(T -> lchild);
            visit(T);
            InOrder(T -> rchild):
        }
    }
    

• 后序遍历

  • 后序遍历左子树

  • 后序遍历右子树

  • 访问根结点

    void PostOrder(BiTree T) {
        if (T != NULL) {
            PostOrder(T -> lchild);
            PostOrder(T -> rchild);
            visit(T);
        }
    }
    

• 三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次。故时间复杂度都是O(n)。

• 递归算法和非递归算法的转换

  • 分析中序遍历

    1. 沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点
    2. 栈顶元素出栈并访问：若其右孩子为空，继续执行步骤2；若其右孩子不空，将右子树转执行步骤1

  • 写出算法

    void InOrder2(BiTree T) {
    	// 初始化栈S
        InitStack(S);
        // p是遍历指针
        BiTree p = T;
        
        while (p || !IsEmpty(S)) {
            // 一路向左
            if (p) {
                // 当前结点入栈
                Push(S, p);
                // 左孩子不空，一直向左走
                p = p -> lchild;
            } else {
                // 出栈，并转向出栈结点的右子树
                Pop(S, p);
                // 栈顶元素出栈，访问出栈结点
                visit(p);
                // 向右子树走，p赋值为当前结点的右孩子
                p = p -> rchild;
            }
        }
    }
    

• 先序遍历非递归版本

  void PreOrder2(BiTree T) {
      initStack(S);
      BiTree p = T;
      
      while (p || !IsEmpty(S)) {
          if (p) {
              visit(p);
              Push(s, p);
              p = p -> lchild;
          } else {
  		   Pop(S, p);
              p = p -> rchild;
          }
      }
  }
  

• 后序遍历非递归版本是三种遍历方法中最难的。因为在后序遍历中，需要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点。思路分析如下

  • 从根结点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为如果有右子树，还需按相同的规则对其右子树进行处理
  • 直到上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早已访问完），这就保证了正确的访问顺序

• 层次遍历

  • 要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结点，如此往复

    void LevelOrder(BiTree T) {
        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):
            }
        }
    }
    

  遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作

  • 已知树，求结点的双亲、结点的孩子结点、二叉树的深度、二叉树的叶子结点个数、判断两棵二叉树是否相等

• 由遍历序列构造二叉树

  • 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树
    • 由后续和中序也可以唯一确定一棵二叉树
  • 先序遍历中，第一个结点一定是二叉树的根结点
  • 中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列
  • 根据这两个子序列，在先序序列中找到对应的左子序列和右子序列

线索二叉树

• 基本概念

  • 以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继

  • 传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继

  • 前面提到，在含n个结点的二叉树中，有n+1个空指针。这时因为每个叶结点有2个空指针，每个度为1的结点有1个空指针，所以空指针总数为n+1。由此设想能否利用这些空指针来存放指向其前驱、后继的指针，这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找前驱、后继的速度

  • 规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。还需增加两个标志域标识指针域是指向左右孩子或者前驱后继

    

    typedef struct ThreadNode {
        // 数据元素
        ElemType data;
        // 左右孩子指针
        struct ThreadNode *lchild, *rchild;
        // 左右线索标志
        int ltag, rtag;
    } ThreadNode, *ThreadTree;
    

• 中序线索二叉树的构造

  • 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树

    • 以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p

      

    • 通过中序遍历对二叉树线索化的递归算法如下

      void InThread(ThreadTree &p, ThreadTree &pre) {
          if (p != NULL) {
              // 递归，线索化左子树
              InThread(p -> lchild, pre);
              // 左子树为空，建立前驱线索
              if (p -> lchild == NULL) {
                  p -> lchild = pre;
                  p -> ltag = 1;
              }
              if (pre != NULL && pre -> rchild == NULL) {
                  // 建立前驱结点的后继线索
                  pre -> rchild = p;
                  pre -> rtag = 1;
              }
              // 标记当前结点成为刚刚访问过的结点
              pre = p;
              // 递归，线索化右子树
              InThread(p -> rchild, pre);
          }
      }
      

      通过中序遍历建立中序线索二叉树的主过程算法如下

      void CreateInThread(ThreadTree T) {
          ThreadTree pre = NULL;
          if (T != NULL) {
              // 非空二叉树，线索化
              InThread(T, pre);
              // 线索化二叉树
              pre -> rchild = NULL;
              // 处理遍历的最后一个结点
              pre -> rtag = 1;
          }
      }
      

• 中序线索二叉树的遍历

  • 中序线索二叉树的结点中隐含了线索二叉树的前驱、后继信息。在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。在中序线索二叉树中找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

树、森林

树的存储结构

• 双亲表示法

  • 采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。如下图，根结点下标为0，伪指针域为-1

    

  • 双亲表示法的存储结构描述如下

    // 树中最多结点数
    #define MAX_TREE_SIZE 100
    
    // 树的结点定义
    typedef struct {
        ElemType data;
        // 双亲位置域
        int parent;
    } PTNode;
    
    // 树的类型定义
    typedef struct {
        // 双亲表示
        PTNode nodes[MAX_TREE_SIZE];
        // 结点数
        int n;
    } PTree;
    

  • 该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时，需要遍历整个结构

    区别树的顺序储存结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储

• 孩子表示法

  • 将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空）
  • 这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表

• 孩子兄弟表示法 （二叉树表示法）

  • 以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）

    typedef struct CSNode {
        // 数据域
        ElemType data;
        // 第一个孩子和右兄弟指针
        struct CSNode *firstchild, *nextsibling;
    } CSNode, *CSTree;
    

  • 这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子，但缺点是从当前的结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便

    

树、森林与二叉树的转换

• 树转换为二叉树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称为左孩子右兄弟。由于根结点没有兄弟，所以对应的二叉树没有右子树

  

• 树转换为二叉树的画法

  • 在兄弟结点之间加一连线
  • 对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉
  • 以树根为轴心，顺时针旋转45度

• 将森林转换为二叉树的规则与树类似

  • 将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当做第一棵二叉树根的右子树，将第三棵树对应的二叉树当做第二课树根的右子树…以此类推
  • 森林转换二叉树画法
    • 将森林中的每棵树转换成相应的二叉树
    • 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线
    • 以第一棵树的根为轴心顺时针旋转45度

• 二叉树转换为森林的规则

  • 若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开
  • 二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止
  • 最后再将每棵二叉树依次转换成树，就得到了原森林

  

树和森林的遍历

• 树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式
  • 先根遍历
    • 若树非空，先访问其根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子书的规则。其遍历序列与这棵树相应二叉树的先序序列相同
  • 后根遍历
    • 若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同
• 森林的遍历
  • 先序遍历森林
    • 访问森林中第一棵树的根结点
    • 先序遍历第一棵树中根结点的子树森林
    • 先序遍历除去第一棵树之后剩余的树构成的森林
  • 中序遍历森林
    • 中序遍历森林中第一棵树的根结点的子树森林
    • 访问第一棵树的根结点
    • 中序遍历除去第一棵树之后剩余的树构成的森林

树与二叉树的应用

二叉排序树（BST)

• 二叉排序树的定义（二叉查找树）

  • 或者是一棵空树，或者是具有下列特性的二叉树
    • 若左子树非空，则左子树上所有结点的值均小于根结点的值
    • 若右子树非空，则右子树上所有结点的值均大于根结点的值
    • 左、右子树也分别是一棵二叉排序树
  • 根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列

• 二叉排序树的查找

  • 从根结点开始，沿某个分支逐层向下比较的过程

  • 非递归查找算法

    BSTNode *BST_Search(BiTree T, ElemType key ) {
        while ( T != NULL && key != T -> data ) {
            if ( key < T -> data ) 
                T = T -> lchild;
            else
                T = T -> rchild;
        }
        return T;
    }
    

• 二叉排序树的插入

  • 二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生产的，而是在查找过程中，当树中不存在关键字值等于给定值得结点时再进行插入的

  • 插入结点的过程如下

    • 若原二叉排序树为空，则直接插入结点
    • 否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树
    • 插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子

  • 插入操作的算法

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

• 二叉排序树的构造

  • 从一棵空树出发，依次输入元素，将它们插入二叉排序树中的合适位置

  • 构造二叉排序树的算法如下

    void Create_BST(BiTree &T, KeyType str[], int n) {
        T = NULL;
        int i = 0;
        while ( i < n ) {
            BST_Insert(T, str[i]);
            i++;
        }
    }   
    

• 二叉排序树的删除

  • 在二叉排序树删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理

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

    

• 二叉排序树的查找效率分析

  • 主要取决于树的高度
    • 若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度均为**$O(lo{g}_{2}n)$**。
    • 若二叉排序树是一个只有左（右）孩子的单支树（类似于有序的单链表），则其平均查找长度为O(n)

平衡二叉树

1. 平衡二叉树的定义

   • 为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），简称平衡树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是**-1、0、1**
   • 平衡二叉树可定义为一棵空树，或者是具有下列性质的二叉树
     • 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1

2. 平衡二叉树的插入

   • 保持平衡的基本思想如下

     • 每当在二叉排序树中插入或删除一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。
       • 若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡
       • 每次调整的对象都是最小不平衡树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树

   • 调整不平衡的规律如下

     • LL平衡旋转（右单旋转）

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

         

     • RR平衡旋转（左单旋转）

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

         

     • LR平衡旋转（先左后右双旋转）

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

         

     • RL平衡旋转（先右后左双旋转）

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

3. 平衡二叉树的查找

   1. 在平衡二叉树上进行查找的工作与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以**$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)$**，如下图

      

      该结论可用于求解给定结点数的平衡二叉树的查找所需的最多比较次数（或树的最大高度）

哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

   1. 在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为
      $$WPL=\sum _{i=1}^n{w}_i{l}_i$$

      1. 式子中，$w_i$是第i个叶结点所带的权值，$l_i$是该叶结点到根结点的路径长度

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

      

2. 哈夫曼树的构造

   1. 给定n个权值分别为$w_1,w_2,...,w_n$的结点，构造哈夫曼树的算法描述如下
      1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
      2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左右子树上根结点的权值之和
      3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
      4. 重复步骤2、3，直至F中只剩下一棵树为止
   2. 从上述构造过程中可看出哈夫曼树具有如下特点
      1. 每个初始结点最终都成了叶结点，且权值越小的结点到根结点的路径长度越大
      2. 构造过程中共新建了n-1个结点（双分支结点），因此哈夫曼树的结点总数为2n-1
      3. 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点

3. 哈夫曼编码

   1. 在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

      1. 可变长度编码比固定长度编码好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。
      2. 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码

   2. 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

   3. 由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为0表示转向左孩子，标记为1表示转向右孩子

      

      0和1究竟是表示左子树还是右子树没有明确规定。左右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必然相同且是最优的

图

图的基本概念

图的定义

1. 图G由顶点集V和边集E组成，记为G=（V，E），其中V（G）表示图G中顶点的有限非空集；E（G）表示图G中顶点之间的关系（边）集合。若V={$v_1,v_2,...,v_n$}，则用**|V|表示图G中顶点的个数**，E={$(u,v)|u \in V, v \in V $}，用**|E|表示图G中边的条数**

   线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边

2. 有向图

   1. 若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为**<v, w>**，其中v，w是顶点，v称为弧尾，w称为弧头，<v, w>称为从v到w的弧，也称v邻接到w

3. 无向图

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

4. 简单图、多重图

   1. 一个图G如果满足以下条件，那么称图G为简单图
      1. 不存在重复边
      2. 不存在顶点到自身的边
   2. 若图G中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则称图G为多重图。多重图和简单图的定义是相对的。数据结构中仅讨论简单图

5. 完全图（简单完全图）

   1. 对于无向图，|E|的取值范围为0到n(n-1)/2，有n(n-1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，|E|的取值范围为0到n(n-1)，有n(n-1)条弧的有向图称为有向完全图，在有向完全图中，任意两个顶点之间都存在方向相反的两条弧

6. 子图

   1. 设有两个图G=（V, E）和G1=（V1, E1），若V1是V的子集，且E1是E的子集，则称G1是G的子图。若有满足V（G1）=V（G）的子图G1，则称其为G的生成子图
   2. 并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中

7. 连通、连通图和连通分量

   1. 在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

   2. 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

   3. 无向图中的极大连通子图称为连通分量

   4. 假设一个图有n个顶点，如果边数小于n-1，那么此图必是非连通图

      

8. 强连通图、强连通分量

   1. 在有向图中，如果有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。
   2. 若图中任何一对顶点都是强连通的，则称此图为强连通图
   3. 有向图中的极大强连通子图称为有向图的强连通分量

9. 无向图中讨论连通性，有向图中讨论强连通性

10. 生成树、生成森林

    1. 连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边，则会形成一个回路

       

    2. 区分极大连通子图和极小连通子图

       1. 极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边
       2. 极小连通子图是既要保持图连通，又要使得边数保持最少的子图

11. 顶点的度、入度和出度

    1. 在无向图中，顶点v的度是指依附于顶点v的边的条数，记为TD(v)。无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联

    2. 在有向图中，顶点v的度分为入度、出度，入度是以顶点v为终点的有向边的数目，记为ID(v)。而出度是以顶点v为起点的有向边的数目，记为OD(v)。

       1. 顶点v的度，等于其入度 + 出度，即TD(v) = ID(v) + OD(v)

       2. 对于具有n个顶点、e条边的有向图，其全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点
          $$\sum _{\mathrm{i}=1}^{\mathrm{n}}\mathrm{ID}({\mathrm{v}}_{\mathrm{i}})=\sum _{\mathrm{i}=1}^{\mathrm{n}}\mathrm{OD}({\mathrm{v}}_{\mathrm{i}})=\mathrm{e}$$

12. 边的权和网

    1. 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
    2. 这种边上带有权值的图，称为带权图，也称网

13. 稠密图、稀疏图

    1. 边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。
    2. 一般当图G满足**|E| < |V|log|V|时，可以视G为稀疏图**

14. 路径、路径长度和回路

    1. 顶点$v_p$到顶点$v_q$之间的一条路径是指顶点序列$v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q$ ，当然关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环

15. 简单路径、简单回路

    1. 在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

16. 距离

    1. 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷

17. 有向树

    1. 一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树

图的存储及基本操作

邻接矩阵法

1. 所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵

2. 结点数为n的图G=（V，E）的邻接矩阵A是n*n的。将G的顶点编号为$v_1,v_2,...,v_n$。若$(v_i,v_j)\in E$，则A[i][j] = 1，否则A[i][j] = 0
   $$A[i][j]=\{\begin{array}{l}1，若(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0，若(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$$

3. 对于带权图而言，若顶点$v_i$和$v_j$之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点$V_i$和$V_j$不相连，则用$\infty$来代表两个顶点之间不存在边
   $$A[i][j]=\{\begin{array}{l}{w}_{ij}，若(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0或\infty ，若(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$$

4. 图的邻接矩阵存储结构定义如下

   // 顶点数目的最大值
   #define MaxVertexNum 100
   // 顶点的数据类型
   typedef char VertextType;
   // 带权图中边上权值的数据类型
   typedef int EdgeType;
   
   typedef struct {
       // 顶点表
   	VertexType Vex[MaxVertexNum];
       // 邻接矩阵，边表
       EdgeType Edge[MaxVertexNum][MaxVertexNum];
       // 图的当前顶点数和弧数
       int vexnum, arcnum;
   } MGraph;
   

   

   1. 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）
   2. 当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可采用值为0和1的枚举类型
   3. 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储
   4. 邻接矩阵表示法的空间复杂度为$O(n^2)$，其中n为图的顶点数**|V|**

5. 图的邻接矩阵存储表示法具有以下特点

   1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素
   2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非$\infty$元素） 的个数正好是顶点i的度$TD(v_i)$
   3. 对于有向图，邻接矩阵的第i行非零元素（或非$\infty$元素）的个数正好是顶点i的出度$OD(v_i)$，第i列非零元素（或非$\infty$元素）的个数正好是顶点i的入度$ID(v_i)$
   4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大
   5. 稠密图适合用邻接矩阵的存储表示
   6. 设图G的邻接矩阵为A，$A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径的数目$

邻接表法

1. 当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费

2. 所谓邻接表，是指对图G中的每个顶点$v_i$建立一个单链表，第i个单链表中的结点表示依附于顶点$v_i$的边（对于有向图则是以顶点$v_i$为尾的弧），这个单链表就称为顶点$v_i$的边表（对于有向图，则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点

   

3. 顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成

4. 无向图和有向图的邻接表的实例如下图

   

5. 图的邻接表存储结构定义如下

   // 图中顶点数目的最大值
   #define MaxVertexNum 100
   // 边表结点
   typedef struct ArcNode {
       // 该弧所指向的顶点的位置
       int adjvex;
       // 指向下一条弧的指针
       struct ArcNode *next;
   } ArcNode;
   
   // 顶点表结点
   typedef struct VNode {
       // 顶点信息
       VertexType data;
       // 指向第一条依附该顶点的弧的指针
       ArcNode *first;
   } VNode, AdjList[MaxVertexNum];
   
   // 邻接表
   typedef struct {
       // 邻接表
       AdjList vertices;
       // 图的顶点数和弧数
       int vexnum, arcnum;
   } ALGraph;
   

6. 图的邻接表存储方法具有以下特点

   1. 若G为无向图，则所需的存储空间为O(|V| + 2|E|)，若G为有向图，则所需的存储空间为O(|V| + |E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次
   2. 对于稀疏图，采用邻接表表示将极大地节省存储空间
   3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率极低
   4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度，则需要便利全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。
   5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序

十字链表

1. 有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下

   

   1. 弧结点中有5个域

      1. 尾域（tailvex）、头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置；
      2. **链域（hlink）**指向弧头相同的下一条弧。**链域（tlink）**指向弧尾相同的下一条弧；
      3. info域指向该弧的相关信息。
      4. 这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上

   2. 顶点结点中有3个域

      1. data域存放顶点相关的数据信息，如顶点名称
      2. firstin和firstout两个域分别指向以该结点为弧头或弧尾的第一个弧结点

   3. 下图为有向图的十字链表法。注意，顶点结点之间是顺序储存的

      

      1. 在十字链表中，既容易找到$V_i$为尾的弧，又容易找到$V_i$为头的弧，因而容易求得顶点的出度、入度。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图

邻接多重表

1. 邻接多重表是无向图的另一种链式存储结构

2. 在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边或对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低

3. 与十字链表法类似，在链接多重表中，每条边用一个结点表示，其结构如下

   

   1. mark为标志域，可用以标记该条边是否被搜索过
   2. ivex和jvex为该边依附的两个顶点在图中的位置
   3. ilink指向下一条依附于顶点ivex的边
   4. jlink指向下一条依附于顶点jvex的边
   5. info为指向和边相关的各种信息的指针域

4. 每个顶点也用一个结点表示，它由如下所示的两个域组成

   

   1. data域存储该顶点的相关信息
   2. firstedge域指示第一条依附于该顶点的边

5. 在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于

   1. 同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点

6. 下图为无向图的邻接多重表表示法。邻接多重表的各种基本操作的实现和邻接表类似

   

图的基本操作

1. 图的基本操作是独立于图的存储结构的，而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高
2. 图的基本操作主要包括
   1. Adjacent(G, x, y)
      1. 判断图G是否存在边<x, y>或(x, y)
   2. Neighbors(G, x)
      1. 列出图G中与结点x邻接的边
   3. InsertVertex(G, x)
      1. 在图G中插入顶点x
   4. DeleteVertex(G, x)
      1. 从图G中删除顶点x
   5. AddEdge(G, x, y)
      1. 若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边
   6. RemoveEdge(G, x, y)
      1. 若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边
   7. FirstNeighbor(G, x)
      1. 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
   8. NextNeighbor(G, x, y)
      1. 假设图G中顶点y时顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
   9. Get_edge_value(G, x, y)
      1. 获取图G中边(x, y)或<x, y>对应的权值
   10. Set_edge_value(G, x, y, v)
       1. 设置图G中边(x, y)或<x, y>对应的权值为v
   11. 图的遍历算法
       1. 深度优先遍历与广度优先遍历

图的遍历

广度优先搜索 （Breadth-First-Search，BFS）

1. 基本思想

   1. 首先访问起始顶点v
   2. 接着由v出发，依次访问v的各个未访问过的邻接顶点$w_1,w_2,...,w_i$，然后依次访问$w_1,w_2,...,w_i$的所有未被访问过的邻接顶点
   3. 再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止
   4. 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止

2. 是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点

3. 伪代码如下

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

4. BFS算法的性能分析

   1. 无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)
   2. 采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V| + |E|)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O($|V{|}^2$)

5. BFS算法求解单源最短路径问题

   1. 若图G=（V，E）为非带权图，定义从顶点u到顶点v的最短路径d(u, v)为从u到v的任何路径中最少的边数；若从u到v没有通路，则d(u, v) = $\infty$

   2. 使用BFS，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的

   3. 算法如下

      void BFS_MIN_Distance(Graph G, int u) {
          // d[i]表示从u到i结点的最短路径
          for (i =0; i < G.vexnum; ++i ) {
              // 初始化路径长度
              d[i] = -1;
          }
          
          visited[u] = TRUE;
          d[u] = 0;
          EnQueue(Q, u);
          while( !isEmpty(Q) ) {
      	    // 队头元素u出队
              DeQueue(Q, u);
              for ( w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w) ) {
                  if (!visited[w]) {
                      // w为u的尚未访问的邻接顶点
                      // 设已访问标记
                      visited[w] = TRUE;
                      // 路径长度+1
                      d[w] = d[u] + 1;
                      // 顶点w入队
                      EnQueue(Q, w);
                  }
              }
          }
      }
      

6. 广度优先生成树

   1. 在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。主要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的

      

深度优先搜索 （Depth-First-Search, DFS）

1. 类似于树的先序遍历

2. 基本思想

   1. 首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点$w_1$
   2. 再访问与$w_1$邻接且未被访问的任一顶点$w_2$，重复上述过程
   3. 当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点继续开始上述搜索过程，直至图中所有顶点均被访问过为止

3. 算法过程如下

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

4. 图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的

5. DFS算法的性能分析

   1. 是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为O(|V|)
   2. 遍历图的过程，实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为O(|V|)，故总的时间复杂度为O($|V{|}^2$)。以邻接表表示时，查找所有顶点的临界点所需的时间为O(|E|)，访问顶点所需的时间为O(|V|)，此时，总的时间复杂度为O(|V|+|E|)

6. 深度优先的生成树和生成森林

   1. 与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是广度优先生成森林
   2. 与BFS类似，基于邻接表存储的深度优先生成树是不唯一的

图的遍历与图的连通性

1. 图的遍历算法可用来判断图的连通性
2. 对于无向图来说，若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。
3. 对于有向图来说，若从初识点到图中的每个顶点都有路径，则能够访问到图中所有顶点，否则不能访问到所有顶点
4. 在BFSTraverse()、DFSTraverse()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。

图的应用

最小生成树

1. 一个连通图的生成树包含图中的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路

2. 对于一个带权连通无向图G=（V，E），生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的那棵生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）

3. 不难看出，最小生成树具有如下性质

   1. 最小生成树不是唯一的，即最小生成树的树形不唯一，R中可能有多个最小生成树。当图G中的各边权值互不相等时，G的最小生成树是唯一的；若无向连通图G的边树比顶点树少1，即G本身是一棵树时，则G的最小生成树就是它本身
   2. 最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的
   3. 最小生成树的边树为顶点数减1

4. 构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质

   1. 假设G=（V，E）是一个带权连通无向图，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中$u\in U,v\in V-U$，则必存在一棵包含边（u，v）的最小生成树

   2. 基于该性质的最小生成树算法主要有Prim算法、Kruskal算法，基于贪心算法的策略

   3. 通用的最小生成树算法

      GENERIC_MST(G) {
        T = NULL;
        while T 未形成一棵生成树;
        	do 找到一条最小代价边(u, v)并且加入T后不会产生回路
            T = T U（并） (u, v);
      }
      

5. Prim算法

   1. 类似于寻找图的最短路径的Dijkstra算法

   2. 过程如下图所示

      1. 初始时从图中任取一顶点1加入树T，此时树中只含有一个顶点

      2. 之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T

      3. 每次操作后T中的顶点树和边树都增1

      4. 以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边

         

   3. 算法步骤如下

      1. 假设G={V, E}是连通图，其最小生成树T=（U，$E_T$)，$E_T$是最小生成树中边的集合
      2. 初始化：向空树T=（U, $E_T$)中添加图G=（V，E）的任一顶点$u_0$，使U={$u_0$}，$E_T=\varnothing$
      3. 循环（重复下列操作直至U=V）：从图G中选择满足{(u, v) | $u\in U,v\in V-U$}且具有最小权值的边（u，v），加入树T，置U=U $\bigcup$ {v}，$E_T=E_T\cup (u,v)$

   4. 简单实现如下

      void Prim(G, T) {
        T = NULL;
        U = {w};
        
        while( (V-U) != NULL ) {
            设（u，v）是使u属于U与v属于(V-U)，且权值最小的边
            // 边归入树
            T = T U {(u, v)};
            // 顶点归入树
          	U = U U {v};
        }
      }
      

   5. Prim算法的时间复杂度为O($|V{|}^2$)，不依赖|E|，因为它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进Prim算法的时间复杂度，但增加了实现的复杂性

6. Kruskal算法

   1. 与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法

   2. 构造最小生成树的过程

      1. 初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自称一个连通分量

      2. 按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边

      3. 以此类推，直至T中所有顶点都在一个连通分量上

         

   3. 算法简单实现如下

      void Kruskal(V, T) {
          // 初始化树T，仅含顶点
          T = V;
          // 连通分量数
          numS = n;
          
          // 若连通分量数大于1
          while ( numS > 1 ) {
              // 从E中取出权值最小的边（v，u）
              if ( v和u属于T中不同的连通分量) {
                  // 将此边加入生成树中
                  T = T U {(v, u)};
                  // 连通分量数减1
                  numS--;
              }
          }
      }
      

   4. 根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树

   5. 通常在Kruskal算法中，采用堆来存放边的集合，因此每次选择最小权值的边只需O(log|E|)的时间。此外，由于生成树T中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述T，从而构造T的时间复杂度为O(|E|log|E|)。因此，Kruskal算法适合于边稀疏而顶点较多的图

最短路径

1. 当图是带权图时，把从一个顶点到图中其余任意一个顶点的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条称为最短路径

2. 一般分为两类问题，一是单源最短路径，可通过Dijkstra算法求解；二是求每对顶点间的最短路径，可通过Floyd算法求解

3. Dijkstra算法求单源最短路径问题

   1. 设置一个集合S记录已求得的最短路径的顶点，初始时，把源点放入S，集合S每并入一个新顶点，都要修改源点到集合V-S中顶点当前的最短路径长度值

   2. 在构造的过程中，还设置了两个辅助数组

      1. dist[]
         1. 记录从源点到其他各顶点当前的最短路径长度，它的初态为：若从$v_0$到$v_i$有弧，则dist[i]为弧上的权值；否则置dist[i]为$\infty$
      2. path[]
         1. path[i]表示从源点到顶点i之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点到顶点的最短路径

   3. 算法步骤如下

      1. 初始化，集合S初始为{0}，dist[]的初始值dist[i] = arcs[0][i]，i=1，2，…，n-1

      2. 从顶点集合V-S中选出v，满足dist[j] = Min{dist[i] | $v\in V-S$}，v就是当前求得的一条从源点出发的最短路径的终点，令S = S $\cup$ {j}

      3. 修改从源点出发到集合V-S上任一顶点v可达的最短路径长度，若
         $$dist[j]+arcs[j][k]<dist[k]$$
         则更新dist[k] = dist[j] + arcs[j][k]

      4. 重复2~3操作共n-1次，直到所有的顶点都包含在S中

   4. 使用邻接矩阵表示时，时间复杂度为$O(|V{|}^2)$。使用带权的邻接表表示时，虽然修改dist[]的时间可以减少，但由于在dist[]中选择最小分量的时间不变，时间复杂度仍为$O(|V{|}^2)$

   5. 边上带有负权值时，Dijkstra算法并不适用。若允许边上带有负权值，则在与S（已求得最短路径的顶点集，归入S内的结点的最短路径不再变更）内某点a以负边相连的点b确定其最短路径时，其最短路径长度加上这条负边的权值结果可能小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的

      

4. Floyd算法求各顶点之间最短路径问题

   1. 已知一个各边权值均大于0的带权有向图，对任意两个顶点，要求求出它们之间的最短路径和最短路径长度
   2. 基本思想
      1. 递推产生一个n阶方阵序列$A^{-1},A^0,A^k,...,A^{n-1}$，其中$A^k[i][j]$表示从顶点$v_i$到$v_j$的路径长度，k表示绕行第k个顶点的运算步骤
      2. 初始时，对于任意两个顶点$v_i$和$v_j$
         1. 若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度
         2. 若它们之间不存在有向边，则以$\infty$作为它们之间的最短路径长度
      3. 逐步尝试在原路径中加入顶点k（k=0，1，…，n-1）作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径
   3. Floyd算法的时间复杂度为$O(|V{|}^3)$，不过由于代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的
   4. Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图
   5. 也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次Dijkstra算法，其时间复杂度为$O(|V{|}^2)\times |V|=O(|V{|}^3)$

有向无环图描述表达式

1. 若一个有向图中不存在环，则称为有向无环图，简称DAG图

2. 有向无环图是描述含有公共子式的表达式的有效工具，例如表达式可以用二叉树表示，有一些相同的子表达式，在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间

   

拓扑排序

1. AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。

   1. 在AOV网中，活动$V_i$是活动$V_j$的直接前驱，活动$V_j$是活动$V_i$的直接后继，这种前驱和后继关系具有传递性，且任何活动$V_i$不能以它自己作为自己的前驱或后继

2. 拓扑排序：在图论中，有一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑

   1. 每个顶点出现且只出现一次
   2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径

   或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列

3. 对一个AOV网进行拓扑排序的算法有很多，比较常用的方法的步骤是

   1. 从AOV网中选择一个没有前驱的顶点并输出

   2. 从网中删除该顶点和所有以它为起点的有向边

   3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环

      

4. 算法实现如下

   bool TopologicalSort( Graph G ) {
       // 初始化栈，存储度为0的顶点
       InitStack( S );
       
       for ( int i = 0; i < G.vexnum; i++ ) 
           if ( indegree[i] == 0 )
               // 将所有入度为0的顶点入栈
               Push( S, i );
       // 计数，记录当前已经输出的顶点数
       int count = 0;
       // 栈不空，则存在入度为0的顶点
       while ( !IsEmpty( S ) ) {
           // 栈顶元素出栈
           Pop( S, i );
           // 输出顶点i
           print[count++] = i;
           
           for ( p = G.vertices[i].firstarc; p ; p = p -> nextarc ) {
               // 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
               v = p -> adjvex;
               if ( ! ( --indegree[v] ) )
                   // 入度为0，则入栈
                   Push( S, v );
           }
       }
       
       if ( count < G.vexnum )
           // 排序失败，有向图中有回路
           return false;
       else return true;
   }
   

5. 由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)

6. 对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序

   1. 从AOV网中选择一个没有后继（出度为0）的顶点并输出
   2. 从网中删除该顶点和所有以它为终点的有向边
   3. 重复1和2直到当前的AOV网为空

7. 用拓扑排序算法处理AOV网时，需要注意以下问题

   1. 入度为0的顶点，既没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续
   2. 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的
   3. 由于AOV网中各顶点的地位平等，每个顶点编号都是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角形矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立

关键路径

1. 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值，而AOV网中的边无权值，仅表示顶点之间的前后关系
2. AOE网具有以下两个性质
   1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
   2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
3. 在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有路径上的活动都已完成，整个工程才能算结束。
   1. 因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
4. 完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这时因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得到最短完成时间
5. 寻找关键活动的几个参量的定义
   1. 事件$v_k$的最早发生时间ve(k)
      1. 从源点$v_1$到顶点$v_k$的最长路径长度。事件$v_k$的最早发生时间决定了所有从$v_k$开始的活动能够开工的最早时间。可用下面的递推公式来计算
         1. ve（源点）=0
         2. ve（k）=Max{ve(j) + Weight($v_j,v_k$)}, $v_k$为$v_j$的任意后继，Weight($v_j,v_k$)表示<$v_i$, $v_k$>上的权值
         3. 计算ve（）值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算
   2. 事件$v_k$的最迟发生时间vl（k）
      1. 在不推迟整个工程完成的前提下，即保证它的后继事件$v_j$在其最迟发生时间vl（j）能够发生时，该时间最迟必须发生的时间
   3. 活动$a_i$的最早开始时间e（i）
   4. 活动$a_j$的最迟开始时间l（i）
   5. 一个活动$a_i$的最迟开始时间l（i）和其最早开始时间e（i）的差额d（i）=l（i）-e（i）

查找

查找的基本概念

1. 查找

   1. 在数据集合中寻找满足某种条件的数据元素称为查找。查找的结果一般分为两种：
      1. 查找成功，即在数据集合中找到了满足条件的数据元素
      2. 查找失败

2. 查找表（查找结构）

   1. 用于查找的数据集合称为查找表，它由同一类型的数据元素组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种
      1. 查找某个特定的数据元素是否在查找表中
      2. 检索满足条件的某个特定的数据元素的各种属性
      3. 在查找表中插入一个数据元素
      4. 从查找表从删除某个数据元素

3. 静态查找表

   1. 若一个查找表的操作只涉及上述操作1和2，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树、B树都是二叉排序树的改进。

4. 关键字

   1. 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

5. 平均查找长度

   1. 在查找过程中，一次查找长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为
      $$\mathrm{ASL}=\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{P}}_{\mathrm{i}}{\mathrm{C}}_{\mathrm{i}}$$

      1. n是查找表长度
      2. $P_i$是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i$=1/n；
      3. $C_i$是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标

顺序查找和折半查找

顺序查找 （线性查找）

1. 对顺序表和链表都是适用的。

   1. 对于顺序表，可通过数组下标递增来顺序扫描每个元素；
   2. 对于链表，可通过指针next来依次扫描每个元素

2. 顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找

3. 一般线性表的顺序查找

   1. 基本思想

      1. 从线性表的一端开始，逐个检查关键字是否满足给定的条件。
         1. 若查找成功，返回该元素在线性表中的位置
         2. 若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息

   2. 算法

      typedef struct {
          // 元素存储空间基址，建表时按实际长度分配，0号单元留空，方便实现哨兵机制
          ElemType *elem;
          int TableLen;
      } SSTable;
      
      int Search_Seq(SSTable ST, ElemType key) {
          // 将ST.elem[0]称为”哨兵“。引入它的目的是使得Search_Seq内的循环不必判断数组是否会越界
          // 因为满足i==0时，循环一定会跳出
          // 在程序中引入”哨兵”并不是这个算法独有的。引入“哨兵”可以避免很多不必要的判断语句，
          // 从而提高程序效率
          ST.elem[0] = key;
          for (i = ST.TableLen; ST.elem[i] != key; --i);
          return i;
      }
      

   3. 对于有n个元素的表，给定值key域表中第i个元素相等，即定位第i个元素时，需进行**$n-i+1$**次关键字的比较，即$C_i=n-i+1$。查找成功时，顺序查找的平均长度为
      $$\mathrm{AS}{\mathrm{L}}_{\mathrm{成功}}=\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{P}}_{\mathrm{i}}(\mathrm{n}-\mathrm{i}+1)$$
      当每个元素的查找概率相等，即$P_i=1/n$时，有
      $$\mathrm{AS}{\mathrm{L}}_{\mathrm{成功}}=\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{P}}_{\mathrm{i}}(\mathrm{n}-\mathrm{i}+1)=\frac{\mathrm{n}+1}{2}$$
      查找不成功时，与表中各关键字的比较次数显然是n+1次，从而顺序查找不成功的平均查找长度为$AS{L}_{不成功}=n+1$

   4. 通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列

   5. 综上所述，顺序查找的缺点是当n较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找

4. 有序表的顺序查找

   1. 若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度

折半查找 （二分查找）

1. 仅适用于有序的顺序表

2. 基本思想

   1. 首先将给定值key与表中中间位置的元素比较
      1. 若相等，则查找成功，返回该元素的存储位置
      2. 若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续进行同样的查找
   2. 如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息

3. 算法如下

   int Binary_Search(SeqList 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;
   }
   

4. 在等概率查找时，查找成功的平均查找长度为
   $$ASL=\frac{1}{n}\sum _{i=1}^n{l}_i=\frac{1}{n}(1\times 1+2\times 2+...+h\times 2^{h-1})=\frac{n+1}{n}lo{g}_2(n+1)-1\approx lo{g}_2(n+1)-1$$

   1. h是树的高度，并且元素个数为n时树高$h=\lceil lo{g}_2(n+1)\rceil$，所以折半查找的时间复杂度为$O(lo{g}_{2}n)$，平均情况下比顺序查找的效率高

分块查找 （索引顺序查找）

1. 吸取了顺序查找和折半查找的优点，既有动态结构，又适于快速查找

2. 基本思想

   1. 将查找表分为若干子块
   2. 块内的元素可以无序，但块之间是有序的
      1. 即第一个块中的最大关键字小于第二个块中的所有记录的关键字
      2. 第二个块中的最大关键字小于第三个块中的所有记录的关键字
      3. 以此类推
   3. 建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排序

3. 分块查找分两步

   1. 在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表
   2. 在块内顺序查找

4. 分块查找的平均查找长度为索引查找和块内查找的平均长度之和

5. 将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率的情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为
   $$\mathrm{ASL}={\mathrm{L}}_{\mathrm{I}}+{\mathrm{L}}_{\mathrm{S}}=\frac{\mathrm{b}+1}{2}+\frac{\mathrm{s}+1}{2}=\frac{{\mathrm{s}}^2+2s+\mathrm{n}}{2s}$$

   1. 若$s=\sqrt{n}$，则平均查找长度取最小值$\sqrt{n}+1$
   2. 若对索引表采用折半查找时，则平均查找长度为
      $$\mathrm{ASL}={\mathrm{L}}_{\mathrm{I}}+{\mathrm{L}}_{\mathrm{S}}=\lceil \mathrm{lo}{\mathrm{g}}_2(\mathrm{b}+1)\rceil +\frac{\mathrm{s}+1}{2}$$

B树和B+树

B树及其基本操作

1. B树（多路平衡查找树），B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树可以是空树，或者满足以下条件的m叉树

   1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字

   2. 若根结点不是终端结点，则至少有两棵子树

   3. 除根结点外的所有非叶结点至少有$\lceil m/2\rceil$棵子树，即至少含有$\lceil m/2\rceil$-1个关键字

   4. 所有非叶结点的结构如下

      

      1. $K_i(i=1,2,...,n)$为结点的关键字，且满足$K_1<K_2<...<K_n$
      2. $P_i(i=0,1,...,n)$为指向子树根结点的指针，且指针$P_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$P_i$所指子树中所有结点的关键字均大于$K_i$
      3. $n(\lceil m/2\rceil -1\le n\le m-1)$为结点中关键字的个数

   5. 所有叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

2. B树是所有结点的平衡因子均等于0的多路平衡查找树

   

3. B树的高度（磁盘存取次数）

   1. B树中的大部分操作所需的磁盘存取次数与B树的高度成正比

      1. B树的高度不包括最后的不带任何信息的叶结点所处的那一层

   2. 因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足$n\le (m-1)(1+m+m^2+...+m^{h-1}=m^h-1$，因此有
      $$\mathrm{h}\ge \mathrm{lo}{\mathrm{g}}_{\mathrm{m}}(\mathrm{n}+1)$$

   3. 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大

4. B树的查找

   1. 在B树上进行查找与二叉查找树相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定

   2. B树查找包含两个基本操作

      1. 在B树中找结点
      2. 在结点内找关键字

      由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行，后一个查找操作是在内存中进行，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法

5. B树的插入

   1. 定位

      1. 利用B树查找算法，找出插入该关键字的最底层中的某个非叶结点
         1. 在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置
         2. 插入位置一定是最底层中的某个非叶结点

   2. 插入

      1. 在B树中，每个非失败结点的关键字个数都在区间[$\lceil m/2\rceil$-1, m-1]内

         1. 插入后的结点关键字个数小于m，可以直接插入；

         2. 插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，必须对结点进行分裂

            1. 分裂的方法是

               1. 取一个新结点，在插入key后的原结点，从中间位置$\lceil m/2\rceil$将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置$\lceil m/2\rceil$的结点插入原结点的父结点
               2. 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直到这个过程传到根结点为止，进而导致B树高度增1

               

   3. B树的删除

      1. B树的删除与插入操作类似，但要复杂一些，即要使得删除后的结点中的关键字个数$\ge \lceil m/2\rceil -1$，因此将涉及结点的合并问题

      2. 当被删除关键字k不在终端结点（最底层非叶结点）中时，可以用k的前驱（或后继）$k^1$ 来替代k，然后在相应的结点中删除**$k^1$，关键字$k^1$必定落在某个终端结点中，则转换成了被删关键字在终端结点中**的情形

         

      3. 当被删关键字在终端结点（最底层非叶结点）中时，有下列三种情况

         1. 直接删除关键字。若被删除关键字所在结点的关键字个数$\ge \lceil m/2\rceil$，表明删除关键字后仍满足B树的定义，则直接删去该关键字

         2. 兄弟够借。若被删除关键字所在结点删除前的关键字个数$=\lceil m/2\rceil -1$，且与此结点相邻的右（或左）兄弟结点的关键字个数$\ge \lceil m/2\rceil$，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡

         3. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数$=\lceil m/2\rceil -1$，且此时与该结点相邻的左、右兄弟结点的关键字个数均$=\lceil m/2\rceil -1$，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

            

      4. 在合并过程中，双亲结点中的关键字个数会减1

         1. 若其双亲结点是根结点且关键字个数减少至0（根结点关键字个数为1时，有2棵子树），则直接将根结点删除，合并后的新结点成为根；
         2. 若双亲结点不是根结点，且关键字个数减少到$\lceil m/2\rceil -2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直到符合B树的要求为止

B+树的基本概念

1. B+树是应数据库所需而出现的一种B树的变形树

2. 一棵m阶的B+树应满足以下条件

   1. 每个分支结点最多有m棵子树（孩子结点）
   2. 非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil m/2\rceil$棵子树
   3. 结点的子树个数与关键字个数相等
   4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来
   5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针

3. m阶的B+树与m阶的B树的主要差异如下

   1. 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树
   2. 在B+树中，每个结点（非根内部结点）的关键字个数n的范围是$\lceil m/2\rceil \le n\le m$（根结点：$1\le n\le m$）；在B树中，每个结点（非根内部结点）的关键字个数n的范围是$\lceil m/2\rceil -1\le n\le m-1$，（根结点：$1\le n\le m-1$）
   3. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
   4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的

   

   1. 分支结点的某个关键字是其子树中最大关键字的副本

   2. 通常在B+树中有两个头指针

      1. 一个指向根结点
      2. 一个指向关键字最小的叶结点

      因此，可以对B+树进行两种查找运算

      1. 从最小关键字开始的顺序查找
      2. 从根结点开始的多路查找

4. B+树的查找、插入、删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。

   1. 所以。在B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径

散列表

散列表的基本概念

1. 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)
   1. 散列函数可能会把两个或以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词
2. 散列表：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系

散列函数的构造方法

1. 构造散列函数时必须注意以下几点

   1. 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围
   2. 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生
   3. 散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址

2. 常用的散列函数

   1. 直接定址法

      1. 直接取关键字的某个线性函数值为散列地址，散列函数为
         $$H(key)=key或H(key)=a\times key+b$$

         1. a和b是常数，这种方法最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

   2. 除留余数法

      1. 假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址
         $$H(key)=key(\mathrm{mod}p)$$

   3. 数字分析法

      1. 设关键字是r进制数，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数

   4. 平方取中法

      1. 取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

处理冲突的方法

1. 用$H_i$表示处理冲突中，第i次探测得到的散列地址，假设得到的另一个散列地址$H_1$仍然发生冲突，只得继续求下一个地址$H_2$，依次类推，直到$H_k$不发生冲突为止，则$H_k$为关键字在表中的地址

2. 开放定址法

   1. 可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为
      $$H_i=(H(key)+d_i)(\mathrm{mod}m)$$

      1. H(key)为散列函数
      2. i=0，1，2，…，k（$k\le m-1$)，m表示散列表表长
      3. $d_i$为增量序列

   2. 取定某一增量序列后，对应的处理方法就是确定的，通常有以下4种取法

      1. 线性探测法

         1. 当$d_i=0，1，2，...，m-1$时，称为线性探测法。这种方法的特点是
            1. 冲突发生时，顺序查看表中下一单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表
            2. 线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址。。。从而造成大量元素在相邻的散列地址上聚集，大大降低了查找效率

      2. 平方探测法

         1. 当$d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2$时，称为平方探测法，其中$k\le m/2$，散列表长度m必须是一个可以表示成**$4k+3$的素数，又称二次探测法**
         2. 是一种处理冲突的较好方法，可以避免出现堆积问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半元素

      3. 再散列法 （双散列法）

         1. 当${\mathrm{d}}_{\mathrm{i}}=\mathrm{Has}{\mathrm{h}}_2(\mathrm{key})$时。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数$\mathrm{Has}{\mathrm{h}}_2(\mathrm{key})$计算该关键字的地址增量。它的具体散列函数形式如下
            $${\mathrm{H}}_{\mathrm{i}}=(\mathrm{H}(\mathrm{key})+\mathrm{i}\times \mathrm{Has}{\mathrm{h}}_2(\mathrm{key}))(\mathrm{mod}\mathrm{m})$$
            初始探测位置${\mathrm{H}}_0=\mathrm{H}(\mathrm{key})(\mathrm{mod}\mathrm{m})$，i是冲突的次数，初始为0。在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到${\mathrm{H}}_0$位置

      4. 伪随机序列法

         1. 当$d_i=$伪随机数序列时，称为伪随机序列法

         在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除

3. 拉链法 （链接法，chaining）

   1. 为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。
   2. 拉链法适用于经常进行插入、删除的情况

散列查找及性能分析

1. 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的衡量

2. 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子

   1. 装填因子，在散列表中一般记为$\alpha$，定义为一个表的装满程度，即
      $$\alpha =\frac{\mathrm{表中记录数}\mathrm{n}}{\mathrm{散列表长度}\mathrm{m}}$$

   2. 散列表的平均查找长度依赖于散列表的装填因子，而不直接依赖于n或m。直观的看，表示装填的记录越满，发生冲突的可能性越大

排序

排序的基本概念

排序的定义

1. 算法的稳定性：若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$ke{y}_i=ke{y}_j$，且在排序前$R_i$在$R_j$的前面，若使用某一排序算法后，位置顺序保持不变，则称这个排序算法是稳定的，否则称该排序算法不稳定
   1. 算法是否具有稳定性，并能衡量一个算法的优劣，它主要是对算法的性质进行描述
      1. 如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要
   2. 对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可
2. 在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类
   1. 内部排序，排序期间，元素全部存放在内存中的排序
      1. 一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较
   2. 外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序
3. 通常可以将排序算法分为以下五大类
   1. 插入排序
   2. 交换排序
   3. 选择排序
   4. 归并排序
   5. 基数排序

插入排序

1. 插入排序基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成，由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序、希尔排序

直接插入排序

1. 假设在排序过程中，待排序表**L[1…n]**在某次排序过程中的某一时刻状态如下

   

   要将元素L(i)插入已有序的子序列L[1…i-1]，需要执行以下操作

   1. 查找出L(i)在L[i…i-1]中的插入位置k
   2. 将L[k…i-1]中的所有元素依次后移一个位置
   3. 将L(i)复制到L(k)

   

2. 性能分析如下

   1. 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)

   2. 时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态

      1. 最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)
      2. 最坏情况下，表示元素顺序刚好与排序结果中元素顺序相反，总的比较次数达到最大，为${\sum }_{i=2}^{n}i$，总的移动次数也达到最大，为${\sum }_{i=2}^n(i+1)$
      3. 平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均为$n^2/4$
      4. 因此，直接插入排序算法的时间复杂度为O($n^2$)
      5. 稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法

      大部分排序算法都仅适用于顺序储存的线性表

折半插入排序

1. 先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做改进
   1. 由于是顺序储存的线性表，所以查找有序子表时可以用折半查找来实现
   2. 确定待插入位置后，就可统一地向后移动元素
2. 折半插入排序仅减少了比较元素的次数，约为$O(nlo{g}_{2}n)$，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为$O(n^2)$，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。
3. 折半插入排序是一种稳定的排序方法

希尔排序

1. 直接插入排序算法的时间复杂度为$O(n^2)$，但若待排序列为正序时，其时间复杂度可提高至O(n），由此可见，它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序改进而来，又称缩小增量排序

2. 基本思想

   1. 先将待排序表分割成若干形如L[i, i+d, i+2d, …, i+kd]的特殊子表，即把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈基本有序时，再对全体记录进行一次直接插入排序

   2. 过程如下

      1. 先取一个小于n的步长$d_1$，把表中的全部记录分成$d_1$组，所有距离为$d_1$的倍数的记录放在同一组，在各组内进行直接插入排序

      2. 取第二个步长$d_2<d_1$，重复上述过程，直到所取得到的$d_t=1$，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果

         希尔提出的方法是$d_1=n/2,d_{i+1}=\lfloor d_i/2\rfloor$，并且最后一个增量等于1

   

3. 性能分析

   1. 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
   2. 时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度为$O(n^{1.3})$。在最坏情况下，时间复杂度为$O(n^2)$
   3. 稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法
   4. 适用性：仅适用于线性表为顺序存储的情况

交换排序

1. 根据序列中两个元素关键字的比较结果来交换这两个记录在序列中的位置。基于交换的排序算法很多，主要介绍冒泡排序和快速排序

冒泡排序

1. 基本思想：从后往前两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完

   

快速排序

1. 快速排序的基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其最终位置上L(k)上，这个过程称为一趟快速排序，然后分别递归地对两个子表重复上述过程

2. 性能分析

   1. 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为$O(lo{g}_{2}n)$；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n）；平均情况下，栈的深度为$O(lo{g}_{2}n)$
   2. 时间效率：运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为$O(n^2)$
      1. 提升算法效率的方法
         1. 尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素
         2. 随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生
      2. 快速排序是所有内部排序算法中平均性能最优的排序算法
   3. 稳定性
      1. 在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法

   在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上

选择排序

1. 基本思想是：每一趟（如第i趟）在后面n-i+1(i=1,2,…,n-1)个待排序元素中选择关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。

简单选择排序

1. 基本思想：假设排序表为L[1…n]，第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序
2. 性能分析
   1. 空间效率：仅使用常数个辅助单元，故空间效率为O(1)
   2. 时间效率：从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过**3（n-1）**次，最好的情况是移动0次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是n（n-1）/2次，因此时间复杂度始终是$O(n^2)$
   3. 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。因此是一种不稳定的排序方法

堆排序

1. 堆的定义如下，n个关键字序列L[1…n]称为堆，当且仅当该序列满足

   1. L（i）>= L（2i）且L（i）>=L（2i+1），或者是
   2. L（i）<=L（2i）且L（i）<=L（2i+1） （$i\le i\le \lfloor n/2\rfloor$)

2. 可以将该一维数组视为一棵完全二叉树

   1. 满足条件1的称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。
   2. 满足条件2的称为小根堆（小顶堆），定义刚好相反，根结点是最小元素

3. 堆排序的思路很简单

   1. 将存放在L[1…n]中的n个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值
   2. 输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素
   3. 如此重复，直到堆中仅剩一个元素为止

4. 堆排序需要解决两个问题

   1. 如何将无序序列构造成初始堆

      1. n个结点的完全二叉树，最后一个结点是第$\lfloor n/2\rfloor$个结点的孩子
      2. 对第$\lfloor n/2\rfloor$个结点为根的子树筛选，使该子树成为堆
         1. 对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换
      3. 之后向前依次对各结点（$\lfloor n/2\rfloor -1\sim 1$）为根的子树进行筛选，看该结点值是否大于其左右子结点的值
         1. 若不大于，则将左右子结点中较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止
      4. 反复利用上述调整堆的方法建堆，直到根结点

      

   2. 输出堆顶元素后，如何将剩余元素调整成新堆

5. 堆排序算法的性能分析

   1. 空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1)
   2. 时间效率：建堆时间为O(n），之后有n-1次向下调整操作，每次调整的时间复杂度为O(h），所以在最好、最坏和平均情况下，时间复杂度为$O(nlo{g}_{2}n）$
   3. 稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序算法

归并排序和基数排序

归并排序

1. 归并的含义是将两个或以上的有序表组合成一个新的有序表。假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到$\lceil n/2\rceil$个长度为2或1的有序表；继续两两归并…如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序
2. 性能分析如下
   1. 空间效率：合并操作中，辅助空间刚好为n个单元，所以算法的空间复杂度为O(n)
   2. 时间效率：每趟归并的时间复杂度为O(n)，共需进行$\lceil lo{g}_{2}n\rceil$趟归并，所以算法的时间复杂度为$O(nlo{g}_{2}n)$
   3. 稳定性：由于合并操作不会改变相同关键字记录的相对次序，所以2路归并排序算法是稳定的
3. 一般而言，对于N个元素进行k路归并排序时，排序的趟数m满足$k^m=N$，从而$m=lo{g}_{k}N$，又考虑到m为整数，所以$m=\lceil lo{g}_{k}N\rceil$

基数排序

1. 不基于比较、移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法

2. 为实现多关键字排序，通常有两种方法

   1. 最高位优先法（MSD）：按关键字位权重递减依次逐层划分称若干更小的子序列，最后将所有子序列依次连接成一个有序序列
   2. 最低位优先法（LSD）：按关键字权重递增依次进行排序，最后形成一个有序序列

3. 过程

   

   

   

4. 性能分析如下

   1. 空间效率：一趟排序需要的辅助存储空间为r（r个队列：r个队头指针和r个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O®
   2. 时间效率：基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O®，所以基数排序的时间复杂度为O(d(n+r))，它与序列的初始状态无关
   3. 稳定性：对于基数排序而言，最重要的一点就是按位排序时必须是稳定的，因此，这也保证了基数排序的稳定性

各种内部排序算法的比较及应用

算法种类	时间复杂度最好	时间复杂度平均	时间复杂度最坏	空间复杂度	是否稳定
直接插入排序	O(n)	$O(n^2)$	$O(n^2)$	O(1)	是
冒泡排序	O(n)	$O(n^2)$	$O(n^2)$	O(1)	是
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	O(1)	否
希尔排序				O(1)	否
快速排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n^2)$	$O(lo{g}_{2}n)$	否
堆排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	O(1)	否
2路归并排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n)$	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O®	是

外部排序

外部排序的基本概念

1. 许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换

外部排序的方法

1. 因为磁盘读写的机械动作所需的时间远远超过内存运算的时间，因此在外部排序过程中的时间代价，主要考虑访问磁盘的次数，即I/O次数

2. 外部排序通常采用归并排序法。它包括两个相对独立的阶段

   1. 根据内存缓冲区大小，将外存上的文件分成若干长度为L的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重写回外存，称这些有序子文件为归并段或顺串
   2. 对这些归并段进行逐躺归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止

3. 在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、写入磁盘，而这会耗费大量的时间，一般情况下

   外部排序的总时间 = 内部排序所需的时间 + 外存信息读写的时间 + 内部归并所需的时间