一、基础概念

数据结构：数据的组织、管理和存储格式，旨在高效访问和修改数据。它是程序设计的基础，直接影响算法效率。

算法：解决特定问题的有限指令序列，具有输入、输出、确定性、有穷性和可行性五个特性。

二、常见数据结构

1. 线性结构

  • 数组：连续内存空间，随机访问O(1)，插入删除O(n)
  • 链表：
    • 单链表：每个节点包含数据和指向下一节点的指针
    • 双链表：增加指向前一节点的指针
    • 循环链表：尾节点指向头节点
  • 栈：后进先出(LIFO)，基本操作：push/pop/top
  • 队列：先进先出(FIFO)，变种：优先队列、循环队列、双端队列

2. 非线性结构

  • 树：
    • 二叉树：每个节点最多两个子节点
    • 二叉搜索树：左子树<根<右子树，查找O(h)
    • 平衡二叉树(AVL)：左右子树高度差≤1
    • 红黑树：近似平衡的二叉搜索树，广泛用于库实现
    • B/B+树：多路平衡搜索树，数据库索引常用
  • 图：
    • 有向图/无向图
    • 存储方式：邻接矩阵、邻接表
    • 特殊图：DAG(有向无环图)、加权图

3. 高级数据结构

  • 哈希表：通过哈希函数映射键值，平均O(1)查找
  • 堆：完全二叉树，分为最大堆和最小堆，用于优先队列
  • 并查集：高效处理不相交集合的合并与查询
  • Trie树：前缀树，适合字符串前缀匹配
  • 跳表：通过多级索引加速查找，Redis中用于有序集合

三、核心算法

1. 排序算法

  • O(n²)算法：冒泡排序、选择排序、插入排序
  • O(nlogn)算法：归并排序(稳定)、快速排序(不稳定)、堆排序
  • 特殊排序：计数排序、桶排序、基数排序(适用于特定数据范围)

2. 查找算法

  • 顺序查找：O(n)
  • 二分查找：O(logn)，要求有序数组
  • 哈希查找：平均O(1)
  • 树查找：BST中O(h)，平衡树中O(logn)

3. 图算法

  • 遍历：深度优先搜索(DFS)、广度优先搜索(BFS)
  • 最短路径：Dijkstra(单源)、Floyd-Warshall(多源)、Bellman-Ford
  • 最小生成树：Prim算法、Kruskal算法
  • 拓扑排序：针对DAG
  • 网络流：Ford-Fulkerson、Edmonds-Karp

4. 高级算法思想

  • 分治法：将问题分解为子问题，如归并排序、快速排序
  • 动态规划：保存子问题解避免重复计算，如背包问题、LCS
  • 贪心算法：局部最优选择，如Huffman编码、Dijkstra算法
  • 回溯法：系统搜索问题解空间，如N皇后、数独
  • 分支限界：广度优先搜索+剪枝，组合优化问题

四、算法分析

1. 复杂度分析

  • 时间复杂度：算法执行时间与输入规模的函数关系
  • 空间复杂度：算法所需存储空间与输入规模的函数关系
  • 大O表示法：描述算法最坏情况下的渐近行为

2. 常见复杂度

  • O(1)：常数时间
  • O(logn)：对数时间
  • O(n)：线性时间
  • O(nlogn)：线性对数时间
  • O(n²)：平方时间
  • O(2^n)：指数时间
  • O(n!)：阶乘时间

五、学习建议

  1. 理论与实践结合：理解原理后再动手实现
  2. 循序渐进：从基础数据结构开始，逐步学习复杂算法
  3. 刷题巩固：LeetCode、牛客网等平台练习
  4. 分析源码：研究STL、JDK等标准库的实现
  5. 项目应用：在实际项目中应用所学知识
  6. 时间管理：面试准备时重点掌握高频考点

六、经典问题与题型

  • 链表反转、环检测
  • 二叉树遍历与重建
  • LRU缓存实现
  • 字符串匹配(KMP算法)
  • 动态规划：背包问题、最长公共子序列
  • 图论：最短路径、拓扑排序
  • 滑动窗口、双指针技巧

掌握数据结构与算法需要持之以恒的练习。理解原理、多写代码、善于总结是提高的关键。在实际编程中，应根据应用场景选择合适的数据结构和算法，平衡时间复杂度、空间复杂度和代码可维护性。