当前位置: article > 正文

数据结构入门4-1（串、数组）_串的定长顺序结构s[0]与length长度的区别

作者：Cpp五条 | 2024-02-29 23:27:25

踩

串的定长顺序结构s[0]与length长度的区别

注

本笔记主要参考《数据结构（C语言版）》

字符串数据是计算机上的一种非数值处理的对象，字符串简称为串。

串是一种特殊的线性表，其特殊性在于：其数据元素是一个字符。所以，串是一种内容受限的线性表。因为字符串数据处理复杂，为了有效处理字符串，就需要设计合适的存储结构。

串的定义

串（string），又称字符串，是由零个或者多个字符组成的有限序列，一般记为：

一些概念：

子串：串中任意连续的字符组成的子序列；
主串：包含子串的串；
通常将字符在序列中的序号称为该字符在串中的位置（子串在主串中的位置则以字符的第一个字符在主串中的位置来表示）。
特殊的串：
1. 空串：包含零个字符（长度为 0）的串，用符号“∅”表示；
2. 空格串：由一个或多个空格（" "）组成的串。

例如：

假设a、b、c、d四个串：

其中：

a、b分别是c 和 d的子串；
a 在c 和 d中的位置都是 1；
b 在c 中的位置是 4，在d 中的位置是 5。

串相等的情况：当两个串的长度相等，并且各个对应位置的字符都相等时才相等。

串的类型定义、存储结构及其运算

串的抽象类型定义

串的逻辑结构与线性表相似，区别仅在于串的数据对象为字符的集合。

但是，串的基本操作却不同于线性表，因为线性表往往是针对 “单个元素” 进行操作，而串却要以 “串的整体” 作为操作对象。

串的抽象数据类型定义：

串的存储结构

串也存在着两种基本结构：顺序存储和链式存储（不过顺序存储因为存储效率高、算法较为方便，更受欢迎）。

1. 串的顺序存储

类似于线性表，串也使用一组地址连续的存储单元存储串值的字符序列。

串的定长顺序存储结构：


#define MAXLEN 255			//串的最大长度
 
typedef struct 
{
	char ch[MAXLEN + 1];	//使用一维数组存储串
	int length;				//记录串的当前长度
}SString;

这种定义方式在编译时就确定了串空间的大小。但是，在多数情况下，串的操作是以串的整体形式作为对象，而串变量之间的长度往往相差很大，这就会导致（栈区）空间的浪费。

相比于上述这种声明方式，在程序运行阶段进行空间的分配就更加合理，即在堆区（Heap）进行空间的动态开辟。

串的堆式顺序存储结构：


typedef struct {
	char* ch;		//若是非空串，则按串长分配存储区，否则ch为空指针（NULL）
	int length;		//串的当前长度
}HString;

2. 串的链式存储

顺序串的插入和删除操作存在不便，为此，可能需要移动大量的字符。为了处理该问题，可采用单链表的方式存储串。

由于串结构的特殊性（即结构中的每个元素都是一个字符），在实际通过链表存储串的值时，存在“节点大小”的问题：在一个节点中可以存储一个字符，或者存储多个字符。

（除了上述出现的头指针外，还可以设置尾指针指向链表的最后一个节点。）

串的链式存储结构：


#define CHUNKSISE 80	//块的大小由用户决定
typedef struct Chunk 
{
	char ch[CHUNKSISE];
	struct Chunk* next;
}Chunk;
typedef struct 
{
	Chunk* head, tail;	//串的头指针head和尾指针tail
	int length;			//串的当前长度
}LString;

一般而言，在链式存储结构中，需要考虑：

串值的存储密度（节点大小）。若节点大小是1，则运算处理方便，但相对的，存储占用量就会大；
串的字符集的大小。字符集小，则字符的机内编码就短，则会影响存储方式的选择。

串值的链式存储结构在一些特定的操作（如联接操作）中，会较为方便，但总体而言，占用存储量大，操作复杂，不如顺序存储结构灵活。

串的模式匹配算法（定长存储结构下）

子串的定位运算通常被称为串的模式匹配或者串匹配。通常，串的模式匹配设有两个字符串S和T：

S为主串，也称为正文串；
T为子串，也称为模式。

在主串S中查找与子串T匹配的子串，如果匹配成功，则返回子串的第一个字符在主串S中出现的位置。

接下来介绍较为著名的模式匹配算法。

1. BF算法

||| BF（Brute-Force）算法，优点：简单直观。

【代码】

前置条件：① T非空，② 1 ≤ pos ≤ S.length 。

为了方便描述算法，规定：数组的存储从下标为[1]处开始，下标为[0]处闲置。


int Index_BF(SString S, SString T, int pos)
{//返回T在S中第pos个字符开始，第一次出现的位置。若不存在，返回值为0
	int i = pos;
	int j = 1;
 
	while (i <= S.length && j <= T.length)	//比较，直至两个串均比较到末尾
	{
		if (S.ch[i] == T.ch[j])
		{
			++i;
			++j;
		}					//若当前字符相等，继续比较下面的字符
		else
		{
			i = i - j + 2;	//数组从下标为[1]处开始比较，故此处 +2
			j = 1;
		}					//若当前字符不相等，则指针后退继续比较
	}
 
	if (i > T.length)		//若匹配成功
		return i - T.length;
	else
		return 0;
}

上述函数使用的是字符串的顺序存储结构，所以可以不用调用其他串操作的函数。

【分析】

BF算法较好理解：将模式T内的字符与主串S中的字符一一比较，若比较失败（出现某个字符无法匹配的情况），则将主串S中的下一个字符作为开头，重新进行比较。

一般来讲，BF算法会有两种极端情况：

（1）最好的情况：每趟不成功的匹配都发生在模式串T的第一个字符与主串S中相应字符的比较。

若设主串S的长度为n，模式T的长度为m。且：

在第一次比较成功前，匹配失败的次数为：i - 1；
在第 i 次比较时，成功匹配；

那么总的比较次数将会是 i - 1 + m 。

一般而言，对时间复杂度的判断参考的是平均时间复杂度。而在上述条件下，只有pos（即比较中主串的起始位置）是未知的，也就是说，为了得到平均时间复杂度，需要考虑pos所有的取值。

而pos的取值并不难以判断，从主串和子串的长度可知：1 ≤ pos ≤ n - m + 1。假定在这 n - m + 1 个主串的起始位置上匹配成功的概率相等，则在最好的情况下，匹配成功的平均比较次数为

$\sum_{i=1}^{n-m+1}(p_{i}\cdot (i-1+m))=\frac{1}{n-m+1}\sum_{i=1}^{n-m+1}i-1+m=\frac{1}{2}(n+m)$

故此时的平均时间复杂度为O(n + m)。

（2）最坏的情况：每趟不成功的匹配都发生在模式串的最后一个字符与住主串中相应字符的比较。

依旧和上面一样，设主串S的长度为n，模式T的长度为m。且：

在子串与主串成功匹配之前，共进行了 i - 1 趟匹配；
每次匹配比较m个字符；
第 i 次匹配时子串匹配成功。

因为第 i 次匹配成功时也进行了 m 次比较，故总的比较次数为 i × m 。因为pos的取值范围不变（依旧是1 ≤ pos ≤ n - m + 1），所以在最坏的情况下，匹配成功的平均比较次数为

$\sum_{i=1}^{n-m+1}(p_{i}\cdot (i\cdot m))=\frac{1}{n-m+1}\sum_{i=1}^{n-m+1}i\cdot m=\frac{1}{2}(m\cdot n - m^{2} + 2)$

故此时的平均时间复杂度为O(n × m)。

由上述可知，BF算法的优点是直观简明，而缺点是时间复杂度较高且不稳定。相比之下，下面的KMP算法的时间复杂度就较低。

2 - 1. KMP算法 - 分析部分

算法主体部分

该算法的名称来自三位设计了该算法的前辈。此算法可以在O(n + m)的时间量级上完成串的模式匹配操作。比起BF算法，KMP算法更加接近人在处理串匹配时的情况：

假设存在主串S与子串T，并存在指针 s 和 t 分别指向两个串。

请尝试思考，如果要求我们从头开始寻找S中出现的第一个T，应该怎么做？

首先是第一个字符'A'相同；
然后是第二个字符'B'相同；
那么再然后呢？

当我们发现了无法匹配的字符'A'与'C'，我们仅需要回溯子串T的指针 t ，直到指针t指向合适的位置，就可以进行再一次的匹配：

这就是这种模式匹配的基本思路了。当然，上述讲述的部分还未涉及该算法最难懂的部分，如果仔细观察上述推导中的子串，能够发现：上述子串中的字符是不重复的。如果这样考虑算法，显然是不充分的。

为什么呢？假设：

在上述这种子串中，"X"重复了两次（即 T 包括了两个相同的子串"X"）。当该主串和子串发生第一次匹配失败时，情况应该是：

现在存在的问题是：指针t应该回溯到哪个位置？从上帝视角可以轻易发现，如果把指针t往回回溯2个元素，S 和 T 就会匹配：

但在真实操作中，计算机无法通过“观察”这种方式发现指针t的移动方式。为了达到这种效果，就需要为计算机设计相应的算法。由此，就引出了主串T的next函数。

函数get_next( )部分

||| get_next函数（用以获得next值的函数）的定义：

------

在接触该函数前，需要先理解该函数的运行思路。假设主串S和子串T：

此时，按照上面的理解，我们如果将T向右移动 5个元素，就可以直接完成子串与主串的匹配，但这要怎么告诉计算机？

为了达成目的，可以近似地认为：子串T除了下标之外，还存在名为next值的属性，这个属性对应的就是子串T的指针需要移动到的位置。而程序就是通过next值寻找到目标字符的。

对上述 T 的第二个字符'A'而言，其对应的next值就是 1，即第一个字符'A'所在的位置；
对第三个字符'A'而言，其对应第二个字符'A'所在的位置；
……

（注意：此处next值其实存在可优化空间，但当前并不要紧。这些问题会在最后进行讨论。）

以此类推，可以得到前几个字符的next值：

如果就这样往下推，就会发现一个问题，字符'C'该何去何从？

当字符'B'处发生比较失败，可以说：因为在此之前没有字符'B'的存在，所以T应该向前一个元素，找到与'B'不同的最近的'A'。但同样的逻辑却不能适用于当前的字符'C'，因为'C'之前并不存在相同的子串。

其实，上述的字符'B'的next值之所以是3，不仅仅是因为字符'B'当前的唯一性，也因为在'B'之前存在着相同的子串"AA"。

现在，回到更早之前的问题：

在KMP算法中，区分一个字符依靠的不仅仅是该字符本身，更重要的是其之前的子串。在上述的移动中，认为之所以能够移动到目标位置，依靠的是其之前已经完成识别的相同子串。因此，上述的移动才能成立。

而 "AAABC" 中的字符'C'，因为其之前没有相同子串，所以next值只能被设置为1，即回到 T 的开头，进行重新寻找。

------

||| next[ ]的定义：

k的定义：发生匹配失败时，子串中重新进行匹配的字符位置。

||| next[ j ]：

j 的定义：（匹配失败发生时）当前子串T中进行匹配的字符的位置；
next的功能：表明当匹配失败发生时，子串T中重新和主串S进行匹配的字符的位置。

但next函数的功能要如何实现呢？假设：

主串长度为 n ；
子串长度为 m；
发生匹配失败时，子串中重新进行匹配的字符位置为 k （k < j）。

在上图中，存在着如下的关系式：

由上可知，当形如子串T的状况出现时，仅需将子串向右移动直至主串的第i个字符与子串的第k个字符对齐。此时，子串的前 k - 1 个字符的子串和子串中第i个字符之前的长度为 k - 1 的子串相等。

此时可能存在两种情况：

此时存在 next[ j + 1 ] = k + 1 ，即

此时求next值的问题就是一个模式匹配的问题，T 即是主串，又是子串，而字符'B'就是需要被匹配的字符（即在 T 中寻找能够与下标为j 的字符'B'相匹配的字符）。而在此之前，已经得出结论：

现在的问题是：既然 k 对应位置上的字符已经比较失败，那么接下来应该匹配哪个字符？

答案是将 next[ k ] 上的字符与 j 上的字符"B"进行比较（因为在位置 j 之前的所有字符已经拥有了它们的 next[] 值，可以直接使用）。

① 若比较成功，类似于：

此时存在 next[ j + 1] = k' + 1，即

② 若匹配没有成功，这需要继续寻找位置在 next[ k' ] 上的字符，直到匹配成功或者无法找到匹配字符，当后者发生时，有：

通过上述记叙方式，可以得到：

2 - 2. KMP算法 - 代码部分

所使用串的结构：


#define MAXLEN 255			//串的最大长度
 
typedef struct
{
	char ch[MAXLEN + 1];	//使用一维数组存储串
	int length;				//记录串的当前长度
}SString;

函数 Index-KMP( )


int Index_KMP(SString S, SString T, int pos)
{//利用子串T的get_next函数求出T在主串S中第pos个字符之后的位置
 //（T非空，1 ≤ pos ≤ S.length）
	int i = pos;
	int j = 1;
 
	int next[100] = { 0 };					//类型及大小可以自行定义，此处进行简单处理
	get_next(T, next);
 
	while (i <= S.length && j <= T.length)	//当两个串均比较到串尾（实际上此处多移动一位，是为了后面方便计算）
	{
		if (j == 0 || S.ch[i] == T.ch[j])	//当前字符匹配成功
		{
			++i;
			++j;							//指针向后移动
		}
		else
			j = next[j];					//寻找新的字符进行匹配
	}
 
	if (j >= T.length)						//匹配成功（判断条件会因为使用的串的结构不同而发生变化）
		return i - T.length;
	else									//匹配失败
		return 0;
}

函数 get_next( )


void get_next(SString T, int next[])
{//求模式串T的next函数值并存入数组next
	int i = 1;
	int j = 0;
	next[1] = 0;
 
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])	//当前字符匹配成功
		{
			++i;
			++j;							//向后移动指针
			next[i] = j;					//进行相应的next值赋值
		}
		else
			j = next[j];					//寻找新的可匹配字符
	}
}

函数get_nextval( ) —— get_next( )的优化

【分析】

如果仔细思考，就会发现上述定义的next函数是有缺点的。假设：

如果使用上述的next函数，主串T的next值就会如下所示：

这意味着为了获得能够与 S当前字符匹配的字符，需要将T一个元素一个元素地向右移动，每移动一个元素就要比较一次，这很明显是没有必要的（子串T的前4个字符相同，都是字符'A'）。

为此，就需要更新next函数，使其能够满足：当字符相同时，能够令子串T的向右移动能够直接跳过相同字符，抵达目标位置。即：

例如：

【代码】


void get_nextval(SString T, int nextval[])
{//将子串T的next函数值存入数组nextval中
	int i = 1;
	int j = 0;
	nextval[1] = 0;
 
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i;
			++j;
			if (T.ch[i] != T.ch[j])		//当前比较的两个字符不同时
				nextval[i] = j;
			else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}