Data Structure

线性表

  1. 顺序表
  2. 线性链表：设头结点
  3. 循环链表：有时使用尾指针代替头指针，以利于链表的合并
  4. 双向链表

栈和队列

  1. 栈：一般空栈以 top == base 表示，栈不为空时 top 指向栈顶的下一元素，类似 [begin, end)，真正的栈顶元素为 *(top - 1)。
  2. 栈的应用示例：数制转换、括号匹配检查、行编辑程序、迷宫求解、表达式求值、Hanoi 塔问题
  3. 队列：单链队列、循环队列（(Q.rear + 1) % MAXQSIZE == Q.front 表示队满）

串

  1. 顺序存储
  2. 堆分配存储
  3. 块链存储
  4. 常见操作
    • 串联接 concat
    • 求子串 substring
    • 模式匹配 index: Naive –> KMP –> BoyerMoore

数组和广义表

  1. 稀疏矩阵的存储结构
    • 三元组顺序表：转置时附设每一列非零元的个数 num[], 每一列第一个非零元在转置矩阵的位置 cpot[]，可降低时间复杂度。
    • 行逻辑链接的顺序表（矩阵相乘）：将三元组顺序表中的 cpot[] 固定到存储结构中 rpos[]，以便于存储任意行的非零元。
    • 十字链表（矩阵相加）：三元组基础上加入指向同一行的下一个元素的指针 right 和指向同一列的下一个元素的指针 down。
  2. 广义表：由表头（可能是原子或列表）和表尾（只能是列表）组成。
    • 头尾链表存储
    • 扩展线性链表
  3. 广义表的递归算法
    • 求广义表深度
    • 复制广义表
    • 构建广义表

树和二叉树

  1. 二叉树的性质
    • 第 i 层至多 2^(i-1) 个结点
    • 深度为 k 的二叉树至多 (2^k) - 1 个结点
    • 终端结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1
    • 具有 n 个结点的完全二叉树深度为 floor(log2n) + 1
    • 对完全二叉树结点 i，左孩子为 2i，右孩子为 2i + 1
  2. 二叉树的存储结构：顺序存储、链式存储结构
  3. 二叉树的遍历：前根序、中根序、后根序、层次遍历
  4. 线索二叉树：利用叶子结点左右孩子为空的特性，让其指向前驱或后继结点，以便快速访问某个结点的前驱或后继。
  5. 树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法（即二叉树表示法，左孩子右兄弟）
  6. 森林的存储结构：孩子兄弟表示法，树的二叉树表示法根的右子树为空，利用这个特性，让森林里的树的根以右子树的形式联结在一起。
  7. 树与等价问题：并查集 Merge-Find-Set (双亲表示法)
  8. 哈夫曼树（最优二叉树）

图

  1. 概念
    • 网：带权的图
    • 完全图具有 n(n-1)/2 条边，有向完全图具有 n(n-1) 条弧。
    • 简单路径：顶点不重复的路径
    • 连通分量：无向图中的极大连通子图
    • 强连通分量：有向图中的极大连接子图
    • 连通图生成树只一个极小连接子图，包含了所能顶点，但只有足以构成一棵树的 n-1 条边
    • 关节点：删除顶点及关联的边后可将图的一个连通分量分割成两个以上的连通分量
  2. 图的存储结构
    • 数组表示法（邻接矩阵）
    • 邻接链表
    • 十字链表
    • 邻接多重表（适用于无向图）
  3. 图的遍历：深度优先、层次优先
  4. 生成森林的存储结构：孩子兄弟链表
  5. 强连接分量（基于 DFS）
    • kosaraju：原图与转置具有相同的连通分量
    • tarjan：v(i, j)，i 被访问的时间，j 可回溯的最早的时间，如果 i == j 则 v 为关节点。
  6. 最小生成树：prim 或 kruskal 算法
  7. 有向无环图
    • 拓扑排序：由集合上的一个偏序得到该集合上的一个全序的过程。

      当图无环时可以利用深度优先遍历实现，最先退出 DFS 的顶点是出度为0的顶点，是拓扑排序的最后一个顶点。

    • 关键路径（AOE-网）：在拓扑排序的基础上求得 ve（活动的最早开始时间） 和 vl（活动的最迟开始时间），若 ve == vl 则为关键节点。
  8. 带权最短路径
    • dijsktra：按路径长度递增的次序产生最短路径的算法
    • floyed：任意两点之间进行 n 次试探

查找

  1. 表态查找表
    • 顺序查找表：设置哨兵，由后往前查找，可避免越界及下标范围有效性检查。
    • 折半查找：等概率有序表的查找
    • 次优查找树：基于概念有序表的查找，寻找根结点使左右子树带权路径长度差最小。
    • 索引顺序表：分块查找，对顺序查找进行改进，建立一个有序的索引表，根据索引指引到块内进行查找，当每块元素个数为 sqrt(n) 时 ASL 最小。
  2. 动态查找表
    • 二叉排序树：当插入的关键字有序蜕变成单支树。
    • 平衡二叉树（AVL）：左右子树的高度差不超过1。
    • 红黑树：相对 AVL 来说，减少二叉树调整的数量。
    • B树：平衡的多路查找树，m 阶的B树，根结点至少 2 棵子树，非终端结点至少 ceil(m/2) 棵子树，结点信息为 (n, A0, K1, A1…Kn, An)。

      存在 N + 1 >= 2 x ceil(m / 2)^(l - 1)。

    • B+树：叶子结点包含了全部信息，而非终端节点看起来就像索引表只存储关键字。
    • 键树（数字查找树）：孩子兄弟表示法、树的多重链表（Trie树）
  3. 哈希表
    • 构造方法：直接定址法、平方取中法、数字分析法、折叠法、除留余数法、随机数法
    • 处理冲突：开放定址法、再哈希法、链地址法、建立溢出区

内部排序

排序方法 平均时间 最坏情况 辅助存储
简单排序 O(n^2) O(n^2) O(1)
快速排序 O(nlogn) O(n^2) O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)

n 记录数， d 关键字数，rd 关键字的取值范围，如十进制 0~9 即 rd = 10

  1. 插入排序
    • 直接插入排序
    • 折半插入排序：减少关键字比较次数
    • 2-路插入排序：减少记录移动的次数
    • 表插入排序：减少移动记录
    • 希尔排序：插入排序在基本有序的情况效能更高，希尔排序利用这个特点，先使基本有序再对全体记录进行一次插入排序。
  2. 交换排序
    • 冒泡排序：逐个交换，使最大或最小值下沉到最后。
    • 快速排序：将待排记录分割成两部分，一部分比割点小，一部分比割点大，如此递归下去。
  3. 选择排序
    • 简单选择排序：记录移动的次数少，但仍要较多的比较次数，不像冒泡排序发现没有交换就可以提前结束无需进行后续冒泡过程。比如记录已经有序，冒泡只要走一趟就知道不需要排序了，而选择排序仍要把流程走完。
    • 树形选择排序：需要太多的空间来存储树结构。
    • 堆排序：逐步调整堆的过程使整棵逐步有序的过程，每趟调整 log(n)，需要 n-1 趟。
  4. 归并排序：合并有序表的过程。
  5. 基数排序：MSD、LSD