数据结构

绪论

数据结构的基本概念

• 数据与信息

  • 数据是信息的载体

• 数据元素

  • 数据元素是数据的基本单位

  • 数据项是构成数据元素不可分割的最小单位

    • eg：学生是数据元素，学号、姓名等是数据项

• 数据对象

  • 具有相同性质的数据元素的集合

  • 是数据的一个子集

• 数据类型

  • 原子类型

    • 其值不可再分

  • 结构类型

    • 其值可以分解为若干成分

  • 抽象数据类型（ADT）

    • 不关心存储结构

• 数据结构

  • 数据

    • 数据元素

  • 结构

    • 指数据元素相互之间的关系

  • 数据结构是一组存在特定关系的数据元素的集合

数据结构三要素

• 逻辑结构

  • 线性结构

    • 线性表、栈&队列&串（受限线性表）、数组（推广线性表）

  • 非线性结构

    • 树、图、集合

• 存储结构（物理结构）

  • 顺序存储

  • 链式存储

    • 指针

  • 索引存储

    • 索引表

  • 散列存储（hash存储）

• 数据运算

  • 运算的定义（针对逻辑结构）

  • 运算的实现（针对存储结构）

算法

• 算法的五大特征

  • 有穷性

  • 确定性

  • 可行性

  • 输入：零个或多个

  • 输出：一个或多个

• 算法的目标

  • 正确性

  • 可读性

  • 健壮性

  • 效率（时间与空间）

• 算法的效率

  • 时间复杂度

    • 常见的渐进时间复杂度：O(1)<O(log2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

  • 空间复杂度

    • 算法原地工作：O(1)

线性结构

线性表

• 基本概念

  • 位序：从1开始
    下标：从0开始

  • 线性表是逻辑结构
    顺序表和链表是存储结构

• 实现

  • 顺序表（顺序存储）

    • 特点：支持随机存取、存储密度高

    • 分配方式：静态分配、动态分配

  • 链表（链式存储）

    • 单链表

    • 双链表

    • 循环链表

      • 循环单链表

      • 循环双链表

    • 静态链表

      • 借助数组实现
        需要预先分配一块连续的存储空间
        指针是结点的相对地址（数组下标），又称游标

• 时间复杂度分析

  • 按值查找

    • 无序顺序表

      • O(n)

    • 有序顺序表

      • O(log2n)

    • 链表

      • O(n)

  • 按序查找

    • 顺序表

      • O(1)

    • 链表

      • O(n)

栈

• 基本概念

  • 栈的数学性质：n个元素进栈，不同的出栈顺序个数为【】 卡特兰数 见P.61

• 实现

  • 顺序栈（顺序存储）

    • 栈顶指针 S.top

      • 初始值：-1(通常)

        • S.top == -1

        • S.top == MaxSize-1

        • S.top+1

      • 初始值：0(可选)

        • S.top == 0

        • S.top == MaxSize

        • S.top

  • 共享栈（顺序存储）

    • 两个顺序栈共享存储空间

    • top0=-1时 0号栈为空

    • top1=MaxSize时 1号栈为空

    • top1-top0 == 1时 栈满（栈顶指针相邻）

  • 链栈（链式存储）

    • 所有操作在单链表的表头进行

• 应用

  • 括号匹配

  • 后缀表达式求值

    • 中缀表达式与后缀表达式的转换

    • 遇到数值：进栈
      遇到操作符：出栈-运算-进栈

  • 递归算法

    • 将递归算法转换为非递归算法，通常借助栈

    • 但是，消除尾递归通常可以借助循环体完成

• 卡特兰数的应用

  • 卡特兰数F(n) = C(n,2n)/(n+1)

  • 求出栈序列数

    • n个不同元素依次入栈，求不同出栈序列数

    • 在受限的双端队列中，根据条件合理使用

  • 求二叉树

    • n个结点组成的二叉树的不同形状的个数

    • 当给定遍历序列时，求n个不同结点所组成的不同二叉树的个数（确定的形状+确定的序列可唯一确定二叉树，给定序列从而转换成求不同形状的个数）

  • 括号匹配

    • n对括号多少种匹配序列（等价于遇到左括号入队，右括号出队，从而转换为出栈序列数）

队列

• 实现

  • 循环队列（顺序存储）

    • 队头指针Q.front：指向队头元素

    • 队尾指针Q.rear：指向队尾元素的下一个

    • 队空条件：Q.front == Q.rear

    • 如何区分队空和队满？

      • 牺牲一个存储单元，队满条件为(Q.rear+1)%MaxSize == Q.front

      • 增设Q.size数据成员
        队空：Q.size == 0
        队满：Q.size == MaxSize

      • 增设tag数据成员
        队空：若因删除导致Q.front=Q.rear，置tag为0
        队满：若因插入导致Q.front=Q.rear，置tag为1

  • 链式队列（链式存储）

    • 队空条件：Q.front == Q.rear

      • PS：不带头结点，两者都为null

    • 注意是否带头结点

      • 带头结点（通常）

        • 插入和删除元素时无需区分是否为队空

      • 不带头结点

        • 插入元素前：若队空，Q.front=Q.rear=新结点

        • 删除元素后：若队空，Q.front=Q.rear=null

  • 双端队列

    • 又衍生出 输出/输入受限的双端队列

    • 常考：给定输入序列，判断输出序列是否合法

    • 难点（通常不考）：利用卡特兰数等知识，计算可能的输出序列个数

• 应用

  • 层次遍历二叉树

数组

• 应用：压缩矩阵

  • 对称矩阵

  • 三角矩阵

    • 上三角矩阵

    • 下三角矩阵

  • 三对角矩阵

    • 将三条对角线上的元素按行优先方式存放在一维数组中

  • 稀疏矩阵

    • 1)将非零元素对应成一个三元组(行标,列标,值)

    • 2)按照某种规律存储这些三元组，如：

      • 数组存储

      • 十字链表存储

串

• 实现

  • 定长顺序存储表示
    （顺序存储）

    • 静态分配固定长度的存储区，即定长数组

    • 缺点：限制了串长的最大值，超过时采取“截断”

  • 堆分配存储表示
    （顺序存储）

    • 采用动态分配方式，存储于堆中

  • 块链存储表示
    （链式存储）

    • 一个结点称作一个块，各块按照链表结构相连；
      块的大小固定，一个块可以存储一个或多个字符，一个结点占不满时通常用“#”补位

• 串的模式匹配

  • 暴力匹配算法

  • KMP算法

    • （1）分析模式串t的PM表

      • 计算所有前缀的最长相等前后缀长度PM

    • （2）得到优化后的next[j]数组

      • 将PM表整体右移，首位以-1填充

      • 注（下标从0开始）：
        next[0] = -1
        next[1] = 0
        j>1时, next[j] >= 0

        • PM/next数组的后一项最多比前一项大1

    • [可选]next数组进一步优化为nextval

      • nextval[0]=next[0]=-1
        对next从左往右：
        for(j=1;j++){
        若t[j]==t[next[j]]
        则nextval[j] = nextval[next[j]]
        否则，nextval[j] = next[j]
        }

    • 若下标从1开始计，则next、nextval整体再+1
      用0代表原来的-1的含义

    • （3）模式匹配，在主串s中找模式串t

      • 当t[j] != s[i]，发生失配时，则j=next[j]，
        并重新比较t[j]和s[i]（若j != -1）

      • 若next[j]==-1（j==0），则
        i++, j++;
        即主串和模式串同时右移一位

• 时间复杂度分析

  • 主串长n，子串（模式串）长m

    • 暴力模式匹配算法

      • 最坏时间复杂度为O(mn)
        实际情况一般近似为O(m+n)

    • KMP算法

      • O(m+n)

  • KMP算法 仅在主串与子串有很多“部分匹配”时，显得更快，主要优点是不回溯

非线性结构

树形结构

• 树

  • 基本概念

    • 结点的度 & 树的度；
      注意m叉树≠度为m的树（m叉树的度≤m）

    • 无序树 & 有序树

    • 路径：一定是从上向下的
      路径长度：路径上所经过的边的个数
      树的路径长度：树根到每个结点的路径长度的总和

  • 存储结构

    • 双亲表示法

      • 顺序存储，通常采用数组（类似静态链表）

    • 孩子表示法

      • 链式存储，每个结点拥有一个孩子链表（单链表）

    • 孩子兄弟表示法

      • 二叉树表示法，以二叉链表作为树的存储结构

• 二叉树

  • 基本概念

    • 二叉树是有序树

    • 特殊的二叉树

      • 满二叉树

      • 完全二叉树

      • 二叉排序树

        • 左子树<父结点<右子树

      • 平衡二叉树

        • 左子树和右子树的深度之差不超过1

    • 唯一地确定一颗二叉树

      • 先序+中序

      • 后序+中序

      • 层序+中序

  • 实现

    • 顺序存储结构

      • 适合满二叉树和完全二叉树

      • （通常）根节点下标从1开始，则
        结点 i 的双亲为 floor[i/2]
        结点 i 的左孩子（若有）为 2i
        结点 i 的右孩子（若有）为 2i+1

    • 二叉链表（链式存储）

      • n个结点 2n个链域
        n-1个指针域 n+1个空链域

      • 遍历算法

        • 先序遍历

        • 中序遍历

        • 后序遍历

        • 层序遍历

    • 线索二叉树（链式存储）

      • 标志域的含义

        • ltag

          • 0,

            • lchild域 指示结点的 左孩子

          • 1,

            • lchild域 指示结点的 前驱

        • rtag

          • 0,

            • rchild域 指示结点的 右孩子

          • 1,

            • rchild域 指示结点的 后继

      • 构造线索二叉树

        • 根据不同顺序遍历二叉树，实现不同的线索化：
          先序/中序/后序线索二叉树

        • 可以增加一个头结点，
          lchild 指向 二叉树的根节点，
          rchild 指向 遍历时的最后一个结点，
          第一个结点的lchild域指针 和
          最后一个结点的 rchild域指针 均指向头结点

      • 遍历线索二叉树

        • 先序不一定能找到前驱结点
          后序不一定能找到后继结点
          借助三叉链表才能一定找得到

          • 找前驱结点

            • √

            • ×

            • √

          • 找后继结点

            • √

            • √

            • ×

        • 先序找后：先左孩子，再右孩子/后继

          • 先序一定能找到后继结点，不用栈即可先序遍历

        • 后序找前：先右孩子，再左孩子/前驱

          • 后序一定能找到前驱结点，可以逆向后序遍历

        • 后序不一定能找到后继结点，一般需要借助栈遍历（但后序反向遍历则不用借助栈）

• 森林

  • 森林和二叉树的转换

  • 树和森林的遍历与对应二叉树遍历的关系

    • 树

      • 先根遍历

        • 后根遍历

    • 森林

      • 先序遍历

        • 中序遍历

    • 二叉树

      • 先序遍历

        • 中序遍历

• 性质

  • 一般树的性质

    • 结点数 = 所有结点的度数之和+1

  • 二叉树的性质

    • n0 = n2 + 1

    • 第k层至多有2^(k-1)个结点

    • 高h最多有2^h - 1个结点

  • 完全二叉树的性质

    • 结点 i 所在层次（深度）为 floor[log2(i)] + 1

    • 具有n个结点的完全二叉树，其高度为
      ceil[log2(n+1)] 或 floor[log2(n)] + 1

    • 若有2k 个结点，则n0=k, n1=1, n2=k-1；
      若有2k-1个节点，则n0=k, n1=0, n2=k-1

  • m叉树

    • 第k层至多有m^(k-1)个结点

    • 高h最多有(m^h-1)/(m-1)个结点

    • 完全m叉树，高度h和结点n的关系为：

  • 将森林或树转成对应的二叉树，则
    左指针为空的个数 = 原先叶子结点的个数
    右指针为空的个数 = 原先非叶结点数+1

    • 1.左指针为空，即没有孩子。
      2.一组兄弟（同一个父），对应一个空的右指针，根结点没有父，右指针也为空。

• 应用

  • 哈夫曼树

    • 定义

      • 带权路径长度WPL最小的二叉树为哈夫曼树

    • 快捷计算WPL（非定义法）

      • 所有非叶节点的权值之和（仅适用哈夫曼树）

    • 构造过程

    • 哈夫曼编码

      • 前缀编码：没有一个编码是另一个编码的前缀

    • m叉哈夫曼树

      • 补充权值为0的结点，以满足(n-1)%(m-1)=0

  • 并查集

    • 存储结构：通常采用树的双亲表示法（顺序存储）

    • 每个集合用一颗树表示，
      根结点的下标代表集合名，
      根节点的双亲结点为负数，可取元素个数的相反数，
      表示所有集合的树构成表示全集合的森林

    • 操作

      • Initial(S)

        • 将全集S中的每个元素初始化为只有单元素的子集

        • 只需要将各元素的双亲结点置为-1

      • Find(S, x)

        • 查找S中结点x所在的子集合，并返回子集合名（根结点）

        • Find操作的时间复杂度与树的最大高度有关，故应当设法优化减小树的高度

      • Union(S, Root1, Root2)

        • 将S中Root2连接到Root1下，要求两个集合互不相交

        • Union本身不耗费时间，即O(1)，但Union前需要经过Find操作找到集合的根结点

      • Find优化（压缩路径）

        • 1）Find时，先找到所属根结点；
          2）将查找路径上的结点都直接挂在根结点下

      • Union优化

        • 1）用根结点的绝对值表示一棵树的结点总数
          2）Union时，小树并入大树
          可以保证树的高度小于log2(n)

    • 时间复杂度分析

      • Find操作

        • O(n)

          最坏情况下，每次Union操作，都使树高增加1，那么n个元素的树高为n，则进行Find操作的时间复杂度为O(n)

        • O(logn)

          经过Union优化后，设两个集合的树高分别为h和H（h<H），则每次Union将小树合并到大树，则新的树高为max{h+1, H}。
          也就是说仅当两颗树一样高时，新的树比原来的树高增加1。
          最坏情况下，每次合并优先考虑两颗等高的树，类似于归并排序的树形，最终树高一定小于log2(n)
          所以，Find操作的时间复杂度为O(logn)

        • O(α(n))

          对于任意树形，经过一次优化Find后，就会被压缩路径，优化下一次的查找时间，时间复杂度记为O(α(n))

      • （将n个独立元素合并）
        Unionn次，即Findn次

        • O(n^2)

        • O(nlogn)

        • O(nα(n))

    • 应用

      • 判断图的连通性

        • 1）初始时，每个顶点单独一个集合
          2）根据边两两合并集合
          3）若最终合并到一个集合，则为连通图

      • 判断图是否有环

        • 1）2）同上
          3）若合并过程中，出现一条边的两个顶点属于同一集合，说明出现了环

      • 实现kruskal算法

        • 生成最小生成树，依次连接权值最小且不属于同一集合的两个顶点。时间复杂度为O(eloge)

  • 二叉排序树（BST）

    • 定义

      • 左子树结点值 < 根结点值 < 右子树结点值

    • 插入结点

      • 插入的结点一定是一个叶子结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子

    • 删除结点

      • 1）叶子结点，直接删除
        2）只有一颗子树，删除后，由子树替代原来的位置
        3）有两颗子树，由被删除结点的直接后继（或直接前驱）替代，再删除这个直接后继（前驱）

    • 根据序列构造一棵二叉排序树

    • 查找效率

      • 时间复杂度

        • O(h) = O(logn) ~ O(n)
          高度平衡时，为平衡二叉树，O(logn)
          最坏情况（单边树），O(n)

      • 空间复杂度

        • 非递归实现：O(1)
          递归实现：O(h) = O(logn) ~ O(n)

    • 适用场合

      • 静态查找表适合：采用顺序存储，二分查找方法
        动态查找表适合：采用二叉排序树存储

  • 平衡二叉树（AVL）

    • 定义

      • 结点的平衡因子：左右子树的高度差

      • AVL树的结点平衡因子的值是1, -1或0

    • 插入结点

      • 插入后调整最小不平衡子树：
        ① LL右旋
        ② RR左旋
        ③ LR先左后右
        ④ RL先右后左

    • 删除结点

      • 按照二叉排序树删除结点，
        找到最小不平衡子树z，
        找到z的最高孩子y和y的最高孩子x。
        根据根据z/y/x的位置调整最小不平衡子树：
        ① LL右旋
        ② RR左旋
        ③ LR先左后右
        ④ RL先右后左
        调整后若子树高度改变(减1)，检查祖先平衡因子

    • 查找效率

      • 时间复杂度：O(logn)

    • 重要结论
      （规律）

      • 当所有非叶结点的平衡因子均为1/-1时，AVL的结点最少。用n(h)表示深度为h的AVL中的最少结点数，则有：
        n(0)=0, n(1)=1, n(2)=2,
        n(h) = n(h-1) + n(h-2) + 1

  • 红黑树

    • 性质

      • 根叶黑，红相隔，黑高一致

        • 叶结点是虚构的，对应bh=0

    • 结论

      • 最长路径<=最短路径*2

        • 理解：黑结点数相同，红结点<=黑结点
          最长路径<=bh*2（红黑相间）
          最短路径>=bh（全为黑）

      • 平衡性：左右子树高度相差不超过2倍

      • 查找效率：O(logn)

    • 应用

      • C++：map、set
        JAVA：TreeSet、TreeMap

    • 插入结点

      • 新插入结点为红色，若为根，染成黑；
        父为黑，则OK；父为红，做调整。

      • 红父调整看叔叔：
        黑叔跟着AVL，红叔换色再循环

        • 【黑叔跟着AVL】
          ① LL右旋【情况2】
          ② RR左旋【情况2】
          ③ LR先左后右【情况1】
          ④ RL先右后左【情况1】

        • （父叔为红，爷为黑）
          【红叔换色再循环】
          父层爷层对调色，
          指针上移指向爷。
          将爷视作新结点，
          根据规则再循环。
          （若为根，染成黑；
          父为黑，则OK；
          父为红，再调整）

    • 删除结点

      • 有孩找下位填补；
        红色无孩直接删；
        黑色无孩转双黑；
        恢复双黑看兄弟

        • -下位指中序后继/前驱，下位可能是单孩或无孩
          -仅填补结点内容，原来位置的颜色不变
          -转为删除下位结点
          -单孩的下位取孩结点（必为红色的前驱/后继）

      • 恢复双黑看兄弟

        • 红兄弑父并换色

          • 弑父：指父亲变孩子，红兄来做父亲
            换色：交换父和兄的颜色
            （即红兄和黑父的地位和颜色都交换了）
            转变为黑兄情况（情况1->情况2/3/4）

        • 黑兄红孩往上旋

          • 旋转同AVL
            ① LL右旋【情况3】
            ② RR左旋【情况3】
            ③ LR先左后右【情况2】
            ④ RL先右后左【情况2】
            （情况2->情况3，未改变左右黑高）
            （情况3->over，双黑结点所在路径的黑高增加1，因此双黑结点可以恢复为单黑）

              -  
            

        • 黑兄黑孩黑上升

          • 将双黑的一层黑色和黑兄的黑色给父亲；
            若父亲红色->黑色，结束；
            若父亲黑色->双黑，循环（回到情况1/2/3/4）
            （若从1->4则不会循环，4->over；仅一开始为4的情况可能一直循环4到根结点）

  • B树 & B+树

    • B树（多路平衡查找树）

      • 基本概念与性质

        • B树的阶：所有结点的孩子个数的最大值
          B树的高：不包含外部结点（叶结点）的那一层

        • 内部结点：非叶结点（携带关键字）
          外部结点：叶子结点（不含信息），表示查找失败
          终端结点：最底层的非叶结点（属于内部结点）

          • B树的外部结点都位于同一层上，
            外部结点的个数=关键字个数+1

        • 一颗m阶B树满足：
          1）结点最多有m棵子树，至多有m-1个关键字
          2）若根结点不是终端结点，则至少有两颗子树
          3）除根结点外的所有非叶结点至少有ceil[m/2]棵子树，至少含有ceil[m/2]-1个关键字

        • 包含n个关键字、高度为h、阶数为m的B树，应满足：
          ① 关键字尽量多，高度尽量小
          n ≤ m^h - 1 或 h ≥ log(m, n+1)
          ② 关键字尽量少，高度尽量高
          n+1 ≥ 2*(ceil[m/2])^(h-1)

          ① 关键字尽量多，高度尽量小
          每个结点最多含有m-1个关键字，共(1+m+m^2+...+m^(h-1))个结点：
          n ≤ (m-1)(1+m+m^2+...+m^(h-1)) = m^h - 1

          ② 关键字尽量少，高度尽量高
          1层：根结点 1个关键字
          2层：至少2个结点
          3层：至少2ceil[m/2]个结点
          4层：至少2(ceil[m/2])^2个结点
          h层：至少2*(ceil[m/2])^(h-2)个结点
          h+1层（外部结点）至少2*(ceil[m/2])^(h-1)个结点
          【方法1】
          1层：1个关键字；
          2~h层：首项为2，公比为ceil[m/2]，项数为h-1，每个结点有ceil[m/2]-1个关键字。
          求得n ≥ 2(ceil[m/2])^(h-1) - 1

          【方法2】
          根据外部结点个数 = 关键字个数+1
          有n+1 ≥ 2*(ceil[m/2])^(h-1)

      • 基本操作

        • B树的查找

          • 1）在B树中找结点

            • 在磁盘中进行，找到目标结点后，读入内存

          • 2）在结点内找关键字

            • 在内存中进行，结点内可采用顺序查找或折半查找

          • 注意：不能有效的支持顺序查找

        • B树的插入
          （分裂）

          • 1）定位：插入位置是查找失败时的叶结点所对应的非叶结点（位于最底层）
            2）插入：插入后若关键字个数>m-1，进行分裂（中间关键字向上一层移动，可能导致连锁分裂）

        • B树的删除
          （合并）

          • 1）被删除关键字不在终端结点中，则用前驱或后继替代，并在相应的结点中删除该前驱/后继
            2）被删除的关键字在终端结点中：
            ①直接删除：删除关键字后仍满足B树性质，直接删除
            ②兄弟够借：进行一次旋转，挪过来一个关键字。
            ③兄弟不够借：与兄弟结点和[双亲结点中的关键字]进行合并。
            i)合并后双亲结点关键字减少1，可能要继续调整或合并；
            ii)若双亲结点是根结点，且关键字减少到了0，则删除根结点，由其子结点成为新的根结点，对应B树的高减小1

    • B+树

      • 应用于数据库中，是B树的一种变形树

      • 具有n个关键字的结点对应n棵子树，
        每个关键字对应一颗子树

      • 结点的划分

        • 内部结点

          • 分支结点
            （非叶结点）

            • 包含子结点关键字的最大值

          • 叶结点

            • 包含全部关键字和指向记录的指针

        • 关键字个数及子树个数n：
          根结点：2 ≤ n ≤ m
          非根结点：ceil[m/2] ≤ n ≤ m

      • 查找操作：
        1）无论查找是否成功，最终都走到叶结点
        2）支持顺序查找和多路查找（随机查找）

      • 插入和删除操作与B树类似

图

• 基本概念

  • 有向图 & 无向图

  • 简单图 & 多重图

  • 完全图（简单完全图）

    • 无向完全图有C(2,n)条边
      有向完全图有2C(2,n)条边

  • 子图 & 生成子图

    • 顶点集合与原图一致的子图，为生成子图
      即满足V(G)=V(G')

  • 连通性

    • 无向图

      • 连通图：任意两个顶点之间连通

      • 连通分量：极大连通子图

    • 有向图

      • 强连通图：任意两个顶点之间互相连通

      • 强连通分量：极大强连通子图

    • 连通图 至少有n-1条边；非连通图 至多有C(2,n-1)条边；
      强连通图 至少有n条边

  • 生成树 & 生成森林

    • 连通图的生成树：包含全部顶点的极小连通子图

      • 顶点为n的连通图，生成树有n-1条边

      • 若砍去一条边，则一定会变成非连通图；
        若增加一条边，则一定会形成一条回路

    • 非连通图的生成森林：由连通分量的生成树构成

  • 顶点的度、入度、出度

    • 无向图的顶点的 度之和 = 边数*2

    • 有向图的顶点的 入度之和 = 出度之和 = 边数

  • 带权图（网）

  • 稠密图 & 稀疏图

  • 路径 & 回路
    简单路径 & 简单回路

  • 有向树

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

• 存储结构

  • 邻接矩阵法

    • 空间复杂度：O(n^2)

    • 设A为邻接矩阵
      则A^n[i][j] = 顶点i到顶点j长度为n的路径的条数

    • 适合表示 稠密图

  • 邻接表法

    • 空间复杂度

      • 无向图：O(n+2e)

      • 有向图：O(n+e)

    • 适合表示 稀疏图

    • 有向图中，求出度容易、求入度麻烦
      采用逆邻接表，则求入度容易，求出度麻烦

    • 图的邻接表表示并不唯一

  • 邻接多重表（无向图）

    • 空间复杂度：O(n+e)

    • 属于链式存储结构，但顶点之间是顺序存储的

    • 结构

      • 顶点结点：（data，firstedge）

      • 边结点：（ivex，ilink，jvex，jlink）

  • 十字链表（有向图）

    • 空间复杂度：O(n+e)

    • 属于链式存储结构，但顶点之间是顺序存储的

    • 结构

      • 顶点结点：（data，firstin，firstout）

      • 弧结点：（tailvex，headvex，hlink，tlink）

• 图的遍历

  • 广度优先遍历（BFS）

    • 需要借助辅助队列

  • 深度优先遍历（DFS）

    • 需要应用递归（栈）

  • BFS和DFS算法复杂度分析

      - 邻接矩阵
    
      	- 邻接表
    

    • 时间复杂度

      • O(n^2)

        • O(n+e)

    • 空间复杂度

      • O(n)

  • 应用

    • 通过BFS求无权图的单源最短路径

    • 可以通过DFS实现 逆拓扑排序（借助栈逆置，得到拓扑排序）

    • 通过BFS或DFS判断 无向图 的 连通性；
      求出 无向图 的 连通分量数

      • 但是，无法判断有向图的 连通性，因为：
        1）强连通分量：从任意顶点出发，调用一次即可全部遍历
        2）非强连通分量：需要调用一次或多次才可全部遍历
        3）不连通图：一定需要多次调用才可全部遍历

    • 连通图：构造 广/深度优先生成树
      非连通图：构造 广/深度优先生成森林

      • 对于邻接矩阵存储结构，其生成树唯一（邻接矩阵唯一）
        对于邻接表存储结构，其生成树不唯一（邻接表不唯一）

• 图的应用

  • 最小生成树（MST）

    • 基本概念

      • 权值之和最小的生成树为最小生成树

      • 最小生成树通常是不唯一的，但边的权值之和是唯一的。
        当图中各边权值互不相等时，其最小生成树一定是唯一的

      • Prim算法和Dijkstra算法的比较

        • Prim算法和Dijkstra算法都能构造一棵生成树，但是Prim算法可以构造出MST，
          而Dijkstra则不一定

        • Prim算法依次选取距MST最近的顶点；
          Dijkstra算法依次选取距源点最近的顶点

    • Prim算法 和 Kruskal算法 比较

      • Prim算法

        • 依次选择距离生成树T最近的顶点

        • 1）数组isjoin记录顶点是否已被选取
          2）数组lowcost记录各顶点到当前树的边的最小权值；根据新加入的顶点，实时更新

        • 边稠密的图

        • O(n^2)
          1）在lowcost中更新和选取顶点，O(n);
          2）共需要n轮

      • Kruskal算法

        • 按权值的递增次序选择合适的边
          （属于不同的连通分量的边）

        • 边稀疏而顶点较多的图

        • 1）采用堆来存放所有边（连通分量）
          2）采用并查集来描述连通分量

        • O(elog(e))
          1）在堆中查找最小边，需要O(log(e))；
          2）若边关联的点已经在一个连通分量中了，则舍弃这条边，最坏情况下要选取e次

  • 最短路径

    • Dijkstra算法 和 Floyd算法 比较

      • Dijkstra算法

        • 依次选择距离源点最近的顶点

        • 1）数组dist记录源点到其他各点的最短路径长度
          2）数组path记录源点到各顶点的最短路径的前驱结点

        • O(n^2)
          1）在dist中更新和选取顶点，O(n);
          2）共需要n轮

        • O(n)

      • Floyd算法

        • 从邻接矩阵开始，每经过一次迭代，就多考虑一个顶点
          A(-1)是邻接矩阵（不经过任何顶点的路径长度）
          A(0)表示经过顶点V0的各顶点间最短路径长度
          A(i)表示经过顶点编号0~i的最短路径长度
          直到A(n-1)

        • 用path矩阵记录各顶点间最短路径经过的最后一个中转点（-1表示不经过任何顶点）；
          A(-1)对应path(-1)，各元素值为均为-1；
          A(i)对应path(i)，各元素值≤i，表示最短路径经过的最后一个中转点编号

        • O(n^3)
          1）每次更新矩阵都需要O(n^2)；
          2）共需要n轮

        • O(n^2)

    • 各种最短路径算法的适用情况比较

      • BFS

        • √

        • ×

        • ×

        • ×

        • 邻接矩阵O(n^2); 邻接表O(n+e)

        • 单源、无权

      • Dijstra

        • √

        • √

        • ×

        • ×

        • 单源O(n^2); 全部顶点O(n^3)

        • 单源、带权

      • Floyd

        • √

        • √

        • √

        • ×

        • 全部顶点O(n^3)

        • 多源、带权

  • 有向无环图（DAG）描述表达式

    • 有向无环图（DAG）：不存在环的有向图。
      AOV和AOE都属于DAG

    • DAG适合描述有公共子式的表达式，每个操作数在图中只出现1次

    • 步骤：
      1）先写操作数
      2）按照运算顺序自底向上（分层）写运算符
      3）自底向上逐层合并运算符

  • 拓扑排序

    • AOV网（Activity On Vertex）

      • 顶点表示活动，边表示前置关系

    • 拓扑排序：依次输出没有前驱的顶点
      逆拓扑排序：依次输出没有后继的顶点

      • 拓扑排序的逆序一定是逆拓扑排序，反之亦然。
        但它们都不是唯一的

    • 若无法拓扑排序，说明有向图中存在环，反之亦然

    • 若存在拓扑序列，对邻接矩阵进行重新编排，可以得到一个三角矩阵。
      若邻接矩阵是三角矩阵，则一定存在拓扑序列。

    • 实现

      • 类BFS实现

        • 1）求出所有顶点的入度
          2）选取入度为0的顶点输出并[入队]
          3）[出队]并更新所关联顶点的入度
          重复2~3，直到全部输出为止

      • DFS实现

        • DFS回溯时，输出顶点，得到逆拓扑序列；
          可以通过栈进行倒置，得到拓扑序列

    • （拓扑排序）时间复杂度
      PS：同BFS/DFS的时间复杂度

      • 邻接矩阵

        • O(n^2)

      • 邻接表

        • O(n+e)

  • 关键路径

    • AOE网（Activity On Edge）

      • 边表示活动，边的权值表示活动的时间，
        顶点表示事件

      • 仅有一个入度为0的点，为开始顶点（源点）
        仅有一个出度为0的点，为结束顶点（汇点）

      • 事件的最早发生时间ve
        事件的最迟发生时间vl
        活动的最早开始时间e
        活动的最迟开始时间l
        活动的时间余量d = l - e

      • 关键路径

        • 关键路径的长度，
          是从源点到汇点最大路径长度，
          也是完成整个工程的最短时间

      • 关键活动

        • 通过加快关键活动来缩短整个工期
          缩短到一定程度，该关键活动可能变成非关键活动

        • 可能同时存在多条关键路径，此时只有加快包括在所有关键路径上的关键活动才能缩短工期。

    • 时间复杂度：同BFS/DFS

• 图的相关操作时间复杂度汇总

  • Dijkstra

    • O(n^2)

  • Floyd

    • O(n^3)

  • Prim

    • O(n^2)

  • Kruskal

    • O(eloge)

  • DFS/BFS

    • O(n^2)

    • O(n+e)

  • 拓扑排序/关键路径

    • O(n^2)

    • O(n+e)

查找

基本概念

• 查找表（查找结构）

  • 静态查找表

    • 只涉及查找而无需修改表的内容

  • 动态查找表

    • 需要动态地插入或删除元素的查找表

线性结构

• 顺序查找

  • 平均查找长度

    • 无序表

      • ASL成功 = (n+1)/2

        • ASL失败 = n+1

    • 有序表

      • ASL成功 = (n+1)/2

        • ASL失败 = n/2 + n/(n+1)

  • 优化方法：
    1）元素按照查找概率降序排列，可优化ASL成功
    2）采用有序表，可优化ASL失败

  • 适合顺序和链式存储结构

• 折半查找

  • 缺点：
    要求元素有序；
    仅适合顺序存储结构

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

  • 块内无需，块间有序。
    索引表记录各块的最大关键字

  • ASL = L(I)索引查找 + L(S)块内查找

  • 注意：折半查找索引表时，出现low>high后，则在low所指向的分块内查找

  • 平均查找长度（n条记录分成b块，每块s条）

    • 索引 顺序查找
      块内 顺序查找

      • L(I) = (b+1)/2
        L(S) = (s+1)/2
        ASL = (b+1)/2 + (s+1)/2

        • 当s = b = √n时，ASL取最小值√n + 1

    • 索引 折半查找
      块内 顺序查找

      • L(I) = ceil(log2(b+1))
        L(S) = (s+1)/2
        ASL = ceil(log2(b+1)) + s+1

  • 优化方法：每个分块取√n条记录

树形结构

• 二叉排序树

• 二叉平衡树

• 红黑树

• B树、B+树

散列结构

• 散列表

  • 基础概念

    • 散列表 & 散列函数

    • 同义词

      • 发生碰撞的不同关键字

    • 冲突（碰撞）

      • 不同关键字映射到同一地址产生冲突

    • 聚集（堆积）

      • 两个非同义词之间争夺同一个后继哈希地址的现象

  • 构造方法

    • 直接定址法

      • 直接取关键字的某个线性函数值为散列地址

      • H(key) = key 或 H(key) = a × key + b

      • 优点：不会产生冲突
        缺点：若关键字的分布不连续，容易浪费空间
        适合：关键字分布基本连续的情况

    • 除留余数法

      • H(key) = key % p

    • 数字分析法

      • 选取数码分布较为均匀的若干位作为散列地址

      • 适合于已知的关键字集合

    • 平方取中法

      • 取关键字的平方值的中间几位作为散列地址

      • 适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

  • 冲突处理

    • 开放定址法

      • 存放新表项的空闲地址既对同义词开放，又对非同义词开放

      • Hi = (H(key) + di) % m

        • 线性探测法

          • di = 0, 1, 2,...,m-1

          • 缺点：容易产生聚集（堆积）

        • 平方探测法
          (二次探测法)

          • di = 0², 1², -1², 2², -2², ..., k², -k²
            表长m必须是一个可以表示成4k+3的素数

          • 优点：减轻“堆积”问题
            缺点：不能探测到所有单元（但至少一半以上）

        • 再散列法
          (双散列法)

          • di = i * Hash2(hey)
            Hi = (H(key) + i * Hash2(hey)) % m

          • 注意：Hash2计算出来的是关键字的探测增量

          • 最多经过m-1次探测，就会遍历表中所有位置，回到H0

        • 伪随机序列法

          • di = 伪随机序列

      • 注意：采用开放定址法，不能随便删除已有元素，可能会截断其他具有相同散列地址的元素的查找地址。可以采取做一个删除标记，进行逻辑删除。因此也需要定期维护散列表，把要删除的元素物理删除。

    • 拉链法

      • 把所有同义词存放在一个线性链表中

      • 完全避免了聚集现象（或称非同义词的冲突）

  • 性能分析

    • 一般通过ASL来衡量查找效率

      • 计算ASL[失败]时，失败位置是否计算：
        数组访问到空计入次数，链表空指针不计入次数

    • 查找效率的影响因素有：①散列函数、②处理冲突的方法和③装填因子

    • 装填因子α = 表中记录数n / 散列表长度m

      • α越大（表越满），越容易发生冲突

排序

基本概念

• 内部排序算法的比较

  • 直接插入排序

    • √

    • O(1)

    • 最好：O(n)
      平均/最坏O(n^2)

  • 折半插入排序

    • O(n^2)

    • O(1)

    • √

  • 希尔排序

    • 最坏情况O(n^2)

    • O(1)

    • ×

    • 顺序存储

  • 冒泡排序

    • O(1)

    • 最好：O(n)
      平均/最坏O(n^2)

    • √

  • 快速排序

    • O(logn)
      最坏O(n)

    • 平均/最好O(nlogn)
      最坏O(n^2)

    • ×

  • 简单选择排序

    • O(1)

    • O(n^2)

    • ×

  • 堆排序

    • O(1)

    • ×

    • O(nlogn)

  • 归并排序

    • O(n)

    • √

    • O(nlogn)

  • 基数排序

    • O(r)

    • √

    • O(d(n+r))

• 内部排序算法的应用小结

  • n较小时，可采用直接插入排序或简单选择排序；当记录信息量较大时，选择简单选择排序

  • 元素基本有序，选择直接插入排序或冒泡排序

  • n较大时，选择O(nlogn)的算法

    • 快速排序平均时间最快

    • 堆排序所需辅助空间少于快排，
      且不会出现快排的最坏情况

    • 归并排序可以保证稳定性

  • 当n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlogn)的时间

  • 采用链表存储结构可以避免耗费大量移动记录的时间

内部排序

• 插入排序

  • 直接插入排序

  • 折半插入排序

  • 希尔排序

    • 当n在某个特点范围内，时间复杂度约为O(n^1.3)
      最坏情况下，时间复杂度为O(n^2)

• 交换排序

  • 冒泡排序

    • 最好情况：元素初始有序，O(n)
      最坏情况：元素初始逆序，O(n^2)
      平均情况：O(n^2)

  • 快速排序

    • 最坏情况：元素基本有序时，达到O(n^2)

    • 注意：
      Partition比较元素和枢轴时，条件为≤或≥
      一趟排序≠一次划分

    • 快速排序是内部排序中平均性能最优的排序算法

• 选择排序

  • 简单选择排序

  • 堆排序

    • 基本操作

      • 构造初始堆O(n)

        • 从后往前，对每个非叶结点进行一次下降调整
          （最后一个非叶结点即第floor[n/2]个结点）

      • 删除操作O(logn)

        • 用最后一个元素顶替被删除元素，进行一次下降调整

      • 插入操作O(logn)

        • 插入尾部，自下往上（上升）调整

    • 堆排序

      • 构造初始堆后，依次输出堆顶元素（删除）并重新调整为堆，经过n轮后全部输出。O(nlogn)

    • 注意：关键字比较次数的计算

      • 下降时：2个孩子算2次；1个孩子算1次
        上升时：算1次

• 归并排序

  • 对于N个元素的k路归并，排序的趟数m满足k^m = N，从而m = ceil(log(k,N))

  • 每一趟的时间复杂度为O(n)

• 基数排序

  • 位数d
    基数r（十进制为10）

  • 最高位优先（MSD）法

    • 先按高位分组，组内再按次高位分组，经过d躺分配后再依次收集。

  • 最低为优先（LSD）法（更好）

    • 进行d趟分配和收集，利用算法的稳定性，高权重分量相等时，不影响已按照低权重确定的相对位置。故每次分配后可以直接收集。

外部排序

• 多路归并排序

• 多路平衡归并与败者树

• 置换-选择排序
  （生成初始归并段）

• 最佳归并树