数据结构与算法是计算机科学的核心基础，数据结构负责组织和存储数据，算法负责定义处理数据的步骤，二者结合决定了程序的效率与性能。

一、 基础概念

1. 核心目标

   • 时间复杂度：衡量算法执行时间随数据规模增长的变化趋势，用大 O 记法表示（如 \(O(1)\)、\(O(n)\)、\(O(\log n)\)、\(O(n^2)\)）。
   • 空间复杂度：衡量算法占用内存空间随数据规模增长的变化趋势。
   • 算法的特性：输入、输出、有穷性、确定性、可行性。
   • 算法的评价指标：正确性、可读性、健壮性、时间效率与空间效率。

2. 复杂度分析方法

   • 只关注最高阶项，忽略常数项和低阶项。
   • 常见复杂度排序：\(O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)\)

二、 线性数据结构

线性结构的特点是数据元素之间存在一对一的线性关系，可分为顺序存储和链式存储。

1. 数组（Array）

   • 存储：连续的内存空间，相同数据类型。
   • 操作：随机访问 \(O(1)\)；插入、删除 \(O(n)\)（需移动元素）。
   • 优缺点：查询快，增删慢，长度固定（静态数组）。

2. 链表（Linked List）

   • 分类：单链表、双链表、循环链表。
   • 存储：节点 + 指针，非连续内存空间。
   • 操作：访问 \(O(n)\)；插入、删除 \(O(1)\)（已知前驱 / 后继节点）。
   • 优缺点：增删快，查询慢，灵活利用内存，额外存储指针开销。

3. 栈（Stack）

   • 特性：后进先出（LIFO）。
   • 实现：数组实现（顺序栈）、链表实现（链式栈）。
   • 核心操作：入栈 push()、出栈 pop()、查看栈顶 peek()，均为 \(O(1)\)。
   • 应用：括号匹配、表达式求值、函数调用栈、回溯算法。

4. 队列（Queue）

   • 特性：先进先出（FIFO）。
   • 分类与实现：
     • 普通队列：数组 / 链表实现，需处理假溢出问题。
     • 循环队列：数组实现，通过取模解决假溢出，核心操作 \(O(1)\)。
     • 双端队列（Deque）：两端均可入队出队，支持栈和队列的功能。
   • 应用：任务调度、广度优先搜索（BFS）、消息队列。

三、 非线性数据结构

非线性结构的特点是数据元素之间存在一对多或多对多的关系。

1. 树（Tree）

   • 基本概念：根节点、叶子节点、父节点 / 子节点、高度 / 深度、层数、度。

   • 核心性质：n 个节点的树有 n-1 条边；子树不相交。

   • 二叉树

     • 定义：每个节点最多有两个子节点（左子树、右子树）。
     • 性质：
       1. 第 i 层最多有 \(2^{i-1}\) 个节点。
       2. 深度为 k 的二叉树最多有 \(2^k -1\) 个节点。
       3. 叶子节点数 = 度为 2 的节点数 + 1。
     • 特殊二叉树：
       • 满二叉树：所有层节点数都达到最大值。
       • 完全二叉树：除最后一层外，其他层节点数满，最后一层节点靠左排列。
     • 存储：
       • 顺序存储：适合完全二叉树，父节点索引 i，左孩子 \(2i+1\)，右孩子 \(2i+2\)。
       • 链式存储：每个节点包含数据、左指针、右指针。
     • 遍历（核心操作，时间复杂度 \(O(n)\)）：
       • 深度优先遍历（DFS）：前序遍历（根 - 左 - 右）、中序遍历（左 - 根 - 右）、后序遍历（左 - 右 - 根）。
       • 广度优先遍历（BFS）：层序遍历，按层次从上到下、从左到右访问节点。

   • 二叉搜索树（BST）

     • 特性：左子树所有节点值 <根节点值；右子树所有节点值> 根节点值；左右子树也是 BST。
     • 操作：查询、插入、删除 \(O(\log n)\)（平衡时），最坏 \(O(n)\)（退化为链表）。
     • 应用：有序数据的查询与维护。

   • 平衡二叉树

     • 定义：左右子树的高度差绝对值不超过 1，且左右子树都是平衡二叉树。
     • 常见类型：
       • AVL 树：严格平衡，通过旋转（左旋、右旋、左右旋、右左旋）维持平衡，查询效率高。
       • 红黑树：近似平衡，通过颜色标记和旋转维持平衡，插入删除效率更高，是 Java TreeMap、C++ map 的底层实现。

   • 堆（Heap）

     • 特性：完全二叉树；分为大顶堆（父节点 ≥ 子节点）、小顶堆（父节点 ≤ 子节点）。
     • 操作：插入 \(O(\log n)\)、删除堆顶 \(O(\log n)\)、建堆 \(O(n)\)。
     • 应用：优先队列、堆排序、Top K 问题。

   • 哈夫曼树

     • 定义：带权路径长度最短的二叉树（最优二叉树）。
     • 构建：每次选两个权值最小的节点合并为新节点。
     • 应用：哈夫曼编码，用于数据压缩。

2. 图（Graph）

   • 基本概念：顶点（V）、边（E）；分为有向图、无向图；加权图、无权图。
   • 存储方式：
     • 邻接矩阵：二维数组，\(g[i][j]\) 表示顶点 i 和 j 的关系，空间复杂度 \(O(V^2)\)，适合稠密图。
     • 邻接表：数组 + 链表，每个顶点对应一个链表存储相邻顶点，空间复杂度 \(O(V+E)\)，适合稀疏图。
   • 图的遍历（时间复杂度 \(O(V+E)\)）：
     • 深度优先遍历（DFS）：递归 / 栈实现，优先访问子节点，回溯后访问其他邻接节点。
     • 广度优先遍历（BFS）：队列实现，按层次访问邻接节点。
   • 核心算法：
     • 最短路径：Dijkstra 算法（单源最短路径，无负权边）、Floyd-Warshall 算法（多源最短路径）、Bellman-Ford 算法（处理负权边）。
     • 最小生成树：Prim 算法（从顶点出发）、Kruskal 算法（从边出发，需排序和并查集）。
     • 拓扑排序：针对有向无环图（DAG），确定节点的先后执行顺序。
     • 关键路径：用于工程进度规划，找到从起点到终点的最长路径。

3. 哈希表（Hash Table）

   • 核心思想：通过哈希函数将键映射到数组下标，实现高效查询。
   • 哈希函数：要求均匀分布，减少冲突；常见方法：取模、直接定址、折叠法。
   • 冲突解决：
     • 开放寻址法：线性探测、二次探测、双重哈希，适用于数据量小的场景。
     • 链地址法：数组 + 链表 / 红黑树，Java HashMap 采用此方法（链表长度≥8 转为红黑树）。
   • 操作：增删查 \(O(1)\)（平均），最坏 \(O(n)\)（哈希冲突严重）。
   • 应用：缓存、用户信息存储、频率统计。

四、 常用算法思想

1. 分治法

   • 核心思想：将问题分解为若干个规模较小的子问题，解决子问题后合并结果。
   • 步骤：分解 → 解决 → 合并。
   • 典型算法：归并排序、快速排序、二分查找、大整数乘法。

2. 动态规划（DP）

   • 核心思想：将复杂问题分解为重叠子问题，保存子问题的解（状态），避免重复计算，通过状态转移方程推导最终解。
   • 核心要素：状态定义、状态转移方程、初始条件、边界条件。
   • 典型问题：斐波那契数列、最长公共子序列（LCS）、最长递增子序列（LIS）、0-1 背包问题、最短路径。

3. 贪心算法

   • 核心思想：每一步选择局部最优解，期望最终得到全局最优解。
   • 适用条件：问题具有贪心选择性质和最优子结构。
   • 典型问题：活动选择问题、哈夫曼编码、最小生成树（Prim/Kruskal）、单源最短路径（Dijkstra）。
   • 局限性：并非所有问题都适用，如 0-1 背包问题贪心无法得到最优解。

4. 回溯算法

   • 核心思想：基于深度优先搜索，尝试所有可能的解，当发现当前路径无法得到正确解时，回溯到上一步，尝试其他路径。
   • 特点：穷举 + 剪枝（减少不必要的搜索）。
   • 典型问题：全排列、组合总和、N 皇后问题、数独求解。

5. 分支限界法

   • 核心思想：基于广度优先搜索，为每个节点设置边界，剪去不可能得到最优解的分支。
   • 与回溯的区别：回溯是深度优先，追求所有解；分支限界是广度优先，追求最优解。
   • 典型问题：0-1 背包问题、旅行商问题（TSP）。

五、 经典排序算法

排序算法是将一组数据按指定顺序排列的算法，可分为内部排序（数据在内存）和外部排序（数据在磁盘）。

注：k 为数值范围，d 为关键字位数。

六、 字符串算法

1. 字符串匹配
   • 暴力匹配：\(O(nm)\)，n 为主串长度，m 为模式串长度。
   • KMP 算法：\(O(n+m)\)，通过部分匹配表（next 数组）跳过不必要的比较。
   • 其他算法：Boyer-Moore 算法、Rabin-Karp 算法。
2. 字符串处理：前缀函数、后缀自动机、字典树（Trie 树，用于高效存储和查询字符串集合）。