数据结构与算法核心知识体系：从基础到进阶全解析

数据结构与算法是计算机科学的基石，直接决定程序的执行效率、资源占用与可扩展性，是开发者进阶路上的核心必修课。

一、核心算法思想

1. 动态规划（Dynamic Programming）

  • 核心三要素：
    1. 最优子结构：问题的最优解可由其子问题的最优解推导得出（例如：求“从A到B的最短路径”，可拆解为“从A到中间节点C的最短路径”与“从C到B的最短路径”的组合）；
    2. 边界条件：明确问题的初始状态（最小子问题的解），作为递推的起点（例如：斐波那契数列中，F(0)=0、F(1)=1即为边界）；
    3. 状态转移公式：建立子问题与原问题之间的递推关系，描述状态如何演进（例如：斐波那契数列的状态转移公式为F(n)=F(n-1)+F(n-2)）。
  • 与递归的关联：动态规划可解决的问题，均能通过“递归 + 备忘录”实现，两者的时间复杂度与空间复杂度均与问题基数成正比；但当基数较大时，递归会因重复计算导致性能瓶颈，而动态规划通过缓存中间结果避免冗余计算，性能更优。
  • 参考资料：动态规划详解
    递归 vs 动态规划：算法题中的选择与优化

2. 贪心算法（Greedy Algorithm）

  • 核心思想：在每一步决策中选择当前状态下的局部最优解，逐步累积得到全局最优解（核心是“短视”但有效，需确保问题满足“贪心选择性质”）；
  • 典型应用：部分背包问题（给定容量的背包，选择性价比最高的物品组合，最大化装载价值）、活动安排问题（选择最多不冲突的活动）等；
  • 补充示例：假设背包容量为10，物品A（价值6，重量3）、B（价值8，重量4）、C（价值10，重量5），贪心策略会优先选择性价比（价值/重量）最高的A（2），再选B（2），最后剩余容量3无法装下C，总价值14，即局部最优累积得到全局最优；

  • 补充示意图：
    贪心算法应用示意图
  • 参考资料：贪心算法详解

二、常用数据结构

数据结构是组织、存储数据的方式，不同结构适配不同的查询、插入、删除场景，核心分类、特性及补充说明如下：

1. 线性数据结构

线性结构中数据元素按线性顺序排列，访问方式单一，支持顺序或链式存储：

  • 基础线性结构：
    • 数组（Array）：连续存储的同类型数据集合，补充特性：查询效率O(1)，插入/删除效率O(n)（需移动元素），适用于数据量固定、查询频繁的场景（如存储用户ID列表）；
    • 链表（Linked List）：通过指针连接的非连续数据集合，补充特性：查询效率O(n)，插入/删除效率O(1)（仅需修改指针），适用于数据量动态变化、插入删除频繁的场景（如消息队列）；
  • 衍生线性结构：
    • 栈（Stack）：遵循“先进后出”（LIFO）规则的线性表，补充应用：函数调用栈、表达式求值、括号匹配；
    • 队列（Queue）：遵循“先进先出”（FIFO）规则的线性表，补充应用：任务调度、消息队列、广度优先遍历。

2. 树结构（Tree）

树是层次化的非线性结构，适用于高效查找、排序与索引场景，常见类型及补充说明如下：

  • 基础树结构：
    • 二叉树（Binary Tree）：每个节点最多有两个子节点的树，补充特性：满二叉树（所有叶子节点在同一层）、完全二叉树（除最后一层外，每层节点数满，最后一层左连续）；
  • 二叉树衍生结构：
    • 二叉查找树（Binary Search Tree）：左子树节点值小于根节点，右子树节点值大于根节点，便于元素查找与排序，补充缺陷：极端情况下退化为链表（如有序插入1、2、3、4），查询效率降至O(n)；
      • AVL树：平衡二叉查找树（左右子树高度差不超过1），通过旋转维持平衡，保证查找效率稳定在O(logn)；
      • 红黑树：通过颜色规则（根黑、叶黑、红节点子节点黑）维持平衡，插入删除旋转次数少于AVL树，补充应用：Java的TreeMap、TreeSet底层实现；
    • 二叉堆（Binary Heap）：完全二叉树结构，始终保证堆顶元素为最大值（大顶堆）或最小值（小顶堆），补充应用：堆排序算法、优先级队列（如任务优先级调度）；
  • 其他树结构：
    • 哈夫曼树（Huffman Tree）：带权路径长度最短的二叉树，用于将通信报文转换为哈夫曼编码，实现数据压缩（补充：频率越高的字符编码越短，压缩效率更高）；
    • B-树：多路平衡查找树，每个节点可存储多个关键字，补充应用：文件系统索引（适配磁盘IO的块存储特性）；
    • B+树：B-树的优化版本，所有数据存储在叶子节点，叶子节点通过链表连接，补充优势：查询效率稳定O(logn)、支持范围查询，是MySQL等关系数据库的默认索引结构；
    • 前缀树（Trie Tree）：按字符串前缀组织的树结构，补充应用：搜索引擎关键词联想、路由匹配、单词拼写检查。

3. 图结构（Graph）

图是由顶点（Vertex）和边（Edge）组成的非线性结构，用于表示多对多的关系，核心分类与算法补充如下：

  • 图的分类：有向图（边有方向，如A→B）、无向图（边无方向，如A-B）、有权图（边带权重，如交通路线距离）、无权图（边无权重）；
  • 遍历算法：
    • 广度优先遍历（BFS）：按层次遍历，补充应用：最短路径查找（无权图）、朋友圈数量统计；
    • 深度优先遍历（DFS）：沿路径深入遍历，补充应用：拓扑排序、迷宫求解；
  • 核心算法：
    • 最短路径算法：Dijkstra算法（单源最短路径，适用于无权图或正权图）、Floyd算法（多源最短路径，适用于任意图，时间复杂度O(n³)）；
    • 最小生成树（Minimum Spanning Tree）：在保证所有顶点连通的前提下，使边的总成本最小，补充应用：通信网络搭建（最小化布线成本）、交通路线规划。

4. 哈希表（Hash Table）

  • 核心结构：数组与链表的结合（哈希表的底层实现）；
  • 核心原理：通过哈希函数将键（Key）映射到数组索引，实现O(1)级别的快速查找；当发生哈希冲突（不同Key映射到同一索引）时，通过链表（或红黑树）解决；
  • 衍生结构：哈希链表，是LRU（最近最少使用）算法的核心数据结构（补充：哈希表保证查询效率，链表维护使用顺序）；
  • Java中的应用：HashMap底层采用“数组 + 链表 + 红黑树”的混合结构，当链表长度大于8时，自动转换为红黑树；基于统计学原理，链表长度超过8的概率极低，因此可忽略红黑树比链表占用更多空间的影响，优先保证查询效率（红黑树查询效率O(logn)，链表O(n)）。

5. 其他常用数据结构

  • 跳表（Skip List）：在链表基础上增加多层索引，补充优势：将查询效率从O(n)优化至O(logn)，且插入删除无需旋转，实现简单，补充应用：Redis的Sorted Set底层实现；
  • 线段树（Segment Tree）：数组与二叉树的结合，补充应用：区间求和、区间最大值/最小值查询、区间更新（如统计数组[1,3,5,7,9]中索引1-3的和）。

6. 数组的核心特性

  1. 存储空间大小固定，一旦创建无法动态改变；
  2. 存储空间为专用区域，不能被其他数据占用；
  3. 存储空间连续，元素之间无间隔；
  4. 支持通过数组名 + 下标直接访问任意元素（随机访问）。

三、经典算法

算法是解决特定问题的步骤集合，核心围绕排序、查找等场景，以下是常用算法的详细解析及补充说明：

1. 算法复杂度评估

  • 核心概念：时间复杂度（描述算法执行时间与输入规模的关系）、空间复杂度（描述算法所需存储空间与输入规模的关系），均采用“大O记法”表示最坏情况下的复杂度；
  • 常见时间复杂度定义及补充示例：
    • O(1)：常数时间，代码执行次数不受输入规模影响（示例：访问数组指定下标元素、两数相加；即使包含循环，若执行次数为常数级，如循环10次，仍记为O(1)）；
    • O(n)：线性时间，循环变量线性递增/递减，且循环上限与输入规模相关（示例：遍历数组、求数组总和）；
    • O(n²)：平方时间，包含两层嵌套循环，且循环变量均以恒定值递增/递减（示例：冒泡排序、插入排序、求两个数组的交集）；
    • O(logn)：对数时间，循环变量通过乘/除常数递增/递减（示例：二分查找、二叉树遍历）；
  • 参考资料：常用的时间复杂度分析

2. 排序算法

排序算法用于将数据按指定顺序排列，可按“稳定性”“排序场景”分类，核心算法及补充说明如下：

（1）排序算法分类

  • 按稳定性分类：
    • 稳定排序：相等元素在排序后保持原有相对位置（示例：冒泡排序、插入排序、归并排序）；
    • 不稳定排序：相等元素在排序后可能改变相对位置（示例：选择排序、快速排序、堆排序）；
  • 按排序场景分类：
    • 内部排序：排序过程完全在内存中完成（适用于小数据量）；
    • 外部排序：数据量过大，需借助磁盘等外部存储辅助排序（适用于大数据量，如归并排序的外部实现）。

（2）常用排序算法详情

排序算法 时间复杂度 空间复杂度 稳定性 核心原理 补充说明
冒泡排序 O(n²) O(1) 稳定 通过相邻元素两两比较，将较小元素往前调或较大元素往后调，逐轮冒泡至正确位置 简单易实现，适用于小规模数据
选择排序 O(n²) O(1) 不稳定 每轮从待排序数据中选出最小（或最大）元素，存放在当前序列的最前（或最后）位置，依次迭代至全部有序 交换次数少，不适用于大规模数据
插入排序 O(n²) O(1) 稳定 将待排序元素插入到已排序的有序表中，形成新的有序表；通过双层循环实现，外层遍历元素，内层查找插入位置并移动数据 适用于基本有序的数据，插入效率高
快速排序 O(nlogn) O(logn)~O(n) 不稳定 分而治之思想：取一个基准数，将小于基准数的元素放在左侧，大于基准数的元素放在右侧，基准数确定最终位置；递归处理左右子序列，直至整体有序 实际应用中效率最高，适用于大规模数据
归并排序 O(nlogn) O(n) 稳定 分而治之思想：将序列拆分为若干个子序列，先使每个子序列有序，再将有序子序列合并为整体有序序列 稳定且效率稳定，适用于对稳定性有要求的场景
堆排序 O(nlogn) O(1) 不稳定 利用二叉堆的特性：将待排序数据构建为大顶堆（或小顶堆），依次取出堆顶元素（最大值或最小值），重新调整堆结构，直至全部元素取出并有序排列 空间效率高，不适用于对稳定性有要求的场景
锦标赛排序 O(nlogn) O(n) 稳定 基于二叉堆的排序算法，通过构建锦标赛树（胜者树）选择最大值/最小值，依次迭代排序 适用于并行计算场景
计数排序 O(n + k)（k为数据范围） O(k) 稳定 线性时间排序，通过统计每个元素的出现次数，直接确定元素在有序序列中的位置 适用于数据范围小的场景（如学生成绩排序）
桶排序 O(n + k)（k为桶的数量） O(n + k) 稳定 线性时间排序，将数据分配到多个桶中，对每个桶单独排序后，合并所有桶的结果 适用于数据分布均匀的场景
基数排序 O(n×k)（k为数字位数） O(n + k) 稳定 线性时间排序，按数字的每一位（从低位到高位或反之）依次排序，逐步得到有序序列 适用于整数或字符串排序
希尔排序 取决于分组方式（通常O(nlogn)~O(n²)） O(1) 不稳定 插入排序的优化版本，将序列按一定步长分组，对每组进行插入排序，逐步缩小步长至1，完成最终排序 效率优于简单排序，适用于中等规模数据

3. 查找算法

查找算法用于从数据集合中查找目标元素，核心算法及补充说明如下：

  • 二分查找：适用于有序数组，通过不断缩小查找区间（取中间位置比较）实现高效查找；可进一步优化（如非中间位置作为分割点，如黄金分割点），补充时间复杂度O(logn)；
  • 字符串匹配算法：用于在一段文本（主串）中查找某个关键词（模式串），高效算法包括：
    • RK算法（Rabin-Karp算法）：通过哈希函数将字符串映射为数值，比较数值实现快速匹配，补充优势：可同时匹配多个模式串；
    • BM算法（Boyer-Moore算法）：从模式串尾部开始比较，利用坏字符规则与好后缀规则跳过无效比较，补充优势：实际应用中效率高于KMP；
    • KMP算法（Knuth-Morris-Pratt算法）：利用前缀函数避免模式串的重复比较，补充优势：时间复杂度稳定O(n + m)（n为主串长度，m为模式串长度）。

4. 网络安全算法

  • 加密算法：用于数据加密，保障传输安全，补充说明：
    • AES算法（对称加密）：加密解密使用同一密钥，速度快，适用于大数据量加密（如文件传输）；
    • RSA算法（非对称加密）：加密解密使用不同密钥（公钥加密、私钥解密），安全性高，适用于密钥交换、数字签名；
  • 哈希算法：用于数据完整性校验、签名等，补充说明：
    • MD5算法：输出128位哈希值，存在碰撞风险，适用于非敏感数据校验；
    • SHA算法（SHA-1、SHA-256等）：SHA-1输出160位，SHA-256输出256位，安全性高于MD5，适用于敏感数据校验。

参考资料

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
禁止转载，如需转载请通过简信或评论联系作者。

相关阅读更多精彩内容

友情链接更多精彩内容