报名网站建设,做网站的人 优帮云,搞定在线图片编辑,上海企业免费建站这里写目录标题 串定义案例引用串的类型定义以及存储结构抽象类型定义存储结构(顺序表较为常用)顺序存储结构链式存储结构 串的模式匹配算法#xff08;查找主串中是否有某个字串#xff09;BF算法KMP算法设计思想对字串的回溯进行了优化代码对next【j】进行优化 数组类型一维… 这里写目录标题 串定义案例引用串的类型定义以及存储结构抽象类型定义存储结构(顺序表较为常用)顺序存储结构链式存储结构 串的模式匹配算法查找主串中是否有某个字串BF算法KMP算法设计思想对字串的回溯进行了优化代码对next【j】进行优化 数组类型一维数组二维数组 抽象类型定义顺序存储结构已知首元地址求某个元素的地址该元素第一个字节的地址 特殊矩阵的压缩存储对称矩阵三角矩阵带状矩阵稀疏矩阵顺序结构链式结构 广义表简介性质基本运算案例 串
定义 也叫字符串
案例引用 串的类型定义以及存储结构
抽象类型定义 存储结构(顺序表较为常用) 顺序存储结构 为了方便一些操作通常串的数组的第一个位置不放元素而是从ch【1】开始存放元素
链式存储结构 如果一个结点的数据域只放一个字符那么会导致存储密度异常的底解决这个问题在数据域放更多的字符数据 上面的结构体定义结点结构下面定义链表结构
可以得知对于好多功能的链式表示都是定义两个结构一个是结点、一个是链表自己 定义链表时先定义第二个结构体的对象创建出链表如果要创建新的结点那么要用到第一个结构体进行插入即可
串的模式匹配算法查找主串中是否有某个字串
BF算法 如果匹配失败那么需要对两个串的下标进行回溯从而重新比较下一组
对于主串先回溯到原始位置ii-(j-1) 因为对于串的第一个下标都是1所以j移动的格数是j-1而i与j同步移动所以回溯到原始位置是i-(j-1) 之后因为要进行下一组比较所以i回到原始位置之后还需要后移一位所以ii-(j-1)1
对于字串直接回到第一个位置即可j1 由于第一个位置下标为1方便了这里字串位置的计算直接i-T.length即可 while循换条件当主串的下标或者字串的下标有一个出界那就代表匹配结束最后要么匹配成功jT.length要么匹配失败循环继续的条件是二者都没有出界一旦有一个出界那么结果为假那么整体为假一假则假 最好情况是o1 最坏情况是on*m
综合平均on*m
KMP算法
设计思想 对字串的回溯进行了优化 当字串第j个元素失配需要回溯到的下标位置放入数组next【j】中
第一个元素失配那么需要回溯到0但是由于没有0位置所以实际上的操作是ij仍然是1 之后的元素 想看是否满足其前面的首位子集是否相等例如j5时前四个元素先看1、4二者相等所以k-11那么k2之后再看12、34再看123、234如果有更大的k那么就取最大的k为最终值注意不能全部包含 例如1234这样是不可以的
如果这种情况也不满足就是其他情况next【j】1
代码
kmp算法 next【j】的算法
对next【j】进行优化 按照上述标黄的语句进行分析即可开头两位一般是01 或者00 之后 如果回溯位置的元素与自身相同那么val值与回溯位置的next值一样如果不同 那么仍然是自己的next值 最后要注意标黄的第四种情况也就是如果相同每次要判断到第一位为止
总结来说 不同为自身相同做替换不同则停止相同则到底
改进后的next【j】
数组
类型
一维数组 二维数组 二维数组可以是非线性结构也可以是特殊的线性结构
特殊的线性结构将一行看成一个线性结构该行的每个元素是一个列向量 分开定义实际上就是对特殊的线性结构的代码解释 数组一旦定义那么长度固定所以一般只是做取元素和修改元素操作
抽象类型定义 顺序存储结构 因为内存单元只能是线性的但是数组有多维所以要想办法将多维关系映射到一维关系接下来通过找指定元素的地址来反映这个关系接下来就是解决这个问题
已知首元地址求某个元素的地址该元素第一个字节的地址
一维数组
二维数组 也就是第一维下标*列数第二维下标*一个元素所占字节数首元地址目标元素的地址 本质上是要求该元素的前面有几个元素但是因为下标都是从0开始所以根据数学关系下标的数就是该元素之前有几个元素的多少
三维数组
n维
案例 注意这里假设元素占用一个空间先利用第一个条件求出列数之后利用公式求出答案
特殊矩阵的压缩存储 对称矩阵 只存上三角或者下三角元素位置i*i-1/2j 这就是目标元素前面的元素个数
三角矩阵 带状矩阵 稀疏矩阵
顺序结构 链式结构 每行每列都有许多头指针负责该行或者该列
每个非零元素都有一个结点该结点包括行数、列数、值、指向下方的结点、指向右方的结点
广义表
简介 这里注意 表尾1.是除了第一个元素之外的所有元素组成的表 2.一定是一个表所以求表尾第一步先写一个括号之后看去掉表头之后剩什么就直接填入括号里 例如 第二题 表头是第一个元素第一个元素就是一个空括号 所以就是 表尾 先写一个空括号之后看除去表头之后 什么也没有了 就是空所以 括号里什么都不写 所以还是
第三题 表头a 表尾先写一个空括号之后将除去表头的剩下的元素填入空表中也就是bc
性质 基本运算 案例 循环m模式串的长度次就可以将所有可能的情况都取得了
