第5章 串

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

串的比较

给定两个串：s= “a₁a₂……a_n“, t= “b₁b₂……b_m“, 当满足以下条件之一时，s<t。

1. n<m，且a_i=b_i（i=1, 2, ……, n）。
2. 存在某个k<min(m, n), 使得a_i=b_i（i=1，2，……，k-1）a_k<b_k

串的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ADT 串（string）
Data
  串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
  StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
  StrCopy(T,S):串S存在，由串复制得串T。
  ClearString(S):串S存在，将串清空。
  StringEmpty(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联接而成的新串。
  SubString(Sub,S,pos,len):串S存在，1<=pos<=StrLength(S)，且0<=len<=StrLength(S)-pos+1,用Sub返回串S的第pos个字符长度为len的子串。
  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相等的不重叠的子串。
  StrInsert(S,pos,T):串S和T存在，1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T。
  StrDelete(S,pos,len):串S存在，1<=pos<=StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT

Index 的实现算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0 */
int Index(String S, String T, int pos)
{
  int n,m,i;
  String sub;
  if (pos > 0)
  {
    n = StrLength(S);
    m = StrLength(T);
    i = pos;
    while ( i <= n-m+1)
    {
      SubString(sub,S,i,m); /* 取主串第i个位置 长度与T相等子串给sub */
      if (StrCompare(sub,T) != 0)  /* 如果两串不相等 */
        ++i;
      else  /* 如果两串相等 */
        return i;
    }
  }
  return 0; /* 若无子串与T相等，返回0 */
}

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

串的存储结构

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般使用定长数组来定义。

串的链式存储结构

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

串的链式存储结构除了在链接串与串操作时有一定方便外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

朴素的模式匹配算法

子串的定位操作通常称做串的模式匹配。
假设我们要从下面的主串S=“goodgoogle”中，找到T=“google这个子串的位置”。
简单的来说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。
最好的情况，时间复杂度为O(1)。
稍差一些的情况，时间复杂度为O(n+m)，其中n为主串长度，m为要匹配的子串长度。
根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。

KMP模式匹配算法

D.E.Knuth、J.H.Morris 和 V.R.Pratt 发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称 KMP 算法。