张芷铭的个人博客数据结构是计算机存储、组织数据的方式，选择合适的数据结构是高效算法的基础。
线性结构
| 结构 | 特点 | 复杂度 |
|---|---|---|
| 数组 | 连续内存，随机访问 | 访问 O(1)，插入删除 O(n) |
| 链表 | 非连续内存，动态扩展 | 插入删除 O(1)，访问 O(n) |
| 栈 | LIFO 后进先出 | [[栈]] |
| 队列 | FIFO 先进先出 | 任务调度、BFS |
| 串 | 字符串匹配 | [[算法/KMP算法：字符串匹配]] |
树形结构
- 二叉树：前序、中序、后序、层序遍历
- 哈夫曼树：最优二叉树，数据压缩
- 树状数组：区间查询 O(log n)
- 线段树：动态区间统计
- 平衡树：AVL、红黑树
- B 树/B+ 树：数据库索引
- 字典树 (Trie)：字符串搜索
图结构
- [[最小代价生成树]] - MST（Prim、Kruskal）
- 最短路径（Dijkstra、Floyd）
- 拓扑排序、强连通分量
高级结构
| 结构 | 用途 |
|---|---|
| 并查集 | 动态连通性 |
| 堆 | 优先队列、Top K |
| 跳表 | 平衡树替代 |
| 布隆过滤器 | 快速查找 |
应用场景选择
| 场景 | 推荐结构 |
|---|---|
| 频繁访问 | 数组 |
| 频繁插入删除 | 链表 |
| 快速查找 | 哈希表 |
| 有序维护 | 平衡树 |
| 优先级处理 | 堆 |
| 区间操作 | 线段树 |
| 关系网络 | 图 |
学习路径
- 入门：数组 → 链表 → 栈 → 队列 → 二叉树
- 进阶：平衡树 → 堆 → 图 → 并查集
- 面试：[[笔试真题以及题解]]
Comments