画布 1
数据结构
  绪论
    数据结构
      逻辑结构
        线性结构
          线性表、栈、队列、串、数组
        非线性结构
          集合、树、图
      物理（存储）结构
        顺序存储、链式存储、索引存储、散列存储
      数据的运算
    时间复杂度
      算法中所有语句的频度之和记为T(n)
    空间复杂度
      就地算法：空间复杂度为O(1)
  线性表
    逻辑结构
      具有相同的数据类型的n个数据元素的有限序列
      除第一个元素外，每个元素都有且仅有一个直接前驱
      除最后一个元素外，每个元素有且仅有一个直接后继
      表中元素有前后次序
    顺序存储
      逻辑相邻的元素，对应的物理存储位置也相邻
      顺序表插入、删除、查找的时间复杂度为O(n)
      可以随机存取（按序查找的时间复杂度为O(1)）
    链式存储
      头插法、尾插法时间复杂度O(n)
      按序、按指查找时间复杂度O(n)
      插入、删除结点时间复杂度O(1)
      双链表
        指向前驱结点的指针域
      循环链表
        最后一个结点的指针指回头结点
        判空条件：head->next==head
        从任意结点开始遍历链表
        只设置尾指针（head=r->next)
      循环双链表
        头结点的prior指针指向尾结点
      静态链表
        借助数组描述线性表的链式存储结构
        指针是相对地址
  栈和队列
    栈
      只允许一段（栈顶）进行插入或删除操作的线性表
      先进后出
      顺序栈
        声明一个栈，并初始化
          Elemtype stack[MaxSize];
          int top = -1;
        top指针指示当前栈顶元素的位置
          空栈时top=-1，满栈时top=MaxSize-1
          栈长top+1
          进栈时，stack.data[++top]=val
          出栈时，val=stack.data[top—]
        共享栈
          栈底位置不变，栈顶迎面生长
      链式存储（单链表）
        头插法
    队列
      在表的一端进行插入（入队）
      在表的另一端进行删除（出队）
      先进先出
      顺序存储
        队头指针front：指向队头元素（出队）
        队尾指针rear：指向队尾元素下一个位置（入队）
        循环队列
          牺牲一个单元区分队空和队满
            队满：(Q.rear+1)%MaxSize==Q.front
        空队：Q.front==Q.rear==0
        进队：Q.data[Q.rear]=val;Q.rear=(Q.rear+1)%MaxSize
        出队：val=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize
      链式存储
        带有头结点的单链表
      双端队列
        输出受限
          一端允许插入、删除，另一端只允许插入
          一端允许插入、删除，另一端只允许删除
    应用
      栈
        括号匹配
        表达式求值
          编译原理语法分析
        递归
      队列
        层次遍历
    特殊矩阵压缩存储
      对称矩阵
      三角矩阵
      三对角矩阵
      稀疏矩阵
        三元组表
        十字链表
  串
    基本概念
      串
        由零个或多个字符串组成的有限序列
      子串
        串中任意多个连续的字符组成的子序列
    模式匹配
      简单模式匹配
        时间复杂度O(nm)
      KMP算法
        时间复杂度O(n+m)
        不回退主串指针
        next数组
          next[j]：在子串的第j个字符与主串发生失配时，跳到子串的next[j]位置重新与主串当前位置进行比较
          next[1]=0:模式串的第一位与主串的第i位失配时，模式串右移一位，将模式串第一位与主串第i+1位进行匹配
          将a[next[i]]与a[i]比较计算next[i+1]
        nextval数组
          避免pj=p next[j]的情况
  排序
    内部排序
      插入排序
        基本思想：每次将一个待排序记录插入已排好序的子序列中
        直接插入排序
          稳定排序
          时间效率
            比较次数与移动次数取决于原始状态
            排序趟数与原始状态无关
          空间效率
            就地排序——哨兵
          适用于基本有序且数据量不大的排序表
        折半排序
          在寻找待排序记录在已排序子序列中的位置时，使用折半查找
          时间效率
            比较次数与原始状态无关
          稳定排序
        希尔排序
          基本思想：先将待排序表分割为若干个相隔增量d的子表，对各个子表直接插入
          最后一个增量d=1
          空间效率
            就地排序
          时间效率
            n在某个特定范围内
            最差
          不稳定排序
          仅适用于线性表为顺序存储的情况
      交换排序
        基本思想：根据序列中两个关键字的比较结果对换两个结果在序列中的位置
        冒泡排序
          基本思想：每次冒泡将剩余元素中最小（大）大元素放到最终位置
          空间复杂度
          时间效率
            最好情况下（有序）：排序趟数1，比较次数n-1，移动次数0
            最坏情况下（逆序）：排序趟数n-1，比较次数n(n-1)/2,每次比较后必须移动元素三次
          稳定排序
        快速排序
          基本思想
            在待排序子表中任取一个元素pivot作为枢轴
            通过一趟排序将待排序表分为大于pivot和小于pivot的两个子表
            对两个子表递归处理（直到每个子表只有一个元素或空为止）
          pivot选择
            一般选取子表中的第一个元素
            随机选择pivot可以提高算法效率
              将随机选取的pivot与第一个元素交换位置，不改变算法
          空间效率
            最好情况
            最坏情况：O(n)
            平均情况
          时间效率
            最坏情况——基本有序（逆序）
              每次划分的子表长度差最大（一个子表长度为0）
              退化为冒泡算法
            时间复杂度
          不稳定算法
      选择排序
        基本思想：每趟排序在待排序元素中选择关键字最小的元素
        简单选择排序
          空间复杂度：O(1)
          时间效率
            比较次数与原始状态无关：n(n-1)/2
            移动次数：0~3(n-1)
            时间复杂度
          不稳定排序
        堆排序
          大（小）根堆：根结点的值大（小）于其子结点的值
          建立初始堆
            从n/2结点（最后一个非叶结点）开始建堆
            若双亲结点值小于子结点值，双亲结点与子结点中较大值交换
            时间复杂度O(n)
          输出堆顶元素
            将堆中最后一个元素与堆顶元素交换，调整堆
            调整时间与树高有关，时间复杂度O(n)
          插入元素
            将新结点放入堆堆末端，再向上进行调整、
          时间复杂度O(1)
          空间效率
            建堆时间O(n)
            n-1次调整操作，每次调整时间复杂度O(h)
            时间复杂度
          不稳定排序
      归并排序
        基本思想：将n个长度为1的子表，两两合并组成新的有序子表
        Merge()归并子表
          辅助空间n个单元，空间复杂度O(n)（平均、最坏情况都是）
        MergeSort()合并
          一趟归并排序，调用n/2h（向上取整）次Merge
          每趟归并时间复杂度O(n)
          整个归并排序需要log2n趟，（与元素状态无关）
        稳定算法
        改进（与直接插入结合）
          先使用直接插入求得较长的有序子序列，然后两两归并
      基数排序
        比较关键字各位的大小
        最高为优先、最低位优先
        空间效率
          辅助存储空间为r（r个队列）
          空间复杂度O(r)
        时间效率
          d趟分配与收集
          一趟分配O(n)
          一趟收集O(r)
          时间复杂度O(d(n+r))（与原始状态无关）
        稳定排序
    外部排序
      内部排序
        工作过程
          先将大文件分为小段，再将所有小段依次调入内存进行内部排序
          使各个小段有序，形成归并段
        需要2n次磁盘读写（n为文件所占块数）
        置换-选择排序（生成更长的初始归并段）
          工作区WA
            初始为空，MINIMAX为最小值
            从FI中输入w个记录
            从中选取大于MINIMAX且关键字最小的记录，记为MINIMAX
              使用败者树实现
            将MINIMAX输出到FO中，从FI中读入新的记录
            直到在WA中选不出新的MINIMAX记录为止，得到一个初始归并段，输出归并段结束标志到FO
      外存读写
      内部归并
        工作过程
          从两个归并段分别读入一块，在内存中进行多路归并
          归并后的对象顺序放入输出缓冲区
          若缓冲区满则写回磁盘
          直到归并段中的每块都完成调入过内存进行归并
        败者树
          加快多路归并效率
          叶结点记录k个归并段在归并过程中当前参加比较大记录
          内部结点记录左右子树中的败者
          根结点记录最终胜者
          总比较次数
      最佳归并树（哈夫曼树变形）
        叶结点到根结点的路径长度为归并的趟数
        不满足严格k叉树情况
          添加长度为0的虚结点
            离根结点最远
            虚结点个数
          有u个多余结点
  查找
    基本概念
      查找表
        用于查找的数据集合
        数组或链表
      静态查找
        查找某个元素是否在查找表中
        查找符合某个条件的元素的属性
      动态查找
        需要插入删除某个元素
      平均查找长度
        概率✖️查找次数
    顺序查找
      一般线性表
        哨兵
      有序表
      平均成功查找长度相同
    折半查找
      适用于有序顺序表（顺序存储）
      二叉判定树
        平衡二叉树
        mid的选择要保持一致
    分块查找（索引顺序查找）
      块内元素无序
      块间有序
      平均查找长度
        索引查找和块内查找的平均长度之和
    B树、B+树
      B树（多路平衡查找树）
        性质
          树中每个结点最多有m棵子树
            至多有m-1个关键字
          若根结点不是终端结点，则至少有两棵子树
          除根结点外的所有非叶结点至少有m/2（向上取整）棵子树
            至少有m/2（向上取整）-1个关键字
          非叶结点
            关键字递增排列
            指针指向子树根结点
            指针Pi-1所指子树中所有结点的关键字均小于Ki
            指针Pi所指子树中所有结点的关键字均大于Ki
          所有叶子结点都出现在同一层次上，为外部结点
          平衡因子为0
          结点孩子个数为该结点关键字个数➕1
          子树个数等于关键字个数➕1
        B树高度（磁盘存取次数）
          不包括最后不带任何信息的叶子结点层
        操作
          查找
            在B树找结点（磁盘操作）
              将结点信息读入内存
            在结点内部找关键字（内存操作）
              在结点内采用顺序查找或折半查找
          插入
            定位：找到插入该关键字的最底层中某个非叶结点
            插入：若插入后结点内的关键字个数大于m-1时，需要分裂
              分裂
                从中间位置将关键字分为两部分
                  中间关键字插入父结点；
                    （若父结点关键字个数大于m-1，再对非结点进行分裂）
                  左部分关键字保留在原结点；
                  右部分关键字放到新结点；
          删除
            若被删关键字k不在终端结点
              先用k的前驱或后继替代k
              再将终端结点中的替代关键字删去（只保留一个）
            被删关键字k在终端结点
              若删去后关键字个数仍满足条件，直接删除
              兄弟够借
                若删去后的关键字个数小于要求，且该结点相邻兄弟结点个数大于最小要求
                  父子换位法，从父结点借关键字；父结点再从另一个子结点借一个关键字
              兄弟不够借
                若删去后的关键字个数小于要求，且该结点相邻兄弟结点个数等于最小要求
                  将该结点与其兄弟结点以及父结点合并
                  父结点关键字个数减一
                  若此时父结点关键字个数小于最小要求，则再对父结点及其兄弟结点合并
      B+树
        性质
          每个分支结点最多有m棵子树
          非叶根结点至少有两棵子树，其他每个分支结点至少有m/2（向上取整）棵子树
          结点子树个数与关键字个数相同
          叶结点
            所有叶结点包含全部关键字及指向相应记录的指针
            叶结点将关键字按大小顺序排列并且相邻叶结点按大小顺序相互链接起来
          所有分支结点（索引块）仅包含它的各个子结点（下一级索引块）中关键字最大值及指向该结点的指针
          非根内部结点的关键字个数范围为：m/2（向上取整）—— m
          根结点关键字个数范围为：1 —— m
        查找
          当查找到非叶结点上的关键字后，继续向下查找，直到查到叶结点上的关键字为止（获得记录的地址）
    散列表（哈希）
      散列函数
        把查找表中的关键字映射为该关键字对应的地址的函数
        构造方法
          直接定址法
            H(Key) = a * key + b
          除留余数法
            选取一个不大于散列表长度的质数p
            H(Key) = key % p
          数字分析法
            选取数码分布较为均匀的若干位作为散列地址
          平方取中法
            取关键字的平方值中间的几位
      处理冲突方法
        冲突：散列函数将两个以上的关键字映射到同一个地址
        开放定址法
          H = (H(key) + d) % m（d为递增序列）
          线性探测法
            d=1，2，3，4….
            将冲突关键字放到第一个空闲的单元中
            导致“聚集”
          平方探测法
            递增序列：
            m必须是一个可以表示为4k + 3 的素数
          再探测法
            递增序列：
            散列函数
            当出现冲突后利用第二个散列函数计算地址增量
          伪随机散列法
            d为伪随机数序列
          在删除元素时，使用逻辑删除。否则会截断冲突元素的查找
        链接法
          将同义词（冲突元素）放入一个单链表中
      散列查找及性能分析
        根据散列函数获得关键字地址
          若没有元素，则查找失败
          若记录与key值相同，则查找成功
          若记录与key不同，根据处理冲突方法计算“下一个散列地址”
        查找效率——装填因子
          表中记录数 / 散列表长度
          因子越大，发生冲突的可能性越大
  图
    定义
      连通图
        图中任意两个结点都是连通的
      连通分量
        无向图中的极大连通子图
      强连通图
        图中任意一对结点双向都有路径
      强连通分量
        有向图中极大强连通子图
          极大要求子图包含其所有的边
      生成树
        包含图中所有顶点的一个极小连通子图
          极小要求既保持连通性，又使得边数最少
      路径
        由顶点和相邻顶点序偶构成的边形成的序列
      简单路径
        路径序列中，顶点不重复出现的路径
      简单回路
        除起点、终点外，其余结点不重复出现的回路
    存储结构
      邻接矩阵
        无向图的邻接矩阵是一个对称矩阵
        对于无向图，邻接矩阵中第i行（或第i列）的非零元素是该结点的度
        对于有向图，第i行非零元素个数为i出度；第i列非零元素个数为结点i的入度
        A^n的元素A^n[i][j]表示为由顶点i到顶点j长度为n的路径数目
      邻接表
        图中每个结点建立一个单链表存储其边（出边）
        顶点表结点
        边表结点
      十字链表（有向图）
        弧结点
          尾域：表示弧尾顶点
          头域：表示弧头顶点
          链域hlink：弧头相同的下一条弧
          链域tlink：弧尾相同的下一条弧
        顶点结点
      邻接多重表（无向图）
        一条边在邻接多重表中只有一个结点
    图的遍历
      广度优先遍历（BFS）
        空间复杂度O(|V|)
        时间复杂度
          邻接表O(|V|+|E|)
          邻接矩阵O(|V^2|)
        求解单源最短路径问题
          广搜是按距离远近遍历图中顶点
        广度优先树
          邻接矩阵的广度优先生成树是唯一的
          邻接表的广度优先生成树是不唯一的
      深度优先遍历（DFS）
        递归遍历
        空间复杂度O(|V|)
        时间复杂度
          邻接表O(|V|+|E|)
          邻接矩阵O(|V^2|)
        深度优先生成树
          邻接矩阵的广度优先生成树是唯一的
          邻接表的广度优先生成树是不唯一的
          对于非连通图，会产生深度优先森林
      图的连通性
    图的应用
      最小生成树（MST）
        最小生成树不唯一，权值之和唯一
        Prim算法
          选择集合中的顶点到集合外的顶点的权值最小的路径
          时间复杂度O(|V|^2)
        Kruskal算法
          选择当前未被选取且权值最小的边，要求顶点在不同的连通分量
          时间复杂度O(|E|log|E|)
      最短路径
        Dijkatra算法
          单源最短路径问题
          时间复杂度O(|V|^2)
          不适用权值为负的图
        Floyd算法
          每对顶点间的最短路径
          N阶方阵序列
            A^(k)[i][j]：顶点i到顶点j，中间顶点序号不大于k的最短路径长度
            初始化：A^(-1)为原图
            A^(k)[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] < A^(k-1)[i][j]
          时间复杂度O(|V|^3)
      有向无环图
      拓扑排序
        AOV网
          顶点表示活动
          有向边<i,j>：活动I必须先于活动J
        构造算法
          从没有前驱（入度为0）的顶点开始
          删去该结点和它的所有出边
          重复
          最后仍存在有前驱的结点说明AOV图有环
        不能存在环
        每个顶点只出现一次
        时间复杂度O(|V|+|E|)
        逆拓扑排序
          从没有后继的顶点倒退
        若一个结点存在多条出边，则拓扑排序不唯一
      关键路径（带权有向图）
        AOE网
          顶点：事件
          有向边：活动
          权值：活动开销
          仅有一个入度为0的顶点
          活动可以并行执行
        关键路径：最大路径长度的路径
          完成整个工程的最短时间
        关键活动：关键路径上的所有活动
        事件最早发生时间ve(k)
          ve(0)=0
        事件最迟发生时间vl(k)
        活动最早开始时间
        活动最迟开始时间
        l(i)=e(i)的活动是关键活动
        关键路径不唯一
  树与二叉树
    基本术语
      结点的度
        一个结点孩子结点的个数
      树的深度
        树中结点的最大层数
      树的路径长度
        树根到每个结点的路径长度之和
    二叉树
      完全二叉树
        按层序编号后，一旦出现某个结点为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
      二叉树的遍历
        先序遍历
          根左右
        中序遍历
          左根右
        后序遍历
          左右根
        时间复杂度O(n)
        空间复杂度O(n)
          递归工作栈的栈深为树的深度
        非递归遍历算法
          使用栈
        层次遍历
          使用队列
      线索二叉树（物理结构）
        使用线索链找到直接前驱、直接后继
    树和森林
      树的表示
        双亲表示法
          一组连续空间
          伪指针指示双亲在数组中的位置
          求结点孩子时需要遍历整个结构
        孩子表示法
          每个结点的孩子用单链表连接起来（索引）
          寻找双亲复杂
        孩子兄弟表示法（二叉树）
          左指针指向第一个孩子结点
          右指针指向下一个兄弟结点
      树、森林、二叉树的转换
        树转换二叉树
          ”左孩子右兄弟“
        森林转换二叉树
          森林中每棵树转换为二叉树
          将不同树的根相互视为兄弟
      树的遍历
        先根遍历
          先访问根结点，再依次遍历根结点的每棵子树（每个根结点都会有多个子结点形成的子树）
          遍历序列与对应的二叉树的先序序列一致
        后根遍历
          先依次遍历根结点的每棵子树，再访问根结点
          遍历序列与对应的二叉树的中序序列一致
        层次遍历
      森林的遍历
        先序遍历森林
          访问森林中第一棵树的根结点
          先序遍历第一棵树中根结点的子树森林
          先序遍历除去第一棵树后剩余树构成的森林
        中序遍历森林
          中序遍历第一棵树的根结点的子树森林
          访问第一棵树的根结点
          中序遍历除去第一棵树后剩余树构成的森林
    并查集（新增考点）
      逻辑结构——集合
        将若干个元素划分为互不相交的子集
        用树表示一个子集的元素（双亲表示法）
      初始化
        数组元素初始化为-1
      查
        一个元素到底属于那个子集
        优化查操作（压缩路径）
          每次查操作先找到x所属根结点，再将路径上所有结点都直接挂在根结点下面
          时间复杂度O(a(n))
      并
        将两个子集合并为一个集合
        优化（降低树的高度）
          将小树合并到大树下面
          用s[root]的值的绝对值表示为树的结点个数
          不优化并操作，时间复杂度O(n)
          优化并操作，时间复杂度O(log2 n)
      应用
        判断图的连通分量数
          将有边相连的两个顶点并为一个集合
        判断图是否有环
          在同一个集合的两个顶点还有一条边
        Kruskal算法
          判断两个结点是否已经连通（在同一子集中）
    二叉排序树
      二叉排序树的删除
        右子树空，用左子树填补
        左子树空，用右子树填补
        左右子树均不为空，在右子树上找中序第一个子女（右子树上最小的元素）
      评价查找长度O(log2n)
    平衡二叉树
      平衡因子：左子树高度—右子树高度
      插入
        LL
          A的左孩子B成为A的根结点
          A成为B的右子树的根结点
          B的右子树成为A的左子树
        RR
          A的右孩子B成为A的根结点
          A成为B的左子树的根结点
          B的左子树成为A的右子树
        LR
          两次旋转
            A的左孩子B的右子树根结点与B转换
            C再与A转换
        RL
          两次旋转
            A的右孩子B的左子树（导致失衡的子树）根结点C与B转换
            C与A转换
    红黑树（新增考点）
      优点：查找等操作时间复杂度与AVL相同；插入，删除无需频繁调整树的形态，可在常数级时间内完成
      定义
        二叉排序树
        有向上寻找双亲结点的父指针
        用红色颜色代替AVL中的平衡因子
        每个结点或是红色，或是黑色的
        根结点是黑色的
        叶结点（外部结点、NULL结点、失败结点）均是黑色的
        不存在两个相邻的红结点（红结点的父结点和孩子结点均是黑色的）
        对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同
          黑高bh：从某个节点出发（不含该结点）到达任一空结点的路径上黑结点总数
      性质
        从根结点到叶结点的最长路径不大于最短路径的2倍
          左右子树高度差不超过2倍
        有n个内部结点的红黑树高度h小于等于2log2（n+1）
      查找操作
        查找到一个空叶结点则查找失败
      插入操作
        确定插入位置（二叉排序树插入）
          新结点是根——染为黑色
          新结点非根——染为红色
            若不满足红黑树特性，需要调整
        调整
          叔叔结点（父结点的兄弟）为黑色
            LL型：右单旋，父换爷+染色
            RR型：左单旋，父换爷＋染色
            LR型：左、右双旋，儿换爷＋染色（儿结点、爷结点）
            RL型：右、左双旋，儿换爷＋染色
          叔叔结点为红色（染色＋变新）
            叔父爷染色，爷变为新结点
              此时爷结点有可能继续破坏红黑树性质，需要进一步调整
      删除操作
    哈夫曼树
      构造
        选取权值最小的两个结点
        将相加后的结点视为一个新结点
        结点总数2n-1
        不存在度为0的结点
      哈夫曼编码
        前缀不相同
        使用哈夫曼树
        判断是否为哈夫曼编码
          一个编码的前缀是否为另一个字符
      哈夫曼树不唯一，但WPL相同且为最优