4.1 串的定义与存储

串的基本概念与操作，定长顺序存储、堆分配存储和块链存储，以及朴素模式匹配算法。

串的定义

• 子串：串中任意多个连续的字符组成的子序列；包含子串的串称为主串。
• 某个字符在串中的序号称为该字符在串中的位置；子串在主串中的位置以子串的第一个字符在主串中的位置来表示。
• 两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。
• 由一个或多个空格组成的串称为空格串（注意：空格串不是空串）。

例如 $S = \text{'data structure'}$，子串 $\text{'struct'}$ 在 $S$ 中的位置是 6。

基本操作

最小操作子集：串赋值 StrAssign、串比较 StrCompare、求串长 StrLength、串联接 Concat 和求子串 SubString。其他操作均可在该子集上实现。

串的存储结构

定长顺序存储

用一组地址连续的存储单元存储串值的字符序列，为每个串变量分配一个固定长度的存储区。

#define MAXLEN 255          // 预定义最大串长
typedef struct {
    char ch[MAXLEN];        // 每个分量存储一个字符
    int length;             // 串的实际长度
} SString;

超过预定义长度的串值会被舍去，称为截断。串长有两种表示方法：一是如上定义用额外变量 length 存放；二是在串值后面加一个不计入串长的结束标记 '\0'（C 语言风格），此时串长为隐含值。

堆分配存储

仍以一组地址连续的存储单元存放串值，但存储空间是在程序执行过程中动态分配得到的（malloc / free）。

typedef struct {
    char *ch;               // 按串长分配存储区，ch 指向串的基地址
    int length;
} HString;

块链存储

类似于线性表的链式存储，由于串的特殊性（每个元素只有一个字符），每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。最后一个结点占不满时通常用 # 补上。

朴素模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。

朴素（暴力）算法的思想：从主串的第一个字符起，与模式串的第一个字符比较，若相等则继续逐个比较后续字符；否则从主串的下一个字符起，重新与模式串的第一个字符比较……直到模式串中每个字符依次与主串中一个连续的字符序列相等，则匹配成功。

1int Index(SString S, SString T) {
2    int i = 1, j = 1;
3    while (i <= S.length && j <= T.length) {
4        if (S.ch[i] == T.ch[j]) {
5            ++i; ++j;            // 继续比较后继字符
6        } else {
7            i = i - j + 2;       // 主串指针回溯
8            j = 1;               // 模式串从头开始
9        }
10    }
11    if (j > T.length) return i - T.length;
12    else return 0;
13}

失配时，主串指针 i 回溯到 i - j + 2（本趟起始位置的下一个），模式串指针 j 回到 1。

朴素算法的低效之处在于：已经匹配过的字符信息被丢弃了，主串指针反复回溯。下一课的 KMP 算法正是针对这一点进行改进。

即时练习