数据结构之串

数据结构之串

第四章_串

4.1 串的定义

串（string） 是由零个或多个字符组成的有限序列（就是我们常说的字符串）通常记为：

S = 'a₁ a₂ … aₙ'（n ≥ 0）

其中，S 是串名，单（双）引号括起的字符序列是串的值（单双引号取决于语言，比如python用单引号，C语言用双引号），每个 aᵢ 可以是字母、数字或其他字符，串中字符的个数 n 称为串的长度，当 n = 0 时，该串称为空串，用 ∅ 表示。

实际上串也是一种特殊的线性表，其特殊性体现在：串的元素类型限定为字符，且其基本运算主要是子串操作（如模式匹配），而不是一般线性表的插入和删除操作。 下面是子串相关的定义，用举例说明：

S="HelloWorld!"
T='iPhone 18 Pro Max?'

子串： 串中任意个连续的字符组成的子序列（可以等于主串）。 Eg: ‘iPhone’, ‘Pro M’ 是串 T 的子串 主串： 包含子串的串。 Eg: T 是子串 ‘iPhone’ 的主串 字符在主串中的位置： 字符在串中的序号。 Eg: ‘8’ 在 T 中的位置是 9 （注意这里指的是位序） 子串在主串中的位置： 子串的第一个字符在主串中的位置。 Eg: ‘11 Pro’ 在 T 中的位置为 8 （注意这里指的是位序）

4.2 串的基本操作

串的基本操作不做过多解释，基本和平常使用的C语言中string库中函数的作用相同，其函数规范如下：

• StrAssign (&T,chars): 赋值操作。把串 T 赋值为 chars。
• StrCopy (&T,S): 复制操作。由串 S 复制得到串 T。
• StrEmpty (S): 判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
• StrLength (S): 求串长。返回串 S 的元素个数。
• ClearString (&S): 清空操作。将 S 清为空串（逻辑上清空，并没有回收空间）。
• DestroyString (&S): 销毁串。将串 S 销毁（回收存储空间）。
• Concat (&T,S1,S2): 串联接。用 T 返回由 S1 和 S2 联接而成的新串
• SubString (&Sub,S,pos,len): 求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
• Index (S,T): 定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为 0。
• StrCompare (S,T): 比较操作。若 S>T，则返回值 > 0；若 S=T，则返回值 = 0；若 S < T，则返回值 < 0。

4.3 串的存储结构

既然是串是一种特殊的线性表，其实现方式我们自然能想到两种即顺序存储和链式存储：

4.3.1 串的顺序存储

我们在C语言中接触的字符串顺序存储是在其末尾加上一个’\0’作为字符串的结束标识，而在数据结构中串其实并不只有这一种顺序存储方式，下面介绍四种串的顺序存储方式： 方案一：使用一个单独的变量length进行存储数组长度 方案二：在下标为0的位置存储数组长度，缺点是ch[0]的空间只有1字节，故数组长度只能为0-255。优点是数组下标与位序相同。 方案三：末尾加上一个’\0’作为字符串的结束标识，缺点是知晓数组长度需要挨个遍历。 方案四： 综合方案一和方案二，之后的介绍默认都是这种方式。

4.3.2 串的链式存储

实现方式和链表类似，值得注意的是如何提高存储空间的密度的问题，如下图所示：

4.4 串的模式匹配

字符串的模式匹配就是在子串中查找与模式串（带搜索的字符串）完全相同的子串。

4.4.1 简单（朴素）模式匹配算法

简单模式匹配算法（Brute-Force 算法） 是一种暴力匹配算法。 其基本思想是：从主串的第一个字符开始，依次取出与模式串长度相等的子串，并将其与模式串逐字符比较；若比较失败，则主串起始位置后移一位，重新进行比较，直到匹配成功或主串扫描结束。 采用基本操作，实现代码如下：

#define MaxSize 255
typedef struct {
	char ch[MaxSize];
	int length;  //实际数组的长度，不是单纯的sizeof()
}SString;

int Index(SString S, SString T) {
	int n = S.length;
	int m = T.length;
	int i = 1;
	SString str; //用于暂存子串

	while (i <= n - m + 1) {  //满足条件的子串最多 n - m + 1 个
		SubString(str, S, i, m);
		if (!StrCompare(str, T)) {
			return i;
		}
		i++;
	}
	return 0; //不存在与其相同的子串
}

不采用基本操作，实现如下： 采用两个指针分别指向主串和模式串中的当前比较位置，逐字符进行比较；当字符相等时，两个指针同时后移，当失败时，主串指针回退到本次匹配起始位置的下一位，模式串指针重新置为起始位置。

#define MaxSize 255
typedef struct {
	char ch[MaxSize];
	int length;
}SString;

int Index(SString S, SString T) {
	int i = 1;
	int j = 1;
	while (i <= S.length && j <= T.length) {
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;  //把起点右移一位，再重新匹配，注意这里有点容易搞晕，画个图便知
			j = 1;
		}
	}

	if (j > T.length) {
		return i - j + 1;  //匹配成功，返回本次匹配起始位置
	}
	else {
		return 0;  //匹配失败
	}
}

4.4.2 KMP算法

KMP算法由D.E.Knuth，J.H.Morris，V.R.Pratt，提出，是对朴素模式匹配算法的一种优化算法，其算法的核心在于若已匹配成功的序列中有后缀正好是模式串的前缀，则可直接将模式串右滑到与这些字符对齐的位置， 无需像朴素模式匹配算法那样右滑一位从头开始。

首先我们需要明确以下三个概念：

• 前缀： 除最后一个字符外，字符串的所有头部子串。
• 后缀： 除第一个字符外，字符串中的所有尾部子串。
• 部分匹配值： 指前缀和后缀的最长相等前后缀长度。

比如 ‘ababa’ 的前缀为 {‘a’,‘ab’,‘aba’,‘abab’} ，后缀为 {‘a’,‘ba’,‘aba’,‘baba’} ，交集为 {‘a’,‘aba’} ‘aba’ 最长，故部分匹配值为 3 。

4.4.2.1 KMP总体算法实现

通过对匹配过程的观察可以发现，当匹配失败时，主串指针 i 无需回退，只需根据失配位置调整模式串指针 j。 由于模式串在不同位置失配时，j 的回退位置不同，因此需要对模式串进行预处理，构造 next 数组，用于指示失配时 j 的移动位置。 在此基础上，KMP 算法的整体实现便可得到简化。 得到 next 数组之后，总体实现代码如下：

#define MaxSize 255
typedef struct {
	char ch[MaxSize];
	int length;
}SString;

int Index_KMP(SString S, SString T,int next[]) {
	int i = 1;
	int j = 1;
	while (j <= T.length && i <= S.length) {
		if (j == 0 || T.ch[j] == S.ch[i]) {  //注意这里j-0的情况
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}

	if (j > T.length) {
		return i - j + 1; //匹配成功
	}
	return 0; //匹配失败
}

4.4.2.2 求next数组

next 数组含义：在第 j 位失配时，next[j] 表示模式串对应的下一次比较位置。next[j] 等于模式串前 j−1 个字符的最长相等前后缀长度加 1。

在考研中，手算求取 next 数组是重点，不难发现 next[0] 将其置空，next[1] 始终为 0，next[2] 始终为 1。 其方法和示例如下图所示： 实现代码如下：

void getNext(SString T, int next[]) {
    int j = 1, k = 0;
    next[1] = 0;

    while (j < T.length) {
        if (k == 0 || T.ch[j] == T.ch[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

4.4.2.3 KMP 算法改进

若出现如图所示的情况：当 j 位置的字符和其 next[j] 位置的字符相等时，当 j 位置的字符匹配失败，那么 next[j] 位置的字符也必然匹配失败。 那优化思路也显而易见，我们不断地将出现这种情况 next[j] 全部替换为 next[next[j]]，而将修正之后的这种数组称为 nextval 数组。计算 nextval 数组的示意和算法代码改动如下：

void get_nextval(SString T, int nextval[]) {
    int j = 1, k = 0;
    nextval[1] = 0;  // 初始化nextval数组的第一个位置
    while (j < T.length) {  // 遍历模式串T的每个字符
        if (k == 0 || T.ch[j] == T.ch[k]) {  // 匹配成功或k已经回到起点
            ++j; ++k;  // 同时移动j和k
            if (T.ch[j] != T.ch[k])  // 如果当前字符与k位置字符不相等
                nextval[j] = k;     // 直接将k赋值给nextval[j]
            else
                nextval[j] = nextval[k];  // 否则继承nextval[k]的值（优化）
        }
        else
            k = nextval[k];  // 匹配失败时，k回溯到nextval[k]的位置
    }
}

附言

在整个串的章节中，内容相对精简，但 KMP 算法是考研数据结构中难度较高、重要性排名前三的算法之一。初学者可能一开始难以理解 next / nextval 数组的构造逻辑，但只要通过多次手算模式串、绘制 next 表格、结合匹配示意图练习几遍，就能很快掌握算法核心思想与实现技巧。