Super_Song_
Super_Song_
发布时间：2022-05-05 10:45

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

文章目录

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

第三章 栈，队列和数组

栈（stack）

数据结构学习笔记（3.栈，队列，数组 4.串）_第1张图片
栈的定义

  • 只允许在一端进行插入或删除操作的线性表
  • 重要术语：栈顶，栈底，空栈

数据结构学习笔记（3.栈，队列，数组 4.串）_第2张图片
栈的基本操作

  • 创建，销毁，进栈，出栈，

数据结构学习笔记（3.栈，队列，数组 4.串）_第3张图片
栈的常考题型

  • 可能是先全部进栈，再出栈；也可能是边进边出；
  • 可能的出栈顺序的排列组合为卡特兰数，了解即可
  • 考试多数出选择题，选出可能的情况
    数据结构学习笔记（3.栈，队列，数组 4.串）_第4张图片
    知识点小结
  • 栈是一种进出受限的线性表

数据结构学习笔记（3.栈，队列，数组 4.串）_第5张图片

顺序栈的实现

数据结构学习笔记（3.栈，队列，数组 4.串）_第6张图片
顺序栈的定义，top存放栈顶位置
数据结构学习笔记（3.栈，队列，数组 4.串）_第7张图片
初始化操作

  • 初始化的栈没有存放元素，给top值为-1，也方便判断栈空

数据结构学习笔记（3.栈，队列，数组 4.串）_第8张图片
新元素入栈
数据结构学习笔记（3.栈，队列，数组 4.串）_第9张图片
课本写法，注意区分前++和后++
数据结构学习笔记（3.栈，队列，数组 4.串）_第10张图片
出栈操作

  • 注意区分前++和后++，不要把top指针指错位置，返回错误的元素
  • 这种删除这是逻辑删除，实际数据还残留在内存中
    数据结构学习笔记（3.栈，队列，数组 4.串）_第11张图片
    读栈顶元素
  • 与删除操作相似，也是返回当前top指向的元素
  • 不同的是，读栈顶操作无需删除元素，无需移动top值

数据结构学习笔记（3.栈，队列，数组 4.串）_第12张图片
另一种实现方式

  • top指向下一个元素的位置
  • 因此，初始化顺序栈以后，top的值应该是0
  • 入栈，出栈，会有所不同，注意区分

数据结构学习笔记（3.栈，队列，数组 4.串）_第13张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第14张图片
顺序栈的缺点：栈的大小不可改变

共享栈：

  • 两个栈共享一片空间
  • top1从上往下依次递增
  • top0从下往上依次递增
    数据结构学习笔记（3.栈，队列，数组 4.串）_第15张图片
    知识点小结
  • 采用声明栈的方式进行的定义，系统自动分配内存，并没有使用malloc
  • 因此内存的回收也会在函数结束由系统进行

链栈的实现

数据结构学习笔记（3.栈，队列，数组 4.串）_第16张图片
回顾

  • 头插法建立单链表，只对头结点后进行插入操作，对应了进栈操作
  • 单链表的删除操作，只对头结点后进行删除操作，对应了出栈操作

数据结构学习笔记（3.栈，队列，数组 4.串）_第17张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第18张图片
单链表的定义

  • 也区分带头结点和不带头结点，判空不一样
  • 可以理解为操作受限的单链表，代码基本相通，可以直接参考

数据结构学习笔记（3.栈，队列，数组 4.串）_第19张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第20张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第21张图片

队列基本概念

数据结构学习笔记（3.栈，队列，数组 4.串）_第22张图片
队列的定义

  • 也是一种操作受限的线性表
  • 队列与栈对比着理解
  • 队列特点：先进先出
    数据结构学习笔记（3.栈，队列，数组 4.串）_第23张图片
    队列的定义
    数据结构学习笔记（3.栈，队列，数组 4.串）_第24张图片
    队列的基本操作
    数据结构学习笔记（3.栈，队列，数组 4.串）_第25张图片
    知识点小结
    数据结构学习笔记（3.栈，队列，数组 4.串）_第26张图片

队列顺序实现

数据结构学习笔记（3.栈，队列，数组 4.串）_第27张图片
静态数组的方式实现，定义
数据结构学习笔记（3.栈，队列，数组 4.串）_第28张图片
初始化，队头队尾都指向0
数据结构学习笔记（3.栈，队列，数组 4.串）_第29张图片
插入数据元素

  • 如何判断队列满了？
  • rear为10不一定满，因为front前面可能有空余
    数据结构学习笔记（3.栈，队列，数组 4.串）_第30张图片
    循环队列
  • 将存储空间在逻辑上形成环状
  • 将无限的整数域映射到有限的整数集合上
  • 这种方式也叫做循环队列
  • 循环队列已满的条件

数据结构学习笔记（3.栈，队列，数组 4.串）_第31张图片
判空逻辑

  • 不能用rear=front，因为这是初始化时队列为空的判断逻辑
  • 代价：牺牲一个存储单元

数据结构学习笔记（3.栈，队列，数组 4.串）_第32张图片
出队操作

查询操作，通常队列的查询就是查询队头元素

数据结构学习笔记（3.栈，队列，数组 4.串）_第33张图片
方案一：判断队满，队空
数据结构学习笔记（3.栈，队列，数组 4.串）_第34张图片
方案二：判断队满，队空

  • 增加一个size记录长度
    数据结构学习笔记（3.栈，队列，数组 4.串）_第35张图片
    方案三：判断队满，队空
  • tag记录最近到底是进行了插入还是删除操作

数据结构学习笔记（3.栈，队列，数组 4.串）_第36张图片
其他出题方法，和上面对比理解

  • 队尾指针也可能指向队尾元素，代码略有不同

数据结构学习笔记（3.栈，队列，数组 4.串）_第37张图片
初始化状态

  • front=0 rear=n-1
  • 新增元素的时候，rear如图按照顺时针的方向往下走
  • 这个初始化的状态也可以用来
    数据结构学习笔记（3.栈，队列，数组 4.串）_第38张图片
    判满
  • 如果链表存满，rear与front的相对位置与为空时是一样的，有两个方案解决
  • 方案一，牺牲最后一个结点不再存储，用于判满
  • 方案二，增加一个辅助变量，size或者flag
    数据结构学习笔记（3.栈，队列，数组 4.串）_第39张图片
    知识点小结
  • 注意区分队尾指针到底是指向队尾元素的后一个位置，还是指向队尾元素
    数据结构学习笔记（3.栈，队列，数组 4.串）_第40张图片

队列的链式实现

还是单链表的限制版
数据结构学习笔记（3.栈，队列，数组 4.串）_第41张图片
链队列的实现

  • 通过链式存储实现的队列叫做链队列

数据结构学习笔记（3.栈，队列，数组 4.串）_第42张图片
初始化–带头节点版本
数据结构学习笔记（3.栈，队列，数组 4.串）_第43张图片
初始化–不带头结点
数据结构学习笔记（3.栈，队列，数组 4.串）_第44张图片
入队–带头节点

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

数据结构学习笔记（3.栈，队列，数组 4.串）_第46张图片
出队–带头节点
数据结构学习笔记（3.栈，队列，数组 4.串）_第47张图片
出队–不带头结点
数据结构学习笔记（3.栈，队列，数组 4.串）_第48张图片
队列满的情况

  • 链式存储无需关系，因为一般不会满

数据结构学习笔记（3.栈，队列，数组 4.串）_第49张图片
知识点小结

  • 如果需要计算队列长度，还是需要遍历队列得到
  • 如果经常需要掌握队列的长度，可增加一个元素用来存储队列长度

数据结构学习笔记（3.栈，队列，数组 4.串）_第50张图片

双端队列

双端队列

  • 也是一种操作受限的线性表
  • 只允许从两端插入和删除
  • 因此，栈和队列能实现的功能，双端队列也可以实现
  • 由此可以产生变种
    数据结构学习笔记（3.栈，队列，数组 4.串）_第51张图片
    双端队列考点
  • 判断输出序列的合法性
  • 不可能让列出所有，因为太多，只需重点分析，先后顺序即可
  • 还是推荐记住卡特兰数

栈
数据结构学习笔记（3.栈，队列，数组 4.串）_第52张图片

验证输出受限的双端队列

  • 栈里面合法的，双端队列里也一定合法
  • 只需要验证栈里不合法的即可
    数据结构学习笔记（3.栈，队列，数组 4.串）_第53张图片
    验证输入受限的双端队列
  • 栈里面合法的，双端队列里也一定合法
  • 只需要验证栈里不合法的即可
    数据结构学习笔记（3.栈，队列，数组 4.串）_第54张图片

技巧归纳

  • 输出受限的双端队列：如果在输出序列中看到某一号元素，那么在这个元素输出之前，之前的所有元素已经输入到队列里了
  • 输入首先的双端队列：在序号较大的元素出队之前，其他的序号较小的元素已经可以确定他们在队列的相对位置，接下来需要验证能不能根据左右两边的删除操作来拼凑出后续的这些队列

知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第55张图片

栈的应用–括号匹配问题

比如，确保代码中的括号是成对出现的
数据结构学习笔记（3.栈，队列，数组 4.串）_第56张图片
配对技巧

  • 遇到左括号就入栈，遇到右括号就消耗一个左括号（出栈）
  • 消耗时发现括号类型不匹配，或者到最后同类型括号数量不一致，说输入非法

具体过程也可以看视频动画演示

算法流程图
数据结构学习笔记（3.栈，队列，数组 4.串）_第57张图片
括号匹配算法实现

  • 如果字符串比较长，静态数组不够长，可以换成链栈存储
  • 考试中可以直接使用基本操作，并注明接口的功能
  • 练习时，还是建议动手写完整的代码
    数据结构学习笔记（3.栈，队列，数组 4.串）_第58张图片
    知识点小结
    数据结构学习笔记（3.栈，队列，数组 4.串）_第59张图片

栈的应用–表达式求值

数据结构学习笔记（3.栈，队列，数组 4.串）_第60张图片

表达式的重要性
数据结构学习笔记（3.栈，队列，数组 4.串）_第61张图片
波兰数学家的灵感

  • 不用界限符也能无歧义的表达运算符的顺序

数据结构学习笔记（3.栈，队列，数组 4.串）_第62张图片
中缀、后缀、前缀表达式举例

  • 数字的前后顺序不可随意改变，可能会造成不同的结果
    数据结构学习笔记（3.栈，队列，数组 4.串）_第63张图片
    中缀表达式转后缀表达式（手算）
    数据结构学习笔记（3.栈，队列，数组 4.串）_第64张图片
    中缀转后缀需要注意
  • 后缀表达式的先后顺序，刚好就是中缀表达式中运算符的执行顺序
  • 即使是同一个中缀，我们也可以选择不同的执行顺序，因此对应的后缀也不唯一，但是执行结果都是一样的
  • 这个例子中，两种结果都一样；但如果是计算机算法的话应该是具有确定性的，因此我们选择让计算机固定为左侧的算法
  • 让计算机采取左优先的原则，即，只要左边的运算符能计算，就优先计算左边的
    数据结构学习笔记（3.栈，队列，数组 4.串）_第65张图片
    左优先原则可以保证算法的唯一性
    数据结构学习笔记（3.栈，队列，数组 4.串）_第66张图片
    后缀表达式该如何计算？（手算）
  • 从左向右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数
  • 注意两个操作数的左右顺序

数据结构学习笔记（3.栈，队列，数组 4.串）_第67张图片
后缀表达式计算（机算）

  • 最后栈中只会留下一个元素，就是我们的计算结果

数据结构学习笔记（3.栈，队列，数组 4.串）_第68张图片

  • 中缀表达式只是人类的理解角度，不适合给计算机用
  • 给计算机中缀表达式，计算机还要判断运算符的生效顺序
  • 给计算机后缀表达式，可以直接计算，更加方便

后缀表达式如何转中缀

  • 把后缀表达式按照计算的顺序合并了，就是中缀表达式

中缀表达式转前缀表达式（手算）

  • 类似于中缀转后缀；
  • 采取右优先原则
    数据结构学习笔记（3.栈，队列，数组 4.串）_第69张图片
    数据结构学习笔记（3.栈，队列，数组 4.串）_第70张图片
    前缀表达式的计算
  • 从右往左扫描
  • 注意，先出栈的是左操作数，这与后缀表达式计算恰好相反

数据结构学习笔记（3.栈，队列，数组 4.串）_第71张图片
知识点小结

  • 经典问题：表达式求值问题
  • 面试容易考
  • 后缀表达式在计算机中使用更多，前缀表达式用的少；考试更侧重考后缀表达式
  • 左右操作数，左右优先原则，这种叫法是咸鱼自己的叫法，考试时不建议这么说，要依据业内专业术语来说

数据结构学习笔记（3.栈，队列，数组 4.串）_第72张图片

栈的应用–表达式求值问题（二） 重要考点

这一节内容，不好理解，计算过程比较复杂；必须结合原视频看动画才能理解算法的精髓
数据结构学习笔记（3.栈，队列，数组 4.串）_第73张图片
中缀表达式转后缀表达式（机算）
数据结构学习笔记（3.栈，队列，数组 4.串）_第74张图片

数据结构学习笔记（3.栈，队列，数组 4.串）_第75张图片

中缀表达式的计算（用栈实现）

  • 其实就是把 中缀转后缀 和 后缀表达式求值 两个算法结合一下

数据结构学习笔记（3.栈，队列，数组 4.串）_第76张图片

数据结构学习笔记（3.栈，队列，数组 4.串）_第77张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第78张图片

思考：中缀表达式的计算搞这么复杂有意义么？

  • 这个算法在计算机中非常重要
  • 因为CPU只能执行最简单的基本运算
  • 在程序编译时，把复杂的指令翻译成机器指令的过程就用到了中缀转后缀的这种思想

栈的应用–递归

函数调用背后的过程

  • 最后被调用的其实是最先执行的，这个特性与栈的特性非常接近
  • 每进入到下一层函数，都要开辟新的一片内存；同时还要保存函数的入口的地址，便于回到上一层函数，接着往下执行
  • 其实在main函数之前也是需要执行其他前置函数的
    数据结构学习笔记（3.栈，队列，数组 4.串）_第79张图片
    使用IDE调试debug查看函数调用过程中的栈
    数据结构学习笔记（3.栈，队列，数组 4.串）_第80张图片
    栈在递归中的应用
  • 我们着重探讨栈和递归算法背后的联系

数据结构学习笔记（3.栈，队列，数组 4.串）_第81张图片
递归算法求阶乘

  • 随着调用层数的增加，问题规模逐渐收敛
  • 缺点是，如果递归层数太多，可能导致栈溢出，因为可利用内存资源优先
  • 所以要关注递归函数的空间复杂度
  • 由于递归算法背后就是用栈实现的，我们可以自定义栈来改造成非递归算法

数据结构学习笔记（3.栈，队列，数组 4.串）_第82张图片
递归算法求斐波那契数列

  • 由此可见，递归算法中可能包含很多重复的计算
  • 因此递归算法的效率有时不是很高

数据结构学习笔记（3.栈，队列，数组 4.串）_第83张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第84张图片

队列的应用

树的层次遍历

  • 一层层遍历
  • 需要辅助队列
  • 有个印象就行，后面的章节会详细讲解

数据结构学习笔记（3.栈，队列，数组 4.串）_第85张图片
图的广度优先遍历

  • 有个印象，后面的章节会详细讲解

数据结构学习笔记（3.栈，队列，数组 4.串）_第86张图片
队列在操作系统中的应用

  • 用队列实现先来先服务的策略

在这里插入图片描述
数据结构学习笔记（3.栈，队列，数组 4.串）_第87张图片

特殊矩阵–压缩存储

数据结构学习笔记（3.栈，队列，数组 4.串）_第88张图片
一维数组的存储结构
数据结构学习笔记（3.栈，队列，数组 4.串）_第89张图片
二维数组的存储结构

  • 在内存中可以有行优先、列优先存储策略
  • 行优先、列优先本质是把逻辑存储结构拉成线性结构，符合物理存储结构

数据结构学习笔记（3.栈，队列，数组 4.串）_第90张图片
行优先存储方式进行随机访问

数据结构学习笔记（3.栈，队列，数组 4.串）_第91张图片
列优先存储方式进行随机访问
数据结构学习笔记（3.栈，队列，数组 4.串）_第92张图片
普通矩阵的存储
数据结构学习笔记（3.栈，队列，数组 4.串）_第93张图片
对称矩阵的压缩存储（跟线性代数里的一样）
数据结构学习笔记（3.栈，队列，数组 4.串）_第94张图片
主对角线+下三角区，行优先原则存入以为数组

  • 等差数列求出用于存储的数组的大小
  • 通过映射函数，可以将矩阵下标与一维数组下标一一对应，便于我们随机访问

数据结构学习笔记（3.栈，队列，数组 4.串）_第95张图片

  • 如果查找的元素在下三角取余，直接对应找到元素；如果是在上三角区域，转成下三角区的元素查找；
  • 映射公式没必要背，明白了等差数列的规律，现场推导也行
  • 考试的时候也可能会有一定的变换

数据结构学习笔记（3.栈，队列，数组 4.串）_第96张图片
出题发生变换，按列优先原则存入的数组
数据结构学习笔记（3.栈，队列，数组 4.串）_第97张图片
在这里插入图片描述
三角矩阵存储

  • 与对称矩阵的方式类似，只需要存储上三角，下三角的矩阵即可，
  • 常量映射到一维数组的最后一个位置即可

数据结构学习笔记（3.栈，队列，数组 4.串）_第98张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第99张图片
三对角矩阵压缩存储

  • 只需要存储带状矩阵的非零元素即可
  • 除了第一行，最后一行只有两个元素，其他每行都有三个元素

已知二维数组下标ij，求一维数组下标k
数据结构学习笔记（3.栈，队列，数组 4.串）_第100张图片
已知一维数组下标k，求二维数组下标ij

  • 这里的刚好，含义就是过了找临界值，过了这个临界值，刚好元素落在了某一行内，也就得到了i

数据结构学习笔记（3.栈，队列，数组 4.串）_第101张图片
求出i的值以后，根据ijk的关系求出j的值
数据结构学习笔记（3.栈，队列，数组 4.串）_第102张图片
稀疏矩阵的压缩存储

  • 非零元素远远少于矩阵元素的个数

数据结构学习笔记（3.栈，队列，数组 4.串）_第103张图片

压缩存储策略：顺序存储，三元组

  • 定义一个struct存储三元组，再用数组保存一个个struct
  • 缺点：要访问某一元素，只能依次扫描，无法随机访问

数据结构学习笔记（3.栈，队列，数组 4.串）_第104张图片
压缩存储策略：链式存储–十字链表法
数据结构学习笔记（3.栈，队列，数组 4.串）_第105张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第106张图片
常见考点
数据结构学习笔记（3.栈，队列，数组 4.串）_第107张图片

第四章 串

串的定义、基本操作

数据结构学习笔记（3.栈，队列，数组 4.串）_第108张图片
串的定义

  • 注意字符在主串中的编号是从1开始的
  • 空串和空格串是不一样的
  • 和线性表非常相似

数据结构学习笔记（3.栈，队列，数组 4.串）_第109张图片
串VS线性表
数据结构学习笔记（3.栈，队列，数组 4.串）_第110张图片
串的基本操作
数据结构学习笔记（3.栈，队列，数组 4.串）_第111张图片
串的比较操作

  • 从第一个开始往后，依次逐个比较
  • 先出现更大的字符的串就更大
  • ascii码值越大，字符就越大

数据结构学习笔记（3.栈，队列，数组 4.串）_第112张图片
字符集编码

  • ascii编码对于英文字符够用，但是对于汉字不够用，最多只有2的8次方，256个状态
  • 基于中英文有一套unicode的字符集；给这些字符集进行编码，得到了编码方案；
  • 基于同一个字符集，可以有不同的编码方案，如GBK，UTF-8，；
  • 同一个字符在不同的编码方案里面占用的字节可能是不同的
  • 考试中一般只需要考虑英文字符的情况，即一个英文字符只占一个字节

数据结构学习笔记（3.栈，队列，数组 4.串）_第113张图片
拓展-乱码问题

  • 产生问题的原因，解码方式出现了错误
  • 没有使用正确的编码方案，错误的将编码翻译成了其他字符

数据结构学习笔记（3.栈，队列，数组 4.串）_第114张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第115张图片

串的存储结构

数据结构学习笔记（3.栈，队列，数组 4.串）_第116张图片
串的顺序存储

  • 和线性表的存储结构很类似，只不过存储的元素限制为char
  • 静态数组实现，定长顺序存储，系统自动回收
  • 动态数组实现，堆分配存储，用完手动释放内存

数据结构学习笔记（3.栈，队列，数组 4.串）_第117张图片
串的顺序存储几套方案

  • 方案二，优点：字符的位序和数组下标相同；缺点：0位也是一个字节，只能表示0-255
  • 方案三，只能遍历一遍才知道串的长度
  • 如果频繁计算串的长度，还是有必要存储长度的
  • 方案四：结合一和二的优点，在结尾用int变量存储串的长度
  • 串的顺序存储优缺点，结合顺序表的优缺点来解答
    数据结构学习笔记（3.栈，队列，数组 4.串）_第118张图片
    串的链式存储
  • 存储密度低，char变量只占1个字节，32位的指针变量*却要占用4个字节
  • 解决办法，每一个node中存储更多的字符，改成char数组，提高存储密度
  • 串的链式存储的优缺点，结合链表的优缺点来回答

数据结构学习笔记（3.栈，队列，数组 4.串）_第119张图片
基本操作实现
数据结构学习笔记（3.栈，队列，数组 4.串）_第120张图片
求子串
数据结构学习笔记（3.栈，队列，数组 4.串）_第121张图片
比较串的大小
数据结构学习笔记（3.栈，队列，数组 4.串）_第122张图片
定位操作
数据结构学习笔记（3.栈，队列，数组 4.串）_第123张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第124张图片

字符串–朴素模式匹配算法

什么是字符串的模式匹配

  • 就是在主串中搜索与模式串相同的子串，并返回其所在位置
  • 可能搜索不到

数据结构学习笔记（3.栈，队列，数组 4.串）_第125张图片
两种模式匹配算法
在这里插入图片描述
朴素模式匹配算法

  • 即暴力匹配解决
  • 将主串中所有长度指定指定长度的子串都与模式串进行匹配
  • 找到了，就返回子串首字符的位置

数据结构学习笔记（3.栈，队列，数组 4.串）_第126张图片
使用字符串基本操作实现朴素模式匹配算法
数据结构学习笔记（3.栈，队列，数组 4.串）_第127张图片
仅通过操作数组下标实现朴素模式匹配算法

  • 注意理解主串i与子串j的关系，如果匹配失败；主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置

数据结构学习笔记（3.栈，队列，数组 4.串）_第128张图片

数据结构学习笔记（3.栈，队列，数组 4.串）_第129张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第130张图片
朴素模式匹配算法代码实现
数据结构学习笔记（3.栈，队列，数组 4.串）_第131张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第132张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第133张图片

KMP算法

考点

  • 串的知识点，尤其是KMP算法比较难理解；但是在考纲中不占据重要位置，基本以小题为主
  • 重点就是如何理解KMP算法，手动求出next数组和nextval数组
    数据结构学习笔记（3.栈，队列，数组 4.串）_第134张图片
    KMP算法
  • KMP这个名字是由人名字母简化来的

朴素模式匹配法的思考

  • 当主串与模式串字符不匹配了，i和j都要跳回1重新开始，这样导致整个算法的时间复杂度很大，O(mn)
  • 但是，当某一字符失配的时候，说明前面的字符已经匹配成功了，可以利用好这一部分信息

数据结构学习笔记（3.栈，队列，数组 4.串）_第135张图片

  • 我们可以基于这一部分信息，可以避免从头开始匹配
  • 而是，从新的位置开始匹配
  • 这样，一下子跳过前面几个注定了匹配失败的中间子串

在这里插入图片描述
数据结构学习笔记（3.栈，队列，数组 4.串）_第136张图片
优化规律

  • 这种规律其实和主串没有关系的，而是取决于模式串的特点
  • 如何总结这种规律？
  • 其实就是当模式串分别取1.2.3.4…的长度时，总结模式串的前后缀的吻合程度
  • 已经吻合的表示没必要再比较了，直接跳到下一位进行比较

next数组

  • 基于这种规律我们总结了next数组，目前考试要求，next数组我们只需要自己手动总结规律即可
  • next数组的0标空着，从1标开始写
  • 当某个元素匹配失败，直接根据next数组存放的值，跳到指定的位置进行比较
  • 利用next数组进行匹配，主串指针不用回溯，模式串指针跳跃即可
  • next数组只和模式串有关，跟主串无关
  • next的1和2号位置可以直接无脑写0和1
  • 当需要跳到0标位置时，其实就是主串标+1，模式串标0+1=1
  • 如何手动求next数组，很难用文字解释清，多做几道题领会就很容易摸清规律了

数据结构学习笔记（3.栈，队列，数组 4.串）_第137张图片
代码实现

  • 有了next数组，我们就可以利用next数组，在代码里进行KMP算法匹配

数据结构学习笔记（3.栈，队列，数组 4.串）_第138张图片
举例，继续巩固一下如何求next数组

  • 固定模式：next 0不写，next 1写0，next 2写1
  • next数组的作用：当模式串的第j个字符匹配失败，从模式串的第next[j]个元素继续往后匹配

数据结构学习笔记（3.栈，队列，数组 4.串）_第139张图片

  • 如，5号不匹配，说明前面的元素已经匹配了；
  • 把模式串向右移，直到i这个位置前面的几个元素可以和模式串的头几个元素相匹配

数据结构学习笔记（3.栈，队列，数组 4.串）_第140张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第141张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第142张图片

  • 此时，出现了i的前面的元素与模式串的1号位匹配，因此我们可以直接从2号位开始匹配
  • 因此：当google的5号位失配，那么主串i不变，模式串跳到2号位继续匹配；next[5]=2
  • 得出google的next数组

数据结构学习笔记（3.栈，队列，数组 4.串）_第143张图片
开始使用next数组进行模式匹配

  • 当发现google的6号位不匹配，查找next数组发现next[6]=1；
  • 则主串i不变，模式串跳到1号位接着匹配

数据结构学习笔记（3.栈，队列，数组 4.串）_第144张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第145张图片

  • 结果发现跳到1号位之后，失配
  • 根据next跳到0号位
  • 我们有个特殊的判断，当发现j==0，则i和j同时+1，然后再匹配

数据结构学习笔记（3.栈，队列，数组 4.串）_第146张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第147张图片
求ababaa的的next数组
数据结构学习笔记（3.栈，队列，数组 4.串）_第148张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第149张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第150张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第151张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第152张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第153张图片
知识点小结
数据结构学习笔记（3.栈，队列，数组 4.串）_第154张图片

KMP算法–进一步优化

思考这种情况

  • 模式串3号不匹配，将会跳到1号匹配
  • 但是3号是a，1号也是a，所以1号也一定不匹配
  • 继续，1号失配，又要跳到0号位，继续后面的算法
  • 因此，当3号失配，我们可以直接跳到0号位

数据结构学习笔记（3.栈，队列，数组 4.串）_第155张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第156张图片
优化之后

  • 让next[3]=0
  • 当3号不匹配，直接跳到0号位

数据结构学习笔记（3.栈，队列，数组 4.串）_第157张图片
数据结构学习笔记（3.栈，队列，数组 4.串）_第158张图片
nextval数组

  • nextval本质上是对next数组的优化
  • 在使用KMP算法时，使用nextval数组替代next数组
  • 与主串没有关系，对于next数组以外的其他代码没有影响

手算求nextval数组

  • 先求出next数组
  • 开始从前往后写nextval数组，1号位固定写0
  • 当出现后面的字符与要跳到的前面的字符相同时，就把当前位置的值写成最前面的同字符的值
  • 如果当前字符与要跳到的前面字符不等，则保持不变

数据结构学习笔记（3.栈，队列，数组 4.串）_第159张图片
再练一个
在这里插入图片描述

你可能感兴趣的

按字母分类： ABCDEFGHIJKLMNOPQRSTUVWXYZ其他