锐客网

  1. 首页 > 睿知 > it技术 > >

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）

408学习专区算法学习数据结构


文章目录

  • 第三章 栈，队列和数组
    • 栈（stack）
    • 顺序栈的实现
    • 链栈的实现
    • 队列基本概念
    • 队列顺序实现
    • 队列的链式实现
    • 双端队列
    • 栈的应用--括号匹配问题
    • 栈的应用--表达式求值
    • 栈的应用--表达式求值问题（二） 重要考点
    • 栈的应用--递归
    • 队列的应用
    • 特殊矩阵--压缩存储
  • 第四章 串
    • 串的定义、基本操作
    • 串的存储结构
    • 字符串--朴素模式匹配算法
    • KMP算法
    • KMP算法--进一步优化

第三章 栈，队列和数组 栈（stack） 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

栈的定义
  • 只允许在一端进行插入或删除操作的线性表
  • 重要术语：栈顶，栈底，空栈
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

栈的基本操作
  • 创建，销毁，进栈，出栈，
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

栈的常考题型
  • 可能是先全部进栈，再出栈；也可能是边进边出；
  • 可能的出栈顺序的排列组合为卡特兰数，了解即可
  • 考试多数出选择题，选出可能的情况
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    知识点小结
  • 栈是一种进出受限的线性表
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

顺序栈的实现 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

顺序栈的定义，top存放栈顶位置
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

初始化操作
  • 初始化的栈没有存放元素，给top值为-1，也方便判断栈空
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

新元素入栈
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

课本写法，注意区分前++和后++
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

出栈操作
  • 注意区分前++和后++，不要把top指针指错位置，返回错误的元素
  • 这种删除这是逻辑删除，实际数据还残留在内存中
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    读栈顶元素
  • 与删除操作相似，也是返回当前top指向的元素
  • 不同的是，读栈顶操作无需删除元素，无需移动top值
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

另一种实现方式
  • top指向下一个元素的位置
  • 因此，初始化顺序栈以后，top的值应该是0
  • 入栈，出栈，会有所不同，注意区分
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

顺序栈的缺点：栈的大小不可改变
共享栈：
  • 两个栈共享一片空间
  • top1从上往下依次递增
  • top0从下往上依次递增
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    知识点小结
  • 采用声明栈的方式进行的定义，系统自动分配内存，并没有使用malloc
  • 因此内存的回收也会在函数结束由系统进行
链栈的实现 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

回顾
  • 头插法建立单链表，只对头结点后进行插入操作，对应了进栈操作
  • 单链表的删除操作，只对头结点后进行删除操作，对应了出栈操作
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

单链表的定义
  • 也区分带头结点和不带头结点，判空不一样
  • 可以理解为操作受限的单链表，代码基本相通，可以直接参考
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

队列基本概念 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

队列的定义
  • 也是一种操作受限的线性表
  • 队列与栈对比着理解
  • 队列特点：先进先出
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    队列的定义
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    队列的基本操作
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    知识点小结
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片
队列顺序实现 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

静态数组的方式实现，定义
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

初始化，队头队尾都指向0
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

插入数据元素
  • 如何判断队列满了？
  • rear为10不一定满，因为front前面可能有空余
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    循环队列
  • 将存储空间在逻辑上形成环状
  • 将无限的整数域映射到有限的整数集合上
  • 这种方式也叫做循环队列
  • 循环队列已满的条件
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

判空逻辑
  • 不能用rear=front，因为这是初始化时队列为空的判断逻辑
  • 代价：牺牲一个存储单元
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

出队操作
查询操作，通常队列的查询就是查询队头元素
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

方案一：判断队满，队空
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

方案二：判断队满，队空
  • 增加一个size记录长度
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    方案三：判断队满，队空
  • tag记录最近到底是进行了插入还是删除操作
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

其他出题方法，和上面对比理解
  • 队尾指针也可能指向队尾元素，代码略有不同
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

初始化状态
  • front=0 rear=n-1
  • 新增元素的时候，rear如图按照顺时针的方向往下走
  • 这个初始化的状态也可以用来
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    判满
  • 如果链表存满，rear与front的相对位置与为空时是一样的，有两个方案解决
  • 方案一，牺牲最后一个结点不再存储，用于判满
  • 方案二，增加一个辅助变量，size或者flag
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    知识点小结
  • 注意区分队尾指针到底是指向队尾元素的后一个位置，还是指向队尾元素
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片
队列的链式实现 还是单链表的限制版
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

链队列的实现
  • 通过链式存储实现的队列叫做链队列
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

初始化–带头节点版本
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

初始化–不带头结点
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

入队–带头节点
  • 向队尾插入元素
  • 不论插入的是第一个元素，还是之前已经有元素了，入队代码都是一样的
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    入队–不带头节点
  • 插入第一个元素和已经有元素了再插入，代码不一样
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

出队–带头节点
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

出队–不带头结点
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

队列满的情况
  • 链式存储无需关系，因为一般不会满
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
  • 如果需要计算队列长度，还是需要遍历队列得到
  • 如果经常需要掌握队列的长度，可增加一个元素用来存储队列长度
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

双端队列 双端队列
  • 也是一种操作受限的线性表
  • 只允许从两端插入和删除
  • 因此，栈和队列能实现的功能，双端队列也可以实现
  • 由此可以产生变种
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    双端队列考点
  • 判断输出序列的合法性
  • 不可能让列出所有，因为太多，只需重点分析，先后顺序即可
  • 还是推荐记住卡特兰数
栈
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

验证输出受限的双端队列
  • 栈里面合法的，双端队列里也一定合法
  • 只需要验证栈里不合法的即可
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    验证输入受限的双端队列
  • 栈里面合法的，双端队列里也一定合法
  • 只需要验证栈里不合法的即可
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片
技巧归纳
  • 输出受限的双端队列：如果在输出序列中看到某一号元素，那么在这个元素输出之前，之前的所有元素已经输入到队列里了
  • 输入首先的双端队列：在序号较大的元素出队之前，其他的序号较小的元素已经可以确定他们在队列的相对位置，接下来需要验证能不能根据左右两边的删除操作来拼凑出后续的这些队列
知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

栈的应用–括号匹配问题 比如，确保代码中的括号是成对出现的
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

配对技巧
  • 遇到左括号就入栈，遇到右括号就消耗一个左括号（出栈）
  • 消耗时发现括号类型不匹配，或者到最后同类型括号数量不一致，说输入非法
具体过程也可以看视频动画演示
算法流程图
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

括号匹配算法实现
  • 如果字符串比较长，静态数组不够长，可以换成链栈存储
  • 考试中可以直接使用基本操作，并注明接口的功能
  • 练习时，还是建议动手写完整的代码
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    知识点小结
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片
栈的应用–表达式求值 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

表达式的重要性
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

波兰数学家的灵感
  • 不用界限符也能无歧义的表达运算符的顺序
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

中缀、后缀、前缀表达式举例
  • 数字的前后顺序不可随意改变，可能会造成不同的结果
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    中缀表达式转后缀表达式（手算）
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    中缀转后缀需要注意
  • 后缀表达式的先后顺序，刚好就是中缀表达式中运算符的执行顺序
  • 即使是同一个中缀，我们也可以选择不同的执行顺序，因此对应的后缀也不唯一，但是执行结果都是一样的
  • 这个例子中，两种结果都一样；但如果是计算机算法的话应该是具有确定性的，因此我们选择让计算机固定为左侧的算法
  • 让计算机采取左优先的原则，即，只要左边的运算符能计算，就优先计算左边的
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    左优先原则可以保证算法的唯一性
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    后缀表达式该如何计算？（手算）
  • 从左向右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数
  • 注意两个操作数的左右顺序
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

后缀表达式计算（机算）
  • 最后栈中只会留下一个元素，就是我们的计算结果
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 中缀表达式只是人类的理解角度，不适合给计算机用
  • 给计算机中缀表达式，计算机还要判断运算符的生效顺序
  • 给计算机后缀表达式，可以直接计算，更加方便
后缀表达式如何转中缀
  • 把后缀表达式按照计算的顺序合并了，就是中缀表达式
中缀表达式转前缀表达式（手算）
  • 类似于中缀转后缀；
  • 采取右优先原则
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    前缀表达式的计算
  • 从右往左扫描
  • 注意，先出栈的是左操作数，这与后缀表达式计算恰好相反
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
  • 经典问题：表达式求值问题
  • 面试容易考
  • 后缀表达式在计算机中使用更多，前缀表达式用的少；考试更侧重考后缀表达式
  • 左右操作数，左右优先原则，这种叫法是咸鱼自己的叫法，考试时不建议这么说，要依据业内专业术语来说
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

栈的应用–表达式求值问题（二） 重要考点 这一节内容，不好理解，计算过程比较复杂；必须结合原视频看动画才能理解算法的精髓
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

中缀表达式转后缀表达式（机算）
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

中缀表达式的计算（用栈实现）
  • 其实就是把 中缀转后缀 和 后缀表达式求值 两个算法结合一下
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

思考：中缀表达式的计算搞这么复杂有意义么？
  • 这个算法在计算机中非常重要
  • 因为CPU只能执行最简单的基本运算
  • 在程序编译时，把复杂的指令翻译成机器指令的过程就用到了中缀转后缀的这种思想
栈的应用–递归 函数调用背后的过程
  • 最后被调用的其实是最先执行的，这个特性与栈的特性非常接近
  • 每进入到下一层函数，都要开辟新的一片内存；同时还要保存函数的入口的地址，便于回到上一层函数，接着往下执行
  • 其实在main函数之前也是需要执行其他前置函数的
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    使用IDE调试debug查看函数调用过程中的栈
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    栈在递归中的应用
  • 我们着重探讨栈和递归算法背后的联系
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

递归算法求阶乘
  • 随着调用层数的增加，问题规模逐渐收敛
  • 缺点是，如果递归层数太多，可能导致栈溢出，因为可利用内存资源优先
  • 所以要关注递归函数的空间复杂度
  • 由于递归算法背后就是用栈实现的，我们可以自定义栈来改造成非递归算法
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

递归算法求斐波那契数列
  • 由此可见，递归算法中可能包含很多重复的计算
  • 因此递归算法的效率有时不是很高
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

队列的应用 树的层次遍历
  • 一层层遍历
  • 需要辅助队列
  • 有个印象就行，后面的章节会详细讲解
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

图的广度优先遍历
  • 有个印象，后面的章节会详细讲解
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

队列在操作系统中的应用
  • 用队列实现先来先服务的策略
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

特殊矩阵–压缩存储 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

一维数组的存储结构
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

二维数组的存储结构
  • 在内存中可以有行优先、列优先存储策略
  • 行优先、列优先本质是把逻辑存储结构拉成线性结构，符合物理存储结构
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

行优先存储方式进行随机访问
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

列优先存储方式进行随机访问
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

普通矩阵的存储
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

对称矩阵的压缩存储（跟线性代数里的一样）
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

主对角线+下三角区，行优先原则存入以为数组
  • 等差数列求出用于存储的数组的大小
  • 通过映射函数，可以将矩阵下标与一维数组下标一一对应，便于我们随机访问
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 如果查找的元素在下三角取余，直接对应找到元素；如果是在上三角区域，转成下三角区的元素查找；
  • 映射公式没必要背，明白了等差数列的规律，现场推导也行
  • 考试的时候也可能会有一定的变换
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

出题发生变换，按列优先原则存入的数组
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

三角矩阵存储
  • 与对称矩阵的方式类似，只需要存储上三角，下三角的矩阵即可，
  • 常量映射到一维数组的最后一个位置即可
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

三对角矩阵压缩存储
  • 只需要存储带状矩阵的非零元素即可
  • 除了第一行，最后一行只有两个元素，其他每行都有三个元素
已知二维数组下标ij，求一维数组下标k
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

已知一维数组下标k，求二维数组下标ij
  • 这里的刚好，含义就是过了找临界值，过了这个临界值，刚好元素落在了某一行内，也就得到了i
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

求出i的值以后，根据ijk的关系求出j的值
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

稀疏矩阵的压缩存储
  • 非零元素远远少于矩阵元素的个数
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

压缩存储策略：顺序存储，三元组
  • 定义一个struct存储三元组，再用数组保存一个个struct
  • 缺点：要访问某一元素，只能依次扫描，无法随机访问
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

压缩存储策略：链式存储–十字链表法
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

常见考点
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

第四章 串 串的定义、基本操作 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的定义
  • 注意字符在主串中的编号是从1开始的
  • 空串和空格串是不一样的
  • 和线性表非常相似
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串VS线性表
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的基本操作
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的比较操作
  • 从第一个开始往后，依次逐个比较
  • 先出现更大的字符的串就更大
  • ascii码值越大，字符就越大
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

字符集编码
  • ascii编码对于英文字符够用，但是对于汉字不够用，最多只有2的8次方，256个状态
  • 基于中英文有一套unicode的字符集；给这些字符集进行编码，得到了编码方案；
  • 基于同一个字符集，可以有不同的编码方案，如GBK，UTF-8，；
  • 同一个字符在不同的编码方案里面占用的字节可能是不同的
  • 考试中一般只需要考虑英文字符的情况，即一个英文字符只占一个字节
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

拓展-乱码问题
  • 产生问题的原因，解码方式出现了错误
  • 没有使用正确的编码方案，错误的将编码翻译成了其他字符
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的存储结构 408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的顺序存储
  • 和线性表的存储结构很类似，只不过存储的元素限制为char
  • 静态数组实现，定长顺序存储，系统自动回收
  • 动态数组实现，堆分配存储，用完手动释放内存
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

串的顺序存储几套方案
  • 方案二，优点：字符的位序和数组下标相同；缺点：0位也是一个字节，只能表示0-255
  • 方案三，只能遍历一遍才知道串的长度
  • 如果频繁计算串的长度，还是有必要存储长度的
  • 方案四：结合一和二的优点，在结尾用int变量存储串的长度
  • 串的顺序存储优缺点，结合顺序表的优缺点来解答
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    串的链式存储
  • 存储密度低，char变量只占1个字节，32位的指针变量*却要占用4个字节
  • 解决办法，每一个node中存储更多的字符，改成char数组，提高存储密度
  • 串的链式存储的优缺点，结合链表的优缺点来回答
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

基本操作实现
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

求子串
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

比较串的大小
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

定位操作
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

字符串–朴素模式匹配算法 什么是字符串的模式匹配
  • 就是在主串中搜索与模式串相同的子串，并返回其所在位置
  • 可能搜索不到
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

两种模式匹配算法
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

朴素模式匹配算法
  • 即暴力匹配解决
  • 将主串中所有长度指定指定长度的子串都与模式串进行匹配
  • 找到了，就返回子串首字符的位置
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

使用字符串基本操作实现朴素模式匹配算法
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

仅通过操作数组下标实现朴素模式匹配算法
  • 注意理解主串i与子串j的关系，如果匹配失败；主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

朴素模式匹配算法代码实现
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

KMP算法 考点
  • 串的知识点，尤其是KMP算法比较难理解；但是在考纲中不占据重要位置，基本以小题为主
  • 重点就是如何理解KMP算法，手动求出next数组和nextval数组
    408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
    文章图片

    KMP算法
  • KMP这个名字是由人名字母简化来的
朴素模式匹配法的思考
  • 当主串与模式串字符不匹配了，i和j都要跳回1重新开始，这样导致整个算法的时间复杂度很大，O(mn)
  • 但是，当某一字符失配的时候，说明前面的字符已经匹配成功了，可以利用好这一部分信息
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 我们可以基于这一部分信息，可以避免从头开始匹配
  • 而是，从新的位置开始匹配
  • 这样，一下子跳过前面几个注定了匹配失败的中间子串
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

优化规律
  • 这种规律其实和主串没有关系的，而是取决于模式串的特点
  • 如何总结这种规律？
  • 其实就是当模式串分别取1.2.3.4…的长度时，总结模式串的前后缀的吻合程度
  • 已经吻合的表示没必要再比较了，直接跳到下一位进行比较
next数组
  • 基于这种规律我们总结了next数组，目前考试要求，next数组我们只需要自己手动总结规律即可
  • next数组的0标空着，从1标开始写
  • 当某个元素匹配失败，直接根据next数组存放的值，跳到指定的位置进行比较
  • 利用next数组进行匹配，主串指针不用回溯，模式串指针跳跃即可
  • next数组只和模式串有关，跟主串无关
  • next的1和2号位置可以直接无脑写0和1
  • 当需要跳到0标位置时，其实就是主串标+1，模式串标0+1=1
  • 如何手动求next数组，很难用文字解释清，多做几道题领会就很容易摸清规律了
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

代码实现
  • 有了next数组，我们就可以利用next数组，在代码里进行KMP算法匹配
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

举例，继续巩固一下如何求next数组
  • 固定模式：next 0不写，next 1写0，next 2写1
  • next数组的作用：当模式串的第j个字符匹配失败，从模式串的第next[j]个元素继续往后匹配
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 如，5号不匹配，说明前面的元素已经匹配了；
  • 把模式串向右移，直到i这个位置前面的几个元素可以和模式串的头几个元素相匹配
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 此时，出现了i的前面的元素与模式串的1号位匹配，因此我们可以直接从2号位开始匹配
  • 因此：当google的5号位失配，那么主串i不变，模式串跳到2号位继续匹配；next[5]=2
  • 得出google的next数组
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

开始使用next数组进行模式匹配
  • 当发现google的6号位不匹配，查找next数组发现next[6]=1；
  • 则主串i不变，模式串跳到1号位接着匹配
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

  • 结果发现跳到1号位之后，失配
  • 根据next跳到0号位
  • 我们有个特殊的判断，当发现j==0，则i和j同时+1，然后再匹配
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

求ababaa的的next数组
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

知识点小结
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

KMP算法–进一步优化 思考这种情况
  • 模式串3号不匹配，将会跳到1号匹配
  • 但是3号是a，1号也是a，所以1号也一定不匹配
  • 继续，1号失配，又要跳到0号位，继续后面的算法
  • 因此，当3号失配，我们可以直接跳到0号位
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

优化之后
  • 让next[3]=0
  • 当3号不匹配，直接跳到0号位
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

nextval数组
  • nextval本质上是对next数组的优化
  • 在使用KMP算法时，使用nextval数组替代next数组
  • 与主串没有关系，对于next数组以外的其他代码没有影响
手算求nextval数组
  • 先求出next数组
  • 开始从前往后写nextval数组，1号位固定写0
  • 当出现后面的字符与要跳到的前面的字符相同时，就把当前位置的值写成最前面的同字符的值
  • 如果当前字符与要跳到的前面字符不等，则保持不变
【408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）】408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

再练一个
408学习专区|数据结构学习笔记（3.栈，队列，数组 4.串）
文章图片

    推荐阅读


    上一篇：python|YOLOv5添加注意力机制

    下一篇：python|Python教程之粒子运动轨迹动态绘图