小题形式考，比较简单，拿两个题来练手就会了
定义
字符串简称串
由零个或多个字符组成的有限序列
S是串名n称为串的长度，n=0称为空串
串中多个连续的字符组成的子序列称为该串的子串
串的逻辑结构和线性表极为相似，区别仅在于串的数据结构对象限定为字符集
线性表的基本操作通常要以单个元素为操作对象
串的基本操作通常以子串作为对象
存储结构
定长顺序存储
串长有两种表示方法：1.用一个额外的变量len来存放串的长度2.串值后面加一个不计入串长的结束标记字符”\0“
堆分配
用malloc()和free()函数来完成动态存储管理
块链存储
最后一个结点占不满时通常用”#“补上
模式匹配
简单模式匹配算法
最坏时间复杂度为O(mn)
推理m个字符,共n-m+1个子串，复杂度=O((n-m+1)m)=O(mn)文章来源：https://www.toymoban.com/news/detail-512627.html
KMP算法
时间复杂度是O(m+n)
主串i指针无须回溯，并从该位置开始继续比较
移动位数=以匹配的字符数-对应的部分匹配值
next[1]无脑写0，next[2]无脑写1
区分next数组和nextval数组
例题：
nextval指针位置不匹配，对应的元素就直接排除那个，串后移，后移的元素同指针位置不匹配的那个元素直接再后移文章来源地址https://www.toymoban.com/news/detail-512627.html
到了这里，关于408数据结构第四章的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
