《数据结构与算法》课件

数据结构与算法高效数据组织与问题求解基础课程目标和学习要求掌握基本概念理解数据结构和算法核心原理实现典型算法能独立编写常见数据结构操作代码分析算法效率评估时间和空间复杂度解决实际问题数据结构的基本概念数据结构定义数据元素及其相互关系的集合逻辑结构描述数据元素之间的逻辑关系物理结构数据在计算机中的存储表示抽象数据类型算法的定义和特性1定义2有穷性3确定性解决问题的明确步骤序列算法必须在有限步骤内结束每步操作清晰无歧义4可行性输入输出算法步骤可执行时间复杂度和空间复杂度时间复杂度空间复杂度算法执行时间与问题规模关系算法执行所需存储空间与问题规模关系•常见O

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

1.3，不稳定排序小数据集效率高•快速排序基本思想1分治法，划分区间实现步骤2选基准、划分、递归排序性能特点3平均，最坏Onlogn On²优化方法4三数取中、小区间改用插入排序归并排序基本思想分治法，合并有序子序列实现步骤分割为最小单元、两两合并性能特点稳定，空间Onlogn On适用场景链表排序、外部排序、大数据量堆排序基本思想利用堆数据结构实现步骤建堆、交换堆顶、调整堆性能特点不稳定，原地排序Onlogn适用场景大时优于快排，求n TopK计数排序和桶排序计数排序桶排序•计算元素出现次数•将元素分到有限数量的桶中•适用范围小的整数•单独排序每个桶•On+k，稳定排序•On+k，取决于桶内排序基数排序实现方式性能特点从低位开始或从高位LSD MSD开始，稳定排序Odn+r基本思想适用场景按位数分组多次排序长度相同的数字、字符串2314外部排序适用场景1内存无法容纳全部数据基本思路2分块排序后归并多路归并3减少次数I/O败者树4优化选择最小元素过程动态规划基础1基本思想将复杂问题分解为简单子问题2核心特征最优子结构、重叠子问题3实现方式自底向上填表、自顶向下备忘录4经典问题背包问题、最长公共子序列、编辑距离贪心算法基本思想特点经典问题每步选择当前最优解局部最优推导全局最优活动选择、哈夫曼编码、最小生成树回溯法基本思想1试探回溯寻找可行解+实现方式2递归实现的深度优先搜索剪枝优化3提前排除无效分支经典问题4皇后、数独、图的着色问题N课程总结和展望基础掌握能力提升1数据组织、算法设计分析问题、选择合适数据结构2未来学习实践应用43高级算法、机器学习算法解决实际编程问题。