天天看点
返回

第四章：串

4.1串的定义和基本操作

串，即字符串，是由零个或多个字符 组成的有限 序列，一般记为：S=‘a1a2…an’；

其中S是串名，单引号内是串的值；

ai可以是字母、数字或其他字符；

串中的字符个数n称为串的长度 ，n=0时的串称为空串。

子串：串中任意个连续的字符组成的子序列。

主串：包含子串的串。

字符在主串中的位置：字符在串中的序号。

子串在主串中的位置：子串的第一个字符在串中的序号。

空串VS空格串：M=’’ VS N=’ ’ 空格占字节

串是一种特殊的线性表，数据元素之间成线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以字串为操作对象

基本操作：

假设有串T = “”，S = “iPhone 11 Pro Max?”，W = “Pro”

  • StrAssign(&T,chars)：赋值操作，把串T赋值为chars
  • StrCopy(&T,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

字符集编码拓展：

任何数据存到计算机中一定是二进制数

需要确定一个字符和二进制数的对应规则就是“编码”

字符集：英文字符----ASCII字符集，中英文----Unicode字符集；基于同一字符集可以有多种编码方案，如：UTF-8、UTF-16；采用不同编码方式每个字符所占空间不同，默认每个字符占1B。

y=f(x)

字符集：函数定义域

编码：函数映射规则f

y：对应二进制数

4.2串的存储结构和基本操作的实现

4.2.1代码展示 

//静态数组实现顺序存储
#define MAXLEN 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;
//用完收到free

//串的链式存储
typedef struct StringNode{
	char ch;//每个结点存一个字符 1B
	struct StringNode *nest;//4B
}StringNode,* String;//存储密度低
typedef struct StringNode{
	char ch[4];//每个结点存多个字符
	struct StringNode *nest;//4B
}StringNode,* String;//存储密度提高

4.2.2串的顺序存储方案

第四章：串

4.2.3基本操作的实现

以顺序存储为例（方案四）

//求字串,用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;
}

//比较操作，若S>T则返回值>0，若S=T则返回值=0，若S<T则返回值<0
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;
}

//定位操作，若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0
int Index(SString S,SString T){
	int i=1, n=StrLength(S), m=StrLength(T);
	SString sub;//用于暂存子串
	while(i<=n-m+1){
		SubString(sub,S,i,m);
		if(StrCompare(sub,T)!=0)
			i++;
		else
			return i;//返回子串在主串中的位置
	}
	return 0;//S中不存在与T相等的子串
}

4.3串的模式匹配

在主串中找到与模式串相同的子串，并返回其所在位置

4.3.1朴素模式匹配算法

将主串中与模式串长度相同的子串搞出来，挨个与模式串对比

当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串

当检索成功时返回第一个字符位置，不成功则返回0

若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较，时间复杂度：O(mn)

成功最好时间复杂度：O(m)，第一个子串就成功，即只比较子串长度次数

失败最好时间复杂度：O(n)，子串第一个字符与主串完全不匹配，只比较主串长度次数

//法1：借助变量k记录位置
int Index(SString S,SString T){
	int k=1;
	int i=k,j=1;
	while(i<=S.length && j<=T.length){//有效范围
		if(S.ch[i]==T.ch[j]){//字符匹配成功
			++i;
			++j;
		}else{
			k++;//检查下一个子串
			i=k;//初始化
			j=1;
		}
	}
	if(j>T.length)//匹配成功终止条件，跳出while循环是因为j越界了
		return k;
	else
		return 0;
}

//法2：不借助k
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;//i=i-(j-1)+1=i-j+2，主串回溯
			j=1;//初始化
		}
	}
	if(j>T.length)//匹配成功终止条件，跳出while循环是因为j越界了
		return i-T.length;
	else
		return 0;
}

4.3.2改进模式匹配算法——KMP算法 

//最重要的就是求出next数组
int Index(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)//匹配成功终止条件，跳出while循环是因为j越界了
		return i-T.length;
	else
		return 0;
}

手算求next数组：

串的前缀：包含第一个字符，且不包含最后一个字符的子串

串的后缀：包含最后一个字符，且不包含第一个字符的子串

当第 j 个字符匹配失败，由前1 ~ j-1 个字符组成的串记为S，则：

next[j] = S的最长相等前后缀长度+1

特别的，next[1]=0，next[2]=1

例：ababaa； 注：粗体前缀，斜体后缀

j=1：S=空；next[1]=0

j=2：S=a，0+1=1；next[2]=1

j=3：S=ab，0+1=1；next[3]=1

j=4：S=aba，1+1=2；next[4]=2

j=5：S=abab，2+1=3；next[5]=3

j=6：S=aba ba，3+1=4；next[6]=4

序号 j 1 2 3 4 5 6
模式串 a b a b a a
next[j] 1 1 2 3 4 
//求模式串T的next数组
void get_next(SString T,int next[]){
	int i=1,j=0;
	next[1]=0;
	while(i<T.length){
		++i;
		++j;
		next[i]=j;
	}else
		j=next[j];
}

//KMP
int Index(SString S,SString T){
	int i=1,j=1;
	int next[T.length+1];
	get_next(T,next);//求模式串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)//匹配成功终止条件，跳出while循环是因为j越界了
		return i-T.length;
	else
		return 0;
}

时间复杂度：O(n+m)

4.3.3 KMP算法进一步优化

优化next数组为nextval数组，减少不必要比较

void get_nextval(SString T,int next[],int nextval[]){
	nextval[1]=0;
	for(int j=2;j<=T.length;j++){
		if(T.ch[next[j]]==T.ch[j])
			nextval[j]=nextval[next[j]];
		else
			nextval[j]=next[j];
	}
}//仔细看看有好处
序号 j 1 2 3 4 5 6
模式串 a b a b a a
next[j] 1 1 2 3 4
nextval[j] 1 1 4
数据结构 字符串
上一篇: 纯干货！AI大模型测试对比
下一篇: 数据结构（C语言）——第四章、串（1）串的顺序存储静态数组动态数组

继续阅读