数据结构（五）：串

串的概念

• 串（String）是由零个或多个字符组成的有限序列，又名字符串，一般记为 s = "a1a2...an"
• 串中任意个数的连续字符组成的子序列称之为该串的子串，例如 "over" 是 "lover" 的子串

串的比较

• "silly"、"stypid" 这样的两个字符串，第一个字母都是 "s"，因此不存在差异，第二个字母由于 "i" 比 "t" 靠前，所以 "i"<"t"，于是我们说 "silly" < "stypid"
• 串的比较是通过组成串的字符之间的编码来进行的，而字符编码是指字符在对应字符集中的序号
• 所以两个字符串是否相等，必须是它们串的长度以及每个字符豆相等时，才算是相等
• 对于不相等的两个串，例如 s = "a1a2...an"，t = "b1b2...bm"，当满足以下条件之一时，s < t
  • n < m，且 ai = bi (i=1,2.....,n)
  • 当 s = "happen",t = "happy" 因为两串前 4 哥字母均相同，而第五个字母 e 的 ASCII 码是 101，y 的 ASCII 码是 121，e < y，所以 s < t

串的抽象数据类型

• 串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，所有元素都是字符，因此串的基本操作与线性表有很大差别
• 线性表更关注的是单个元素的操作，比如增删查一个元素，串中更多的是查找子串的位置、替换等操作
• Data（数据元素）：串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
• 基本操作

方法	描述
StrAssign(T,*chars)	生成一个其值等于字符串常量 chars 的串 T
StrCopy(T,S)	串 S 存在，由串 S 复制得串 T
ClearString(S)	串 S 存在，将串清空
StringEmpty(S)	若串 S 为空，返回 true、否则 false
StrLength(S)	返回串 S 元素个数，即长度
StrCompare(S,T)	若 S > T 返回值 > 0，若 S=T 返回 0，若 S < T 返回值 < 0
Concat(T,S1,S2)	用 T 返回由 S1 和 S2 联接而成的新串
Index(S,T,pos)	若 S 和 T 存在，T 是非空串，1 <= pos <= StrLength(S)，若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中第 pos 哥字符之后第一次出现的位置，否则返回 0
Replace(S,T,V)	串 S、T 和 V 存在，T 是非空串，用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串
StrDelete(S,pos,len)	串 S 存在，1 <= pos <= StrLength(S) - len + 1，从串 S 中删除第 pos 个字符起长度为 len 的子串
SubString(Sub,S,pos,len)	串 s 存在，1 <= pos <= StrLength(S)，且 0 <= len <= StrLength(S) - pos +1 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串

串的存储

顺序存储

• 串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符串序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区
• 一般可以将实际的串长度值保存在数组 0 下标位置，有的书中也会定义存储在数组的最后一个下标位置
• 但有的编程语言觉得存个数字占空间麻烦，它规定在串值后面加一个结束标记，例如 "\0" ，这个时候如果想知道串长度，就需要遍历计算，但这其实还是需要占一个空间，何必呢？
• 顺序存储方式存在些问题，比如两串的连接、新串的插入、以及字符串的替换都可能使得串序列长度超过数组长度

链式存储

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

y4ABu.png

• 此时一个结点存放多少个字符才合适变的很重要，这会直接影响串处理的效率，需根据实际情况做出选择
• 但串的链式存储总的来说不如顺序存储灵活，性能也不如顺序存储结构好

朴素的模式匹配算法

• 子串的定位操作通常称作串的模式匹配，假设要从主串 S = "goodgoogle" 中找到 T = "google" 子串为止，通常需要下面步骤：
  1. 主串 S 第一位开始，S 与 T 前三个字母都匹配成功，但 S 第四个字母匹配失败
  2. 主串 S 第二、三、四位开始，匹配失败
  3. 主串 S 第五位位开始，6 个字母全匹配成功
• 简单的来说就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配，对主串做大循环，内个字符开头做 T 的长度小循环，直到匹配成功或全部遍历完为止

效率问题

• 最好的情况就是一开始就匹配成功，此时时间复杂度为 O(1)
• 最差的时间复杂度为 O((n-m+1)*m)，其中 n 是主串长度，m 为要匹配的子串长度
• 朴素的模式匹配法效率十分低效

KMP 模式匹配算法

Ptj9X.png

• 如果主串 S = "abcdefgab"、T = "abcdex" 那么如果用前面的朴素算法进行匹配，那么流程如下，在流程 ②③④⑤⑥ 中，首字符与子串 T 首字符均不等
• 这似乎也是理所当然，"abcdex" 首字符 "a" 与后面的串 "bcdex" 任意一个字符都不相等，既然 "a" 不与自己后面的子串中任一字符相等，那么对于 ① 来说前 5 位字符分别相等，意味着子串 T 的首字符 "a" 不可能与 S 串的第 2 位到第 5 位的字符相等，因此 ②③④⑤⑥ 是多余的
• 如果我们知道 T 串中首字符 "a" 与 T 中后面的字符均不相等（这是前提），而 T 串的第二位的 "b" 与 S 串中第二位的 "b" 相等，那么意味着 T 串中首字符 "a" 与 S 串中第二位 "b" 是不需要判断也知道它们不可能相等了，所以流程 ② 可以省略
• 同样道理，在知道 T 串中首字符 "a" 与后面的字符不相等的前提下，T 串的 "a" 与 S 串后面的 "c"、"d"、"e" 也可以在流程 ① 之后确定不相等，所以流程 ②③④⑤⑥ 没有必要，只保留 ①⑥ 即可
• 之所以保留 ⑥ 是因为在 ① 中 T [6] ≠ S[6]，尽管我们知道 T[1] ≠ T[6]，但不能断定 T[1] 一定不等于 S[6]

PtGOl.png

• 如果 T 串后面也含有首字符 "a" 怎么办？
• 假设 S = "abcabcabc"、T = "abcabx"，前 5 个字符完全相等，第 6 个字符不等，此时根据刚才经验，T 的首字符 "a" 与 T 的第二、三位字符 "b"、"c" 均不等，所以不需要做判断，因此 ②③ 是多余的
• 因为 T 的首位 "a" 与第四位 "a" 相等，第二位 "b" 与第五位 "b" 相等，而在 ① 时，第四位 "a" 与第五位 "b" 已经与主串 S 中相应位置比较过了，是相等的，因此可以判断，T 的首字符 "a"、第二位的 "b" 与 S 的第四位和第五位字符也不需要比较了，所以 ④⑤ 也可以省略