数据结构和算法重点概念

来自：小麦

数据结构

数组（Array）：
- 逻辑结构：线性，元素类型相同。
- 存储方式：一段连续内存，支持 O(1) 随机访问。
- 更新成本：插入/删除需整体搬移元素，平均 O(n)；容量固定，扩容需重新分配与拷贝。
- 适用场景：元素数量可预估、以读为主或需频繁按下标访问的场合，如矩阵运算、哈希表桶、静态查找表。
链表（Linked List）：
- 逻辑结构：线性，通过节点指针维持次序。
- 存储方式：内存非连续，节点“见缝插针”。
- 更新成本：已知前驱节点时插入/删除 O(1)；访问必须顺序遍历，O(n)。
- 适用场景：数据量动态变化大、以插入/删除为主且不需随机访问的场合，如 LRU 缓存、多项式表示、内存池管理。
栈（Stack）：
- 逻辑结构：LIFO 线性表，仅栈顶可进出。
- 核心操作：push / pop，时间复杂度均为 O(1)。
- 适用场景：函数调用链、表达式求值、括号匹配、深度优先搜索（DFS）、浏览器历史记录。
队列（Queue）：
- 逻辑结构：FIFO 线性表，队尾入、队头出。
- 核心操作：enqueue / dequeue，时间复杂度均为 O(1)。
- 适用场景：任务调度、消息缓冲、广度优先搜索（BFS）、打印队列、生产者-消费者模型。
字符串（String）：
- 逻辑结构：元素为字符的线性序列，通常以数组或链表实现。
- 常见操作：模式匹配（KMP、BM）、子串查找、前缀树索引。
- 适用场景：文本处理、编译器词法分析、搜索引擎、正则引擎。
树（Tree）：
- 逻辑结构：非线性层次结构，每个节点最多两个子树。
- 重要变型：BST（搜索）、AVL/红黑树（平衡）、堆（优先队列）、Trie（前缀树）。
- 遍历方式：前序、中序、后序、层序，时间 O(n)。
- 适用场景：
  - 搜索与排序：二叉搜索树、堆排序
  - 表达式解析：语法树
  - 哈夫曼编码：最优前缀码
  - 索引结构：B+/B- 树在数据库与文件系统
图（Graph）：
- 逻辑结构：非线性，顶点+边，可带权/有向。
- 存储方式：邻接矩阵 O(V²)、邻接表 O(V+E)。
- 核心算法：
  - 遍历：DFS、BFS
  - 最短路径：Dijkstra、Floyd-Warshall、A*
  - 最小生成树：Prim、Kruskal
  - 拓扑排序、关键路径、最大流
- 适用场景：社交网络、路径规划、电路布线、依赖解析、推荐系统。

算法

算法的分类：

排序算法：
- 如快速排序、归并排序、堆排序、插入排序等，需理解其原理、时间复杂度及稳定性。
查找算法：
- 包括顺序查找、二分查找、哈希查找等，重点理解二分查找的前提条件和哈希冲突的处理。
图算法与树算法：
- 如深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径（Dijkstra）、最小生成树（Prim/Kruskal）以及二叉树的遍历（前序、中序、后序、层序）

算法复杂度（大 O 表示法）：

时间复杂度：
- 它描述了算法执行所需的时间随输入规模增长的变化趋势。
- O(1)（常数阶）< O(log n)（对数阶）< O(n)（线性阶）< O(n log n)（线性对数阶）< O(n²)（平方阶） < O(2ⁿ)（指数阶）
空间复杂度：
- 它衡量的是算法在运行过程中临时占用存储空间大小的增长情况。同样用大O符号表示，关注的是随着输入规模增加，算法所需的额外内存空间的变化趋势。