【数据结构】24王道考研笔记——串

四、串

串的定义

串（字符串）是由零个或多个字符组成的有限序列。

子串：串中任意个连续的字符组成的子序列
主串：包含子串的串
字符在主串中的位置：字符在串中的序号
子串在主串中的位置：子串的第一个字符在主串中的位置

串的基本操作：

其中串执行比较操作时，从第一个字符开始往后依次对比，先出现更大字符的串就更大，长串的前缀与短串相同时，长串更大，只有两个串完全相同时，才相等。

串的存储结构

顺序存储

//顺序存储
#define MAXLEN 255 //预定义最大串长为255
//静态数组
typedef struct {
	char ch[MAXLEN]; //每个分量存储一个字符
	int length; //串的实际长度
}SString;
//动态数组
typedef struct {
	char* ch; //按串长分配存储区，ch指向串的基地址
	int length; //串的长度
}HString;
//初始化
	HString S;
	S.ch = (char*)malloc(MAXLEN * sizeof(char));
	S.length = 0;
	return 0;

求子串

//求子串，用Sub返回串S的第pos个字符起长度为len的子串
bool SubString(SString& Sub, SString S, int pos, int len)
{
	//子串范围越界
	if (pos + len - 1 > S.length) return false;
	for (int i = pos; i < pos + len; i++)
		Sub.ch[i - pos + 1] = S.ch[i];
	Sub.length = len;
	return true;
}

比较操作

//比较操作
int StrCompare(SString S, SString T)
{
	for (int i = 1; i <= S.length && i <= T.length; i++)
	{
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	}
	//扫描过的所有字符都相同，则长度长的串更大
	return S.length - T.length;
}

定位操作

//比较操作
int StrCompare(SString S, SString T)
{
	for (int i = 1; i <= S.length && i <= T.length; i++)
	{
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	}
	//扫描过的所有字符都相同，则长度长的串更大
	return S.length - T.length;
}

链式存储

//链式存储
typedef struct StringNode {
	char ch; //每个结点存1个字符
	struct StringNode* next;
}StringNode,*String;
//每个结点存多个字符
typedef struct StringNode2 {
	char ch[4]; //每个结点存四个字符
	struct StringNode2* next;
}StringNode2,*String2;

串的模式匹配

朴素模式匹配

时间复杂度为O(mn)

//朴素模式匹配算法
int Index(SString S, SString T)
{
	int i = 1, 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 - T.length;
	else return 0;
}

KMP算法

先利用模式串T求出next数组，利用next数组进行匹配，使得主串指针不回溯。时间复杂度为O(m+n)

//KMP算法
int Index_KMP(SString S, SString T, int next[])
{
	int i = 1, j = 1;
	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;
}

求next数组

//求next数组
void get_next(SString T, int next[])
{
	int i = 1, j = 0;
	next[1] = 0;//初始化
	while (i, T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i; ++j;
			next[i] = j;//若pi=pj,则next[j+1]=next[j]+1
		}
		else
			j = next[j];
	}
}

改良后求nextval数组

//改良后的nextval数组
void get_nextval(SString T, int nextval[])
{
	int i = 1, 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];
	}
}