数据结构 思维导图
中心主题：数据结构
一级分支 1：基本概念
- 1 定义与目的
- 定义：在计算机中,组织和存储数据的方式。
- 目的：高效地访问和修改数据。
- 时间效率：算法执行速度（时间复杂度）。
- 空间效率：内存占用大小（空间复杂度）。
- 2 基本术语
- 数据：描述客观事物的符号。
- 数据元素：数据的基本单位,在计算机中通常作为一个整体考虑。
- 数据项：数据元素不可分割的最小单位。
- 数据对象：性质相同的数据元素的集合,是数据的一个子集。
- 逻辑结构：数据元素之间的逻辑关系。
- 物理结构/存储结构：数据在计算机中的存储方式。
- 3 数据结构的分类
- 逻辑结构：
- 线性结构：元素之间是一对一的关系。
- 非线性结构：元素之间是一对多或多对多的关系。
- 物理结构：
- 顺序存储：用一段连续的存储空间存储数据元素（如数组）。
- 链式存储：用指针链接分散的存储空间（如链表）。
- 索引存储：建立索引表来加快查找。
- 散列存储：通过散列函数计算存储地址。
- 逻辑结构：
一级分支 2：线性结构
- 1 数组
- 定义：在内存中分配一块连续的空间,存储相同类型的数据元素。
- 特点：
- 优点：通过下标（索引）访问元素，速度快（O(1)）；空间连续,缓存友好。
- 缺点：大小固定；插入和删除元素效率低（O(n)）,需要移动大量元素。
- 基本操作：创建、访问、修改、遍历、插入、删除、查找。
- 应用：向量、矩阵、查找表。
- 2 链表
- 定义：通过指针将一系列离散的节点串联起来,每个节点包含数据域和指针域。
- 特点：
- 优点：大小动态可变；插入和删除元素效率高（O(1)，已知位置）。
- 缺点：访问元素慢（O(n)）；每个节点需要额外的空间存储指针；非连续存储,缓存不友好。
- 常见类型：
- 单链表：每个节点指向下一个节点。
- 双链表：每个节点有前驱和后继两个指针。
- 循环链表：尾节点指向头节点,形成环。
- 静态链表：用数组实现的链表。
- 基本操作：创建、插入、删除、查找、遍历。
- 应用：LRU缓存、操作系统进程管理、实现栈和队列。
- 3 栈
- 定义：一种特殊的线性表，只允许在一端进行插入和删除操作（后进先出 - LIFO）。
- 特点：操作受限。
- 实现方式：
- 顺序栈：基于数组实现。
- 链式栈：基于链表实现。
- 基本操作：
push(入栈)、pop(出栈)、peek(查看栈顶)、isEmpty(判空)。 - 应用：函数调用栈、表达式求值（括号匹配、后缀表达式）、浏览器历史记录、撤销操作。
- 4 队列
- 定义：一种特殊的线性表，只允许在一端（队尾）插入，在另一端（队头）删除（先进先出 - FIFO）。
- 特点：操作受限。
- 实现方式：
- 顺序队列：基于数组实现，存在“假溢出”问题。
- 循环队列：将顺序队列的头尾相连,解决假溢出问题。
- 链式队列：基于链表实现。
- 基本操作：
enqueue(入队)、dequeue(出队)、front(查看队头)、isEmpty(判空)。 - 应用：任务调度、广度优先搜索、消息队列、打印任务管理。
一级分支 3：非线性结构
- 1 树
- 定义：一种分层的数据结构,由n个有限节点组成一个具有层次关系的集合。
- 基本术语：根节点、父节点、子节点、兄弟节点、叶子节点、节点度、树的度、节点层次、树的高度/深度。
- 常见树：
- 二叉树：每个节点最多有两个子节点（左、右）。
- 满二叉树：所有非叶子节点都有两个子节点,且所有叶子都在同一层。
- 完全二叉树：除最后一层外，其他层节点数都达到最大,且最后一层节点从左到右连续排列。
- 二叉搜索树：左子树所有值 < 根节点值 < 右子树所有值。
- 平衡二叉树：任何节点的两个子树高度差不超过1（如 AVL 树、红黑树）。
- 堆：一种特殊的完全二叉树。
- 大顶堆：父节点值 >= 子节点值。
- 小顶堆：父节点值 <= 子节点值。
- B树 / B+树：自平衡的多路搜索树,用于数据库和文件系统。
- 字典树：高效存储和检索字符串前缀的树形结构。
- 二叉树：每个节点最多有两个子节点（左、右）。
- 遍历方式：
- 深度优先遍历：
- 前序遍历：根 -> 左 -> 右
- 中序遍历：左 -> 根 -> 右 (对 BST 得到有序序列)
- 后序遍历：左 -> 右 -> 根
- 广度优先遍历：层序遍历 (使用队列实现)
- 深度优先遍历：
- 应用：文件系统目录结构、DOM树、数据库索引、路由协议、决策树。
- 2 图
- 定义：由顶点和边组成的非线性结构,用于表示多对多的关系。
- 基本术语：顶点、边、弧、有向图、无向图、带权图、路径、环、连通图。
- 存储方式：
- 邻接矩阵：用二维数组表示,适合稠密图。
- 邻接表：用链表数组表示,适合稀疏图。
- 遍历方式：
- 深度优先搜索：从一个顶点出发，尽可能深地探索分支（使用栈或递归）。
- 广度优先搜索：从一个顶点出发，逐层访问所有相邻顶点（使用队列）。
- 应用：社交网络、地图导航、推荐系统、任务调度、网络拓扑。
一级分支 4：高级数据结构
- 1 哈希表
- 定义：通过哈希函数将键映射到数组中的一个位置,实现快速查找。
- 核心概念：哈希函数、哈希冲突、负载因子。
- 解决冲突的方法：
- 链地址法：每个桶（数组位置）是一个链表,冲突的元素挂在链表后。
- 开放地址法：发生冲突时，寻找下一个空位（线性探测、二次探测、双重哈希）。
- 特点：
- 优点：理想情况下，增、删、查时间复杂度均为 O(1)。
- 缺点：存在哈希冲突；空间利用率可能不高；键需要是可哈希的。
- 应用：关联数组（如 Python dict, Java HashMap）、缓存、集合。
- 2 堆
- （已在“树”分支中详述,此处强调其作为独立高级数据结构的应用）
- 核心应用：优先队列。
- 算法应用：堆排序、Top K 问题。
一级分支 5：算法基础
- 1 排序算法
- 比较类排序：
- 冒泡排序：简单，效率低 (O(n²))。
- 选择排序：简单，效率低 (O(n²))。
- 插入排序：对小规模或基本有序数据高效 (O(n²))。
- 希尔排序：插入排序的改进版 (O(n^1.5))。
- 归并排序：稳定，时间复杂度稳定 O(n log n),需要额外空间。
- 快速排序：平均效率高 O(n log n)，不稳定,原地排序。
- 堆排序：时间复杂度 O(n log n)，不稳定,原地排序。
- 非比较类排序：
- 计数排序：整数范围有限时，效率极高 O(n+k)。
- 桶排序：数据分布均匀时，效率接近 O(n)。
- 基数排序：按位排序,稳定。
- 比较类排序：
- 2 查找算法
- 静态表查找：
- 顺序查找：简单，效率低 O(n)。
- 二分查找：有序数组，高效 O(log n)。
- 动态表查找：
- 二叉搜索树查找：平均 O(log n)，最坏 O(n)。
- 平衡树查找：保证 O(log n)。
- 哈希表查找：理想 O(1)。
- 静态表查找：
一级分支 6：应用与选择
- 1 如何选择数据结构？
- 考虑数据关系：线性还是非线性？一对一还是一对多？
- 考虑操作效率：最常执行的操作是什么？是查找快还是插入快？
- 考虑内存限制：数据量有多大？能否接受额外的指针开销？
- 权衡：没有最好的数据结构,只有最适合当前场景的数据结构。
- 2 典型应用场景
- 文件系统：树（目录结构）。
- 数据库索引：B+树、哈希表。
- 网络路由：图。
- 编译器/解释器：树（语法树）、栈（函数调用、符号表）、哈希表（符号表）。
- 游戏开发：图（地图）、树（技能树）、数组/列表（游戏对象列表）。
- 人工智能：图（状态空间搜索）、树（决策树）。
（图片来源网络，侵删）
