【数据结构笔记】8.串
文章目录
- 8.1 串的定义
- 8.2 串的基本操作
- 8.3 串的存储
- 8.3.1 串的顺序存储
- 8.3.2 串的链式存储
- 8.4 串的基本操作的实现
- 8.4.1 求子串
- 8.4.2 比较操作
- 8.4.3 定位操作
- 8.5 朴素模式匹配算法
- 8.6 KMP算法
8.1 串的定义
串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = ′ a 1 a 2 . . . . . . a n ′ ( n ≥ 0 ) S = 'a_1a_2......a_n'(n \geq0) S=′a1a2......an′(n≥0)。其中，S是串名，单引号括起来的字符序列是串的值； a i a_i ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。 n = 0 n=0 n=0时的串成为空串（用 ∅ \emptyset ∅表示）。
注意：有的地方用双引号作为字符串的界限符（如Java、C），有的地方用单引号作为字符串的界限符（如Python）。
-
子串：串中任意个连续的字符组成的子序列。
-
主串：包含子串的串。
-
字符在主串中的位置：字符在串中的序号。
-
子串在主串中的位置：子串的第一个字符在主串中的位置。
串 V.S 线性表：
- 串是一种特殊的线性表，数据元素之间呈线性关系。
- 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）。
- 串的基本操作，如增删改查等通常以子串为操作对象。
8.2 串的基本操作
-
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, 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。
任何数据存到计算机中一定是二进制数。需要确定一个字符和二进制数的对应规则，这就是“编码”。采用不同的编码方式，每个字符所占空间不同，考试中只需默认每个字符占1B即可。
8.3 串的存储
8.3.1 串的顺序存储
静态数组实现（定长顺序存储）
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString;
动态数组实现（堆分配存储），用完需要手动free。
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN * sizeof(char));
S.length = 0;
8.3.2 串的链式存储
//存储密度低：每个字符1B，每个指针4B。
typedef struct StringNode{
char ch; //每个结点存1个字符
struct StringNode * next;
}StringNode, * String;
//可适当提高每个结点所携带的信息量,此时存储密度提高。
typedef struct StringNode{
char ch[4]; //每个结点存多个字符
struct StringNode * next;
}StringNode, * String;
8.4 串的基本操作的实现
8.4.1 求子串
用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;
}
8.4.2 比较操作
若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
}
8.4.3 定位操作
若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
int Intex(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); //从主串S中提取一个与串T长度相同的子串sub
if(StrCompare(sub, T) != 0)
++i;
else
return i;
}
return 0; //S中不存在与T相等的子串。
}
8.5 朴素模式匹配算法
主串长度为n，模式串长度为m。
朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止。
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指向下一个子串的第一个位置，
//模式串指针j回到模式串的第一个位置
i = i-j+2;
j = 1;
}
}
if(j > T.length)
return i-T.length;
else
return 0;
}
最坏的情况，每个子串都要对比m个字符，共n-m+1个子串，复杂度 = O((n-m+1) * m) = O(nm)（注：很多时候n>>m）。
8.6 KMP算法
由D.E.Knuth, J.H.Morris和V.R.Pratt提出，因此成为KMP算法。
next数组：当模式串的第j个字符匹配失败时，令模式串跳到next[j]再继续匹配。
串的前缀：包含第一个字符，且不包含最后一个字符的子串。
串的后缀：包含最后一个字符，且不包含第一个字符的子串。
当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则next[j] = S的最长相等前后缀长度+1.
特别地，next[1] = 0, 且next[2]往往等于1。
//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;
}
//求模式串T的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;
//若pi=pj，则next[j+1] = next[j]+1
next[i]=j;
}
else
j=next[j]; //否则令j=next[j]，循环继续
}
}
//根据next数组求改进的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];
}
- 朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加。最坏时间复杂度O(nm)；
- KMP算法：当子串和模式串不匹配时，主串指针i不回溯，模式串指针j = next[j]，算法平均时间复杂度为O(n+m)。