《数据结构与算法》课件

数据结构与算法高效数据组织与问题求解基础课程目标和学习要求掌握基本概念理解数据结构和算法核心原理实现典型算法能独立编写常见数据结构操作代码分析算法效率评估时间和空间复杂度解决实际问题数据结构的基本概念数据结构定义数据元素及其相互关系的集合逻辑结构描述数据元素之间的逻辑关系物理结构数据在计算机中的存储表示抽象数据类型算法的定义和特性1定义解决问题的明确步骤序列2有穷性算法必须在有限步骤内结束3确定性每步操作清晰无歧义4可行性算法步骤可执行输入输出时间复杂度和空间复杂度时间复杂度算法执行时间与问题规模关系常见：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)空间复杂度算法执行所需存储空间与问题规模关系辅助空间与输入规模的函数渐进符号和算法效率分析大O符号算法最坏情况时间复杂度上界大Ω符号算法最好情况时间复杂度下界大Θ符号算法平均情况时间复杂度确界线性表的定义和特征1概念有序数据元素集合2特点元素线性关系、前驱后继3基本操作初始化、增删改查4实现方式顺序存储、链式存储顺序表的实现单链表的定义和基本操作节点结构数据域+指针域创建空表初始化头指针为空插入节点调整前后节点指针删除节点释放节点空间并连接断点双向链表和循环链表双向链表前驱指针+数据+后继指针可双向遍历循环链表尾节点指向头节点无需判断结束栈的定义和特性定义后进先出的线性表基本操作入栈、出栈、获取栈顶特点只能在一端(栈顶)操作应用函数调用、表达式求值、括号匹配栈的顺序存储实现存储结构一维数组+栈顶指针1入栈操作栈顶指针增加，元素入栈2出栈操作元素出栈，栈顶指针减少3栈空栈满栈顶指针位置判断4栈的链式存储实现链栈结构单链表表示，表头为栈顶入栈操作头插法添加新节点出栈操作移除头节点并返回数据特点不限制容量，按需分配空间栈的应用：表达式求值中缀转后缀使用栈转换表达式操作符优先级决定入栈出栈顺序括号处理左括号入栈，右括号出栈后缀表达式求值遇操作数入栈，遇运算符弹栈计算队列的定义和特性定义先进先出的线性表基本操作入队、出队、获取队头特点一端入队，另一端出队应用缓冲区、打印队列、消息队列队列的顺序存储和循环队列1顺序队列问题假溢出现象2循环队列思想首尾相接成环3状态判断队空：front=rear4队满判断(rear+1)%maxsize=front队列的链式存储实现1链队结构带头尾指针的单链表2入队操作尾指针处添加新节点3出队操作头指针处移除节点4特点不限容量，无需判断队满优先队列和堆优先队列按优先级出队不遵循先进先出堆实现通常用二叉堆实现最大堆：父节点大于子节点最小堆：父节点小于子节点串的定义和基本操作定义由零个或多个字符组成的有限序列基本操作串比较、串连接、求子串模式匹配在主串中查找子串位置KMP算法原理普通匹配问题回溯导致重复比较KMP核心思想利用已知信息避免回溯部分匹配表记录模式串前缀后缀最长公共元素长度失配处理模式串向右移动位数=已匹配字符数-失配前最长共同前后缀KMP算法实现和优化next数组构建记录每个位置失配时的回退位置KMP实现主体匹配过程无回溯nextval优化处理字符相同的特殊情况树的基本概念和术语1定义n个节点的有限集合2术语根、父节点、子节点、兄弟、叶子、层次、深度、高度3特点层次结构、递归定义4应用文件系统、组织结构、语法树二叉树的定义和性质定义每个节点最多有两个子树性质1第i层最多有2^(i-1)个节点性质2深度为k的二叉树最多有2^k-1个节点性质3叶子节点数等于度为2的节点数加1二叉树的遍历（先序、中序、后序）先序遍历根→左→右中序遍历左→根→右后序遍历左→右→根递归实现利用栈实现非递归算法二叉树的层次遍历思路从根节点开始逐层访问1算法实现利用队列进行宽度优先搜索2处理过程队头出队并访问，子节点入队3应用获取层数、判断完全二叉树4二叉树的存储结构顺序存储一维数组适合完全二叉树随机访问效率高链式存储二叉链表：左右子树指针三叉链表：增加父节点指针适用于一般二叉树线索二叉树1定义利用空指针存放前驱后继信息2目的加快节点间遍历速度3线索类型前序线索、中序线索、后序线索4标记方式ltag和rtag标识指针类型哈夫曼树和哈夫曼编码哈夫曼树带权路径长度最小的二叉树构建方法权值小的节点合并为新节点哈夫曼编码变长编码，频率高的用短码二叉搜索树定义左子树小于根，右子树大于根特点中序遍历为升序序列查找比较节点值确定搜索方向插入删除维持二叉搜索树性质平衡二叉树（AVL树）定义任何节点左右子树高度差不超过1左旋处理右子树高于左子树右旋处理左子树高于右子树红黑树概述1定义一种自平衡二叉搜索树2五个特性根黑、叶黑、红节点子黑、黑高相同、新节点红3操作颜色调整和旋转维持平衡4应用关联数组、集合结构实现B树和B+树B树多路平衡查找树所有叶子同层适合磁盘存储B+树所有数据都在叶子节点叶子节点形成链表非叶节点只存索引适合数据库索引图的基本概念和术语顶点和边构成，有向/无向，带权/无权度、路径、连通、环、树等核心概念图的存储结构（邻接矩阵和邻接表）邻接矩阵二维数组表示连接关系适合稠密图查询快，空间占用大邻接表顶点数组+边链表适合稀疏图节省空间，查询慢图的深度优先搜索（DFS）思想尽可能深入探索图的分支1实现方式递归或使用栈2应用解迷宫问题、拓扑排序3时间复杂度O(V+E)邻接表，O(V²)邻接矩阵4图的广度优先搜索（BFS）思想逐层访问节点实现方式使用队列应用最短路径、网络爬虫时间复杂度O(V+E)邻接表，O(V²)邻接矩阵最小生成树：Prim算法基本思想从单个顶点开始构建选择边选最小权值连接外部顶点的边迭代过程重复直至包含所有顶点适用场景稠密图效率更高最小生成树：Kruskal算法1基本思想按权值升序选择边2选择条件不形成环路的最小权值边3判断环路使用并查集检测4适用场景稀疏图效率更高最短路径：Dijkstra算法解决问题单源最短路径基本思想贪心策略逐步确定最短路径算法过程维护距离数组，选择最小值更新限制不适用于负权边最短路径：Floyd算法解决问题多源最短路径基本思想动态规划逐步松弛路径算法过程三重循环考虑中转点时间复杂度O(V³)拓扑排序适用图类型有向无环图(DAG)基本思想按依赖关系排序顶点算法实现删除入度为0顶点及其边应用任务调度、编译依赖关键路径AOE网络中最长路径决定工程总时间的活动序列计算各顶点最早/最晚时间查找算法概述1静态查找表仅查找不修改2动态查找表插入删除查找3评价指标查找长度、平均查找长度4常见算法顺序查找、二分查找、散列查找顺序查找和二分查找顺序查找从头到尾逐个比较适用任何查找表平均查找长度n/2时间复杂度O(n)二分查找折半比较缩小范围要求有序表平均查找长度log₂n时间复杂度O(logn)散列表的基本概念1核心思想直接寻址2散列函数将关键字映射到地址3冲突处理解决多个关键字映射到同一地址4性能分析装填因子与查找性能关系散列函数的设计除留余数法h(key)=key%m乘法散列h(key)=⌊m(A·key-⌊A·key⌋)⌋折叠法将关键字分割后求和散列冲突的处理方法开放定址法线性探测、二次探测、双散列链地址法同一地址用链表存储再散列法冲突多时用新散列函数建立公共溢出区冲突放入溢出表排序算法概述10+常见排序算法各具特点和适用场景2排序方式内部排序与外部排序3评价指标时间复杂度、空间复杂度、稳定性冒泡排序和选择排序冒泡排序相邻元素比较交换最大元素逐渐上浮O(n²)，稳定排序选择排序选择最小元素交换位置每轮确定一个元素位置O(n²)，不稳定排序插入排序和希尔排序插入排序将元素插入有序序列类似扑克牌整理O(n²)，稳定排序小数据集效率高希尔排序改进的插入排序按间隔分组排序O(n^1.3)，不稳定排序快速排序1基本思想分治法，划分区间2实现步骤选基准、划分、递归排序3性能特点平均O(nlogn)，最坏O(n²)4优化方法三数取中、小区间改用插入排序归并排序基本思想分治法，合并有序子序列实现步骤分割为最小单元、两两合并性能特点稳定O(nlogn)，空间O(n)适用场景链表排序、外部排序、大数据量堆排序基本思想利用堆数据结构实现步骤建堆、交换堆顶、调整堆性能特点不稳定O(nlogn)，原地排序适用场景n大时优于快排，求TopK计数排序和桶排序计数排序计算元素出现次数适用范围小的整数O(n+k)，稳定排序桶排序将元素分到有限数量的桶中单独排序每个桶O(n+k)，取决于桶内排序基数排序1234基本思想按位数分组多次排序实现方式LSD从低位开始或MSD从高位开始性能特点O(d(n+r))，稳定排序适用场景长度相同的数字、字符串外部排序1适用场景内存无法容纳全部数据2基本思路分块排序后归并3多路归并减少I/O次数4败者树优化选择最小元素过程动态规划基础1基本思想将复杂问题分解为简单子问题2核心特征最优子结构、重叠子问题3实现方式自底向上填表、自顶向下备忘录4经典问题背包问题、最长公共子