数据结构与算法¶

概述¶

数据结构与算法

数据结构与算法是计算机科学的核心基础，研究数据的组织方式和操作方法，是程序设计的灵魂。本模块系统讲解数据结构的基本概念、常用算法的设计与分析方法。

知识体系结构¶

graph TB
    A[数据结构与算法] --> B[线性结构]
    A --> C[树结构]
    A --> D[哈希与堆]
    A --> E[排序算法]
    A --> F[查找算法]
    A --> G[图结构]
    A --> H[算法思想]
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style C fill:#FFF3E0
    style D fill:#F3E5F5
    style E fill:#FCE4EC
    style F fill:#E1F5FE
    style G fill:#FFF8E1
    style H fill:#E8EAF6

主要内容¶

线性结构¶

线性结构

数组: 连续存储，随机访问
链表: 链式存储，动态扩展
栈: 后进先出（LIFO）
队列: 先进先出（FIFO）
跳表: 多层索引，快速查找
循环队列/双端队列/优先队列: 特殊队列
单调栈/单调队列: 单调性优化
LRU/LFU缓存: 缓存淘汰策略

树结构¶

树结构

二叉树: 基础树结构
二叉搜索树: 有序查找
AVL树/红黑树: 自平衡树
堆: 优先队列实现
B树/B+树: 磁盘友好
线段树/树状数组: 区间查询
字典树: 字符串查找
并查集: 等价类划分
R树/KD树: 空间索引
Treap/伸展树: 随机化/自调整
替罪羊树: 部分重建
LSM树: 写优化

哈希与堆¶

哈希与堆

哈希表: 快速查找
布隆过滤器: 概率型数据结构
左堆/二项堆/斐波那契堆: 可合并堆

排序算法¶

排序算法

冒泡/选择/插入排序: O(n²)简单排序
快速排序/归并排序: O(nlogn)高效排序
堆排序: 原地排序
计数/基数/桶排序: 线性排序

查找算法¶

查找算法

二分查找: 有序数组查找
插值查找/斐波那契查找: 改进二分
哈希查找: O(1)查找
树表查找: BST/AVL/红黑树/B+树

图结构¶

图结构

图基础: 概念、存储、遍历
最短路径: Dijkstra、Floyd、Bellman-Ford
最小生成树: Prim、Kruskal
拓扑排序: 有向无环图排序
二分图/网络流: 图论应用
强连通分量: Kosaraju、Tarjan
欧拉路径/哈密顿路径: 路径问题
图着色: 顶点/边着色

算法思想¶

算法思想

递归: 问题分解
分治: 分而治之
动态规划: 最优子结构
贪心: 局部最优
回溯: 系统搜索
分支限界: 剪枝优化
双指针/位运算: 技巧优化
前缀和/滑动窗口: 区间处理
字符串匹配: KMP、BM
模拟退火/遗传算法: 启发式搜索

学习路径¶

推荐学习路径

基础阶段：线性结构 → 排序算法 → 查找算法
进阶阶段：树结构 → 哈希与堆 → 图结构
高级阶段：算法思想 → 复杂度分析 → 算法设计

目录¶

线性结构¶

树结构¶

哈希与堆¶

排序算法¶

查找算法¶

图结构¶

算法思想¶

参考资料¶

《算法导论》- Thomas H. Cormen
《数据结构与算法分析》- Mark Allen Weiss
《算法（第4版）》- Robert Sedgewick
OI Wiki