数据结构详细笔记——串

---

串的三要素

逻辑结构（定义）

串，即字符串（String）是由零个或多个字符组成的有限序列，串中字符的个数 n 称为串的长度。n=0 时的串称为空串。

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

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

数据的运算（基本操作）

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,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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

存储结构（物理结构）

顺序串（顺序存储）

顺序串的定义
静态分配

#define MAXLEN 255    // 预定义最大串长为255
typedef struct{
	char ch[MAXLEN];
	int length;
}SString;
1
2
3
4
5

动态分配

typedef struct{
	char *ch;
	int length;
}HString;
HString S;
S.ch = (char *) malloc(MAXLEN*sizeof(char));
S.length = 0;
1
2
3
4
5
6
7

求子串

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;
}
1
2
3
4
5
6
7
8
9
10

比较操作

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;
} 
1
2
3
4
5
6
7
8

定位操作

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相等的子串
}
1
2
3
4
5
6
7
8
9
10

链式串（链式存储）

存储密度低，每个字符1B，每个指针4B

typedef struct StringNode{
	char ch;  // 每一个结点存1个字符
	struct StringNode *next;  // 指针
}StringNode,*String;
1
2
3
4

提高存储密度

typedef struct StringNode{
	char ch[4];   // 每个结点存多个字符
	struct StringNode *next;
}StringNode,*String;
1
2
3
4

字符串模式匹配

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

两种模式匹配的算法
1、朴素模式匹配算法
2、KMP算法

朴素模式匹配算法

主串长度为n，模式串长度为m
将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止
最多对比 n-m+1个子串

Index(S,T) 定位操作就是利用了朴素模式匹配算法原理

通过数组下标实现朴素模式匹配算法

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

设主串长度为n，模式串长度为m，则时间复杂度 O(nm)

朴素模式匹配算法的缺点：当某些子串与模式能部分匹配时，主串的扫描指针经常回溯，导致时间开销增加。

KMP算法

KMP算法：利用next数组进行匹配，减少回溯

int Index_KMP(SString S,SString T,int next[]){
	int i = 1, j = 1;
	whlie(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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码中的next数组是：当模式串的第j个字符匹配失败时，令模式串跳到next【j】再继续匹配

求模式串的next数组

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

如 'abababcdef'
前缀：'abababcde'
后缀：'bababcdef'

1
2
3
4

当第j个字符匹配失败，由前 1~j-1个字符组成的串记为S，则next[j] = S的最长相等前后缀长度加1，
注意：next[1] = 0 , next[2] = 1

模式串：'ababaa'
当j=1时，next[1] = 0;
当j=2时，next[2] = 1;
当j=3时，S：ab, 前缀：a, 后缀：b, 前缀后缀相等长度为0 , next[3] = 0+1 = 1;
当j=4时，S：aba, 前缀：ab, 后缀：ba, 前缀后缀相等长度为0 , next[4] = 0+1 = 1;
当j=5时，S：abab, 前缀：aba, 后缀：bab, 前缀后缀相等最长串为ab，长度为2 , next[5] = 2+1 = 3;
当j=6时，S：ababa, 前缀：abab, 后缀：baba, 前缀后缀相等最长串为aba，长度为3 , next[6] = 3+1 = 4;

所以得
序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
1
2
3
4
5
6
7
8
9
10
11
12

代码如下

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++;
			 // 若pi=pj,则next[j+1]=next[j]+1
			 next[i] = j;
		} else {
			j = next[j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

KMP算法完整代码时间复杂度 O(n+m)

int Index_KMP(SString S,SString T){
	int i = 1, j = 1;
	int next[T.length+1];
	get_next(T,next);
	whlie(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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

KMP算法的进一步优化

对于KMP算法色优化实际上是优化next数组，将next数组优化为nextval数组

例如上面的next数组
序号j		1	2	3	4	5	6
模式串		a	b	a	b	a	a
next[j]		0	1	1	2	3	4
nextval[j]	0	1	0	1	0	4

//求nextval
netval[1] = 0;
for(int j=2; j<=T.length;mj++){
	if(T.ch[next[j]] == T.ch[j])
		nextval[j] = nextval[next[j]];
	else
		nextval[j] = next[j];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14