数据结构与算法
线性表
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 顺序表-数组 | 用一段连续的内存空间存储元素 | 随机访问快速，节省空间 | 插入删除需要移动大量元素，固定大小不易扩展 | 频繁随机访问，元素数量相对固定 |
| 单链表-不带头节点 | 每个节点包含数据和指向下一个节点的指针 | 插入删除操作高效，动态分配内存 | 随机访问慢，需要额外的指针空间 | 频繁插入删除，不需要随机访问 |
| 单链表-带头节点 | 在链表开头增加一个空的头节点 | 简化插入和删除操作，统一了空表和非空表的操作 | 额外的头节点增加了内存开销 | 需要简化链表操作的场合 |
| 双链表-不带头节点 | 每个节点有两个指针，分别指向前一个和后一个节点 | 可以双向遍历，删除节点更方便 | 需要更多的存储空间，操作稍微复杂 | 需要双向遍历或频繁在任意位置插入删除 |
| 双链表-带头节点 | 在双链表的基础上增加头节点，简化了边界条件的处理，操作更统一 | 简化了边界条件的处理，操作更统一 | 额外的头节点增加了内存开销 | 需要简化双链表操作的场合 |
| 循环单链表 | 最后一个节点指向第一个节点形成环 | 可以从任意节点遍历整个链表，方便实现某些算法 | 判断遍历结束的条件稍复杂 | 需要循环处理数据的场合，如约瑟夫环问题 |
| 循环双链表 | 首尾相连的双向链表 | 结合了循环链表和双链表的优点 | 结构较复杂，操作需要考虑的情况更多 | 需要双向循环遍历的应用 |
| 静态链表 | 用数组实现的链表，数组元素中包含数据和下一元素的数组下标 | 避免了动态分配内存，可以在不支持指针的语言中实现链表 | 大小固定，效率比动态链表低 | 内存分配受限或不支持指针的环境 |
栈和队列
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 栈-顺序表 | 用数组实现的栈，在数组一端进行push和pop操作 | 实现简单，操作效率高 | 大小固定，可能会溢出 | 元素数量可预测，需要频繁的入栈出栈操作 |
| 栈-链表-带头节点 | 用带头节点的链表实现栈，在链表头部进行操作 | 大小动态变化，不会溢出 | 需要额外的空间存储指针 | 元素数量不可预测，内存空间充足 |
| 栈-链表-不带头节点 | 用不带头节点的链表实现栈 | 节省了头节点的空间，操作稍简单 | 需要特殊处理空栈情况 | 对空间要求严格，且栈操作频繁 |
| 队列-顺序表 | 用数组实现的队列，一端入队，另一端出队 | 实现简单，随机访问快 | 出队时需要移动元素，效率低 | 元素数量固定，需要频繁随机访问 |
| 队列-链表-带头节点 | 用带头节点的链表实现队列 | 入队出队操作效率高，大小动态变化 | 需要额外的空间存储指针 | 元素数量变化大，频繁入队出队 |
| 队列-链表-不带头节点 | 用不带头节点的链表实现队列 | 节省了头节点的空间 | 需要特殊处理空队列情况 | 对空间要求严格，队列操作频繁 |
| 队列-顺序表-循环队列 | 在顺序队列的基础上，将队列头尾相连 | 克服了顺序队列”假溢出”的问题，空间利用率高 | 判断队列空或满的条件稍复杂 | 频繁入队出队，且空间受限 |
| 栈-括号匹配-顺序表 | 使用栈实现括号匹配算法 | 实现简单，直观 | 只能处理括号匹配问题 | 编译器的语法检查，文本编辑器的括号匹配 |
| 栈-表达式计算-顺序表 | 使用栈实现算术表达式的计算 | 可以处理复杂的表达式，包括括号和运算符优先级 | 实现相对复杂 | 计算器应用，编译器的表达式求值 |
| 队列-双端队列 | 两端都可以进行入队和出队操作的队列 | 灵活性高，可以在两端进行操作 | 实现相对复杂 | 需要在队列两端频繁操作的场景 |
| 队列-层次遍历 | 使用队列实现树或图的层次遍历 | 能够按层次顺序访问节点 | 需要额外的空间存储队列 | 树或图的层次遍历，如二叉树的层次遍历 |
数组
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 数组-存储结构 | 在内存中连续存储的同类型数据元素集合 | 支持随机访问，存取速度快 | 插入删除需要移动元素，大小固定 | 需要频繁随机访问，元素数量固定的场景 |
| 压缩存储-对称矩阵 | 只存储对称矩阵的上（或下）三角部分 | 节省存储空间 | 访问元素需要进行下标变换 | 存储大型对称矩阵，如相关性矩阵 |
| 压缩存储-三角矩阵 | 只存储上（或下）三角部分和对角线 | 节省存储空间 | 访问元素需要进行下标变换 | 存储大型三角矩阵，如某些数学计算 |
| 压缩存储-三对角矩阵 | 只存储主对角线及其上下两条对角线 | 大幅节省存储空间 | 访问元素较复杂 | 存储大型三对角矩阵，如有限元分析 |
| 稀疏矩阵-三元组 | 只存储非零元素的行列值和数值 | 节省存储空间，适合稀疏矩阵 | 随机访问速度慢 | 存储大型稀疏矩阵，如社交网络邻接矩阵 |
串
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 朴素模式匹配 | 逐个比较主串和模式串的字符 | 实现简单，对小规模匹配效率尚可 | 时间复杂度高，最坏情况下为O(mn) | 短文本匹配，模式串较短时 |
| KMP算法 | 利用已匹配信息加速匹配过程 | 时间复杂度为O(m+n)，效率高 | 实现相对复杂，需要额外空间存储next数组 | 长文本匹配，需要多次匹配同一模式串时 |
树结构
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 二叉树-链式存储 | 每个节点包含数据、左右子节点指针 | 插入、删除操作方便，适合动态变化 | 需要额外的指针空间 | 经常进行插入、删除操作的树结构 |
| 二叉排序树-链式存储 | 左子树所有节点值小于根节点，右子树大于根节点 | 查找、插入、删除的平均时间复杂度为O(logn) | 可能退化为链表，最坏时间复杂度为O(n) | 需要动态插入、删除、查找的有序数据集 |
| 哈夫曼树-顺序存储 | 带权路径长度最小的二叉树 | 可以用于数据压缩，最优前缀编码 | 构建过程相对复杂 | 数据压缩，字符编码 |
| 线索二叉树 | 利用空指针存储前驱后继信息 | 加速了树的遍历过程 | 结构较复杂，修改操作麻烦 | 需要频繁遍历的二叉树 |
| AVL平衡二叉树 | 任何节点的左右子树高度差不超过1 | 保证了查找、插入、删除的时间复杂度为O(logn) | 插入删除时可能需要旋转操作，实现复杂 | 需要保证最坏情况下查找效率的场景 |
| 树存储结构-双亲 | 每个节点存储其父节点的位置 | 寻找父节点操作迅速 | 寻找子节点较慢 | 经常需要查找父节点的应用 |
| 树存储结构-孩子 | 每个节点存储所有子节点的链表 | 寻找子节点操作迅速 | 寻找父节点较慢，存储空间较大 | 经常需要查找子节点的应用 |
| 树存储结构-孩子双亲 | 结合孩子表示法和双亲表示法 | 能够快速找到父节点和子节点 | 存储空间开销大 | 需要同时快速查找父节点和子节点的场景 |
图结构
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 存储结构-邻接矩阵 | 用二维数组表示顶点间的连接关系 | 直观，易于理解和实现，快速判断两点是否相连 | 空间复杂度高O(n^2)，稀疏图浪费空间 | 稠密图，需要快速判断顶点间连接关系 |
| 存储结构-邻接链表 | 每个顶点有一个链表存储其邻接顶点 | 节省空间，适合稀疏图 | 判断两点是否相连较慢 | 稀疏图，需要节省空间 |
| 广度优先搜索-BFS | 逐层遍历图中顶点 | 找到的路径是最短路径 | 需要额外的队列空间 | 最短路径问题，层次遍历 |
| 深度优先搜索-DFS | 尽可能深地搜索图的分支 | 内存占用小，实现简单 | 可能陷入深层次的结构中 | 拓扑排序，寻找连通分量 |
| Prim(普里姆)算法 | 构建最小生成树的贪心算法 | 适用于稠密图 | 不适合分布式系统 | 网络设计，电路设计 |
| Kruskal(克鲁斯卡尔)算法 | 另一种构建最小生成树的贪心算法 | 适用于稀疏图 | 需要对边进行排序 | 网络设计，尤其是稀疏网络 |
| Dijkstra(迪杰斯特拉)算法 | 寻找单源最短路径的算法 | 能找到最短路径 | 不适用于负权边 | 导航系统，网络路由 |
| Floyd(佛洛依德)算法 | 寻找所有点对最短路径的算法 | 可以处理负权边（非负权回路） | 时间复杂度高O(n^3) | 需要所有顶点间最短路径的场景 |
| 拓扑排序-栈 | 将有向无环图的顶点排成一个线性序列 | 可以检测图中是否有环 | 只适用于有向无环图 | 任务调度，编译器符号依赖分析 |
| 关键路径 | 在带权有向无环图中寻找最长路径 | 可以找出项目中的关键任务 | 计算复杂度较高 | 项目管理，工程进度 |
查找
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 顺序查找-乱序表 | 从表的一端开始逐个比较元素 | 实现简单，适用于任何顺序表 | 平均时间复杂度O(n)，效率低 | 小规模数据，无序数据集 |
| 顺序查找-有序表 | 在有序表中从一端开始比较，遇到大于待查元素则停止 | 可能在中途停止，平均性能优于乱序表 | 仍需要O(n)时间复杂度 | 小规模有序数据集 |
| 折半查找 | 在有序表中不断折半缩小查找范围 | 时间复杂度O(log n)，效率高 | 要求数据有序存储 | 大规模有序数据集，静态查找 |
| B树 | 多路平衡查找树 | 适合外部存储，I/O次数少 | 实现复杂 | 数据库索引，文件系统 |
| B+树 | B树的变体，非叶节点只存储键 | 范围查询效率高，叶节点相连 | 实现复杂 | 数据库索引，文件系统 |
| 红黑树 | 自平衡二叉查找树 | 保证最坏情况下的时间复杂度O(log n) | 实现复杂，需要颜色标记 | 需要频繁插入删除的动态查找表 |
| 哈希表-拉链法 | 通过哈希函数将键映射到数组，冲突通过链表解决 | 平均查找时间O(1) | 可能出现哈希冲突，需要额外空间 | 需要快速查找、插入、删除的场景 |
| 哈希表-开放定址法 | 冲突发生时，尝试其他位置 | 节省空间，无需链表 | 可能出现聚集现象 | 内存受限，数据量可预测的情况 |
排序
| 算法或数据结构名 | 说明 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 直接插入排序 | 将一个记录插入到已排序的有序表中 | 实现简单，对小规模数据很有效 | 平均时间复杂度O(n^2) | 小规模数据，基本有序的数据 |
| 折半插入排序 | 在插入排序的基础上使用折半查找 | 比直接插入排序减少了关键字比较次数 | 平均时间复杂度仍为O(n^2) | 小规模数据，需要减少比较次数 |
| 希尔排序 | 将整个序列分为几个子序列分别进行插入排序 | 对中等规模数据效率较高 | 不稳定排序，最坏时间复杂度难以确定 | 中等规模数据，对稳定性不作要求 |
| 冒泡排序 | 相邻元素比较交换，每轮确定一个最大元素 | 实现简单，稳定 | 平均时间复杂度O(n^2)，效率低 | 小规模数据，教学演示 |
| 快速排序 | 选择基准元素，将序列分为两部分，递归排序 | 平均时间复杂度O(nlogn)，原地排序 | 最坏情况下时间复杂度O(n^2)，不稳定 | 大规模数据，要求高效率 |
| 简单选择排序 | 每次从未排序序列中选择最小元素 | 交换次数少 | 平均时间复杂度O(n^2) | 小规模数据，交换成本高的情况 |
| 堆排序 | 利用堆的性质进行排序 | 时间复杂度O(nlogn)，空间复杂度O(1) | 不稳定排序 | 大规模数据，要求空间复杂度低 |
| 归并排序 | 将序列分成子序列，排序后合并 | 稳定排序，时间复杂度O(nlogn) | 需要额外空间O(n) | 大规模数据，要求稳定排序 |
| 基数排序 | 按位数字或字符进行排序 | 可以避免元素间的比较，适合数字和字符串 | 需要额外空间，依赖数据分布 | 整数、字符串排序，数据范围较小 |
- 数据结构与算法
线性表
顺序表-数组 单链表-不带头节点 单链表-带头节点 双链表-不带头节点 双链表-带头节点 循环单链表 循环双链表 静态链表
栈和队列
栈-顺序表 栈-链表-带头节点 栈-链表-不带头节点 队列-顺序表 队列-链表-带头节点 队列-链表-不带头结点 队列-顺序表-循环队列 栈-括号匹配-顺序表 栈-表达式计算-顺序表 队列-双端队列 队列-层次遍历
数组
数组-存储结构 压缩存储-对称矩阵 压缩存储-三角矩阵 压缩存在-三对角矩阵 稀疏矩阵-三元组
串
朴素模式匹配 KMP算法
树结构
二叉树-链式存储 二叉排序树-链式存储 哈夫曼树-顺序存储 线索二叉树 AVL 平衡二叉树 树存储结构-双亲 树存储结构-孩子 树存储结构-孩子双亲
图结构
存储结构-邻接矩阵 存储结构-邻接链表 广度优先搜索-BFS 深度优先搜索-DFS Prim(普里姆)算法 Kruskal(克鲁斯卡尔)算法 Dijkstra(迪杰斯特拉)算法 Floyd(佛洛依德)算法 拓扑排序-栈 关键路径
查找
顺序查找-乱序表 顺序查找-有序表 折半查找 B树 B+树 红黑树 哈希表-拉链法 哈希表-开放定址法
排序
直接插入排序 折半插入排序 希尔排序 冒泡排序 快速排序 简单选择排序 堆排序 归并排序 基数排序