数据结构入门：从数组到图

数据结构入门：从数组到图 数据结构是算法的根基。选对数据结构，问题就解决了一半。 一、为什么要学数据结构？ 程序 = 数据结构 + 算法 —— 图灵奖得主 Niklaus Wirth 数据结构决定了 数据的组织方式 ，进而影响 操作的效率 。 例如： 频繁查找 → 哈希表（O(1)） 频繁插入 → 链表（O(1)） 排序查询 → 树（O(log n)） 二、八大基础数据结构 1. 数组（Array） 连续内存 ，下标访问 O(1)。 ✅ 随机访问快 ❌ 插入删除慢（要移动元素） ❌ 大小固定 2. 链表（Linked List） 非连续内存 ，指针连接。 ✅ 插入删除快 ✅ 大小动态 ❌ 不能随机访问 经典题 ：反转链表、检测环、合并有序链表 3. 栈（Stack） 后进先出（LIFO） 。 应用 ： 函数调用栈 括号匹配 表达式求值 浏览器前进后退 4. 队列（Queue） 先进先出（FIFO） 。 变种 ： 双端队列：两端都可进出 优先队列：按优先级出队（堆实现） 循环队列：固定大小，环形复用 应用 ：BFS、任务调度、消息队列 5. 树（Tree） 层次结构，n 个节点的有限集。 特殊二叉树 ： 满二叉树 ：所有层都满 完全二叉树 ：除最后一层，都满且靠左 二叉搜索树（BST） ：左 < 根 < 右 平衡二叉树（AVL） ：左右高度差 ≤ 1 红黑树 ：近似平衡，操作 O(log n) 遍历方式 ： 前序：根 → 左 → 右 中序：左 → 根 → 右（BST 得到升序） 后序：左 → 右 → 根 层序：逐层（BFS） 6. 图（Graph） 由 顶点 和 边 组成的结构。 存储方式 ： 邻接矩阵：二维数组，O(V²) 邻接表：链表数组，O(V+E) 遍历 ： DFS（深度优先）：递归或栈 BFS（广度优先）：队列 应用 ：社交网络、地图导航、依赖管理 7. 哈希表（Hash Table） 通过 哈希函数 把 key 映射到下标，平均 O(1) 查找。 冲突解决 ： 开放寻址：找下一个空位 链地址：每个桶存链表 应用 ：缓存、字典、去重 8. 堆（Heap） 完全二叉树 ，分为大顶堆和小顶堆。 父节点 ≥（或 ≤）子节点 插入/删除：O(log n) 取最值：O(1) 应用 ：优先队列、Top K、堆排序、定时器 三、复杂度对比 | 数据结构 | 查找 | 插入 | 删除 | 空间 | | | | | | | | 数组 | O(n) | O(n) | O(n) | O(n) | | 有序数组 | O(log n) | O(n) | O(n) | O(n) | | 链表 | O(n) | O(1) | O(1) | O(n) | | 哈希表 | O(1) | O(1) | O(1) | O(n) | | BST（平衡） | O(log n) | O(log n) | O(log n) | O(n) | | 堆 | O(n) | O(log n) | O(log n) | O(n) | 四、如何选型？ 灵魂三问 ： 1. 主要操作是什么？ 查找 / 插入 / 删除 / 范围查询 2. 数据规模多大？ 内存 / 磁盘 3. 是否需要有序？ 是 → 树；否 → 哈希 常见场景对应 ： | 场景 | 推荐 | | | | | 缓存 | 哈希表 | | 排行榜 | 堆 / 跳表 | | 撤销操作 | 栈 | | 任务调度 | 队列 | | 关系网络 | 图 | | 文件系统 | 树（B+ 树） | 五、LeetCode 经典题 数组/链表 两数之和 反转链表 环形链表 合并有序数组 栈/队列 有效的括号 用栈实现队列 滑动窗口最大值 树 二叉树的最大深度 验证 BST 二叉树的层序遍历 图 岛屿数量 课程表 网络延迟时间 六、小结 | 数据结构 | 核心 | 应用 | | | | | | 数组 | 连续 | 随机访问 | | 链表 | 指针 | 频繁增删 | | 栈 | LIFO | 调用栈、回溯 | | 队列 | FIFO | BFS、调度 | | 树 | 层次 | 索引、文件系统 | | 图 | 关系 | 网络、依赖 | | 哈希表 | 映射 | 缓存、字典 | | 堆 | 最值 | Top K、排序 | 小宇宙寄语：数据结构是程序员的基本功，刷 LeetCode 不是目的，理解每种结构的思想才是关键。