请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

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

2023-07-13

四、串

串的定义

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

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

串的基本操作:

image.png

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

串的存储结构

顺序存储

image.png

//顺序存储
#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];
	}
}

主要参考:王道考研课程
后续会持续更新考研408部分的学习笔记,欢迎关注。
github仓库(含所有相关源码):408数据结构笔记

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部