大话数据结构(五)串(朴素的模式匹配算法、KMP模式匹配算法)
串
串是由零个或多个字符组成的有限序列,又名叫字符串
1 串的比较
给定两个串,,当满足以下条件之一时,。
- ,且。例如,,就有。
- 存在某个,使得,。例如,,因为两串前4个字母均相同,而两串第5个字母(值), 的ASCII码是101,而 的ASCII码是121,显然 ,所以。
2 串的抽象数据类型
串的逻辑结构与线性表相似,不同之处在于串针对的是字符集,每个元素都是字符。此外,串的基本操作与线性表有很大差别。线性表关注的是单个元素的操作,串中更多则是查找子串位置、得到指定位置子串、替换子串等操作。
3串的存储结构
3.1 串的顺序存储结构
用一组地址连续的存储单元来存储串中的字符序列。一般用定长数组为每个定义的串变量分配一个固定长度的存储区。这样的存储方式存在问题,因为定长,在字符串操作时候,比如连接、插入新串、替换等操作时,都可能使串序列的长度超过了数组的长度MaxSize。
3.2 串的链式存储结构
与线性表相似,但因为串中每个元素都是一个字符,如果用链表存储串值,一个结点对应一个字符,就会存在很大的空间浪费。因此,一个结点可以存放一个字符,可以考虑存放多个字符,最后一个结点若是未被占满,可用“#”或其他非串值字符补全,如图。
当然,一个结点存多少个字符才合适显得很重要,这会影响串处理的效率,要根据实际情况取舍。总的来说,串的链式存储结构除了在连接串与串操作时有一定方便之外,不如顺序存储灵活,性能也不如顺序存储结构好。
4 朴素的模式匹配算法
5 KMP模式匹配算法
6 KMP改进
以下内容移步本博客其他文章