数据结构与算法学习大纲一、学习大纲1. 线性表线性表是所有数据结构的底层基础是一对一逻辑关系的线性结构。逻辑规则所有元素排成一条逻辑直线除第一个元素外每个元素都有且仅有一个直接前驱除最后一个元素外每个元素都有且仅有一个直接后继。不存在一对多、多对多的关联。线性表分为两种物理存储实现顺序存储顺序表 / 数组、链式存储链表。顺序表物理特征数据在内存中占用连续完整的一块空间每个元素等长依靠下标可以直接定位任意元素。优点随机访问速度极快时间复杂度 O (1)遍历效率高内存无额外指针开销。缺点① 长度固定预先分配空间过小会溢出分配过大造成内存浪费② 在表中间插入、删除元素时需要移动后方所有数据数据量越大效率越低③ 扩容需要开辟一块全新连续内存拷贝全部原有数据开销巨大。适用场景查询、读取操作远多于插入删除数据长度提前可预估例如存储固定配置、常量列表。链表单链表/双向链表/循环链表物理特征数据分散存放在内存不同位置不要求连续空间。每一个存储单元称为节点节点分为两部分数据域存放真实数值、指针域存放下一个节点的内存地址用来串联节点。细分三类1单链表仅保存后继指针只能从头节点单向遍历2双向链表同时存储前驱、后继指针支持向前、向后双向遍历插入删除更方便但多占用一倍指针内存3循环链表尾节点指针指向头节点形成闭环适合环形任务调度。优点① 无需预先分配整块内存动态增减长度无空间浪费② 已知目标节点时插入、删除仅修改指针不需要移动大量数据效率高。缺点不支持随机下标访问查找目标元素必须从头节点依次遍历最坏时间复杂度 O (n)。适用场景频繁增删、数据长度不确定例如浏览器历史记录、LRU 缓存底层。核心操作增删改查、链表反转、快慢指针、合并链表是笔试最常考基础题型。2. 栈和队列二者都是受限线性表底层依旧依托线性表实现但人为限制了数据插入、删除的操作端口以此约束数据存取顺序用来模拟现实中固定顺序的业务逻辑。栈Stack后进先出 LIFO约束规则仅允许在线性表的同一端操作数据开放操作的一端叫栈顶完全封闭的一端叫栈底。新元素只能从栈顶放入取出元素也只能拿栈顶最新放入的数据。类比一摞叠放的盘子只能拿最上面的盘子新盘子只能叠在最上方。核心操作入栈 push、出栈 pop、取栈顶元素 top。应用场景① 操作系统函数调用栈递归、函数嵌套执行执行完毕后倒序返回② 表达式括号匹配、四则运算后缀表达式求值③ 文本编辑器撤销操作、网页回退④ 二叉树、图的非递归遍历。队列队列Queue先进先出 FIFO一端入队、一端出队类比排队买票。约束规则线性表两端拆分功能一端只允许放入数据队尾 rear另一端只允许取出数据队头 front先存入的数据一定会优先取出。基础数组队列缺陷数组不断出队后队头前面的空间会永久闲置造成内存浪费。因此衍生优化结构循环队列头尾指针在数组内循环移动重复利用闲置空间。拓展衍生结构① 双端队列 Deque两端都支持插入、删除同时具备栈和队列特性② 优先队列底层使用堆实现不按入队顺序出队按数据大小优先级取出元素。应用场景多线程任务调度、消息中间件消息队列、广度优先搜索 BFS、窗口滑动算法。3. 字符串字符串是元素类型限定为字符的特殊线性表逻辑上依旧满足一对一的线性关系专门处理文本、字符类数据也是程序开发最常用的数据类型。基础核心操作字符串拼接、子串截取、字符替换、长度统计、大小写转换。学习难点字符串模式匹配在一段主文本中查找目标子串分为两种核心算法1BF 暴力匹配算法逐个字符对比一旦匹配失败子串整体向后移动一位重新比对。逻辑简单但存在大量重复字符对比长文本下效率极低。2KMP 匹配算法提前预处理子串生成 next 前缀数组记录每个位置最长相等前后缀匹配失败时依靠数组直接跳转到无需重复比对的位置大幅减少重复运算时间复杂度优化至 O (nm)是搜索引擎、文本检索底层核心算法。实际业务场景搜索框关键词匹配、爬虫网页文本解析、代码编辑器语法高亮、敏感词过滤。4. 数组和广义表多维数组一维数组本质就是顺序表二维、三维多维数组将线性结构拓展为平面、立体结构用来存储矩阵、图片像素、表格数据。存储规则多维数组逻辑上是多维度但物理内存依旧是一维连续空间分为两种存储映射方式行优先存储先完整存完一行所有元素再存储下一行C、Java 语言默认列优先存储先完整存完一列所有元素再存储下一列Fortran 语言。核心考点给定多维数组下标计算元素在内存中的偏移地址用来理解底层内存寻址逻辑。应用场景图像处理像素矩阵、数学矩阵运算、游戏地图网格。广义表普通线性表的所有元素只能是单一数值广义表突破该限制表内元素可以是基础数值也可以嵌套另一张完整子表支持无限多层嵌套。逻辑特征不限制层级兼具线性、嵌套层级特性是树结构的简易抽象模型。应用场景JSON、XML 嵌套数据解析、树形菜单临时存储、复合表达式存储。5. 树存储结构线性结构最大缺陷查找数据最坏需要遍历全部元素 O (n)树是一对多层级非线性结构依靠层级二分将查找时间复杂度优化至 O (logn)是数据库、集合容器底层核心结构。基础定义由根节点、子节点组成每个节点最多拥有若干子节点节点之间无闭环。普通二叉树规定每个节点最多只能拥有左、右两个子节点分为满二叉树、完全二叉树。基础遍历方式前序、中序、后序、层序遍历是所有高级树的基础。二叉搜索树 BST约束规则任意节点左子树所有值 当前节点值 右子树所有值中序遍历结果为有序数列。缺陷有序数据插入会退化成单链表效率退回 O (n)。平衡二叉树 AVL、红黑树解决 BST 失衡问题自动旋转调整树高度保证增删查稳定 O (logn)Java TreeMap、C map 底层均为红黑树。堆大顶堆 / 小顶堆基于完全二叉树实现父节点值恒大于 / 小于子节点用来快速获取全局最值优先队列底层依靠堆常用于 TopK 问题、任务优先级排序。B 树、B 树多路平衡查找树适配磁盘 IO节点可以存放上千关键字减少磁盘读取次数MySQL 数据库索引底层使用 B 树是海量磁盘数据检索的核心结构。6. 图存储结构树是一对多关系图是多对多非线性结构由顶点节点、边节点之间的连接两部分组成节点之间可以任意双向、单向连接用来描述现实复杂关联关系。图分类无向图边无方向、有向图边带箭头单向通行、带权图边上附带数值代表距离、权重。两种主流物理存储方式邻接矩阵二维数组存储矩阵下标代表顶点数值代表两点之间是否存在边优点查询两点连通性极快缺点顶点数量多时矩阵占用内存极大稀疏图浪费大量空间。邻接表数组 链表组合数组下标代表顶点链表存储该顶点所有相连邻接点优点稀疏图节省内存缺点查询两点连通性需要遍历链表。基础遍历算法① DFS 深度优先一条路径走到尽头再回溯类似二叉树前序遍历② BFS 广度优先逐层向外遍历类似二叉树层序遍历。进阶衍生算法最短路径、最小生成树、拓扑排序。应用场景地图导航路线计算、社交软件好友关系、计算机网络拓扑、项目任务依赖排序。讲解操作系统内存分配逻辑解决静态数组固定长度的缺陷。8. 查找表结构专门解决“快速检索数据”需求分为静态查找、动态查找两大体系顺序查找线性遍历全部元素适配任意结构最坏 O (n)海量数据效率极低二分查找仅适用于有序顺序表不断缩小查找区间时间复杂度 O (logn)链表无法使用二分树表查找依托 BST、红黑树、B 树查找有序且支持动态增删稳定 O (logn)哈希表散列表核心高频结构通过哈希函数将数据映射到内存下标理想状态下增删查时间复杂度 O (1)。哈希表核心难点哈希冲突不同数据算出相同下标两种解决方案链地址法冲突位置挂载链表、开放寻址法向后寻找空闲位置。9. 排序算法内部排序所有待排序数据完整载入内存直接完成排序日常开发最常用按时间效率分为三类简单排序O(n²)冒泡排序、选择排序、插入排序逻辑简单易理解仅适合少量数据高效分治排序O(nlogn)快速排序、归并排序、堆排序工程主流排序算法大数据量首选非比较排序O(n)计数排序、基数排序、桶排序不依靠数值对比仅适用于数据范围有限的场景。外部排序针对超大规模数据场景待排序数据总量过大无法一次性全部载入内存只能存放在磁盘中依靠磁盘内存配合完成排序。核心流程分块处理、内部排序、多路归并优化手段败者树减少归并对比次数、置换选择排序生成更长有序块。10. 动态内存管理前面的顺序表、数组都属于静态内存分配程序运行前就固定分配内存大小无法动态扩容。本章讲解操作系统动态内存分配机制程序运行时按需申请、释放内存解决静态空间的局限性。核心知识点内存分配方式首次适配、最佳适配、最差适配内存碎片频繁申请释放小块内存后内存被分割为大量不连续空闲小块无法分配大块空间分为内部碎片、外部碎片优化算法伙伴系统、边界标记用来减少内存碎片、提升分配效率落地对应C/C malloc/free动态内存申请释放、Java/Go垃圾回收GC底层内存管理逻辑。作用理解编程语言内存底层原理写出避免内存泄漏、空间浪费的代码排查内存溢出类线上故障。
