第 5 章 串

1. 串的定义

是由零个或多个字符组成的有限序列，又名叫字符串。 一般记为s = "a1a1......an"(n >= 0),其中，s是串的名称，用双引号(有些书中也用单引号)括起来的字符序列是串的值，注意单引号不属于串的内容。a1(1 ≤ i ≤ n)可以是字母、数字或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，定义中谈到“有限”是指长度n是一个有限的数值。零个字符的串称为空串(null string)，它的长度为零，可以直接用两双引号““””表示，也可以用希腊字母“φ”来表示。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。

空格串，是只包含空格的串。注意它与空串的区别，空格串是由内容有长度的，而且可以不止一个空格。 子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。 子串在主串中的位置就是子串的第一个字符在主串中的序号。

2. 串的比较

事实上，串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。 对于两个串不相等时，如何判定它们的大小呢。这样定义： 给定两个串：s = "a1a2......an",t = "b1b2......bm"，当满足以下条件之一时，s < t。

1. n < m，且a1 = b1(i = 1,2,......,n)。
2. 存在某个k ≤ min(m,n)，使得ai = bi(i =1,2,....,k-1),ak <bk。

3. 串的抽象数据类型

因此，对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作。

对于不同的高级语言，其实对串的基本操作会有不同的定义方法，所以在用某个语言操作字符串时，需要先查看它的参考手册关于字符串的基本操作有哪些。不过还好，不同语言除方法名外，操作实质都是相类似的。

操作Index的实现算法

当中用到了StrLength、SubString、StrCompare等基本操作来实现。

4. 串的存储结构

串的存储结构与线性表相同，分为两种。

1. 串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。
既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值得终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了，其实这还是需要占用一个空间，何必呢。

刚才讲的串的顺序存储方式其实是有问题的，因为字符串的操作，比如两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度MaxSize。
于是对于串的顺序存储，有一些变化，串值得存储空间可在程序执行过程中动态分配而得。

2. 串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全

当然，这里一个结点存多少字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。 但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

5. 朴素的模式匹配算法

假设要从下面的主串S = "goodgoogle"中，找到T = "google"这个子串的位置。通常需要下面的步骤。

1. 主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是g。第一位匹配失败。

如图，其中竖直连线表示相等，闪电状弯折连线表示不等。

1. 主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图

1. 主串S第三位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败，如图

1. 主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败，如图

1. 主串S第五位开始，S与T，6个字母全匹配，匹配成功，如图

简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。 前面已经用串的其他操作实现了模式匹配的算法Index。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。注意假设主串S和要匹配的子串T的长度存在S[0]和T[0]中。实现代码如下： 分析一下，

6. KMP模式匹配算法

7. 总结