数据结构(四)——串


串的定义和基本操作

定义

串,即字符串(String)是由零个或多个字符组成的有限序列。一般记为S=’a1a2……an‘(n>=0)。

其中,S是串名,单引号括起来的字符序列是串的值:ai可以是字母、数字或其他字符:串中字符的个数n称为串的长度。n=0时的串称为空串。

例:S=”HelloWorld!”
有的语言用双引号,如Java、C;有的语言用单引号,如Python

术语

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

串对比线性表的特性

  • 串是一种特殊的线性表,数据元素之间呈线性关系。
  • 串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等)。
  • 串的基本操作,如增删改查等通常以子串为操作对象。

串的基本操作

  • 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连接而成的新串
  • 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
//静态存储:
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //每个分量存储一个个字符
int length; //串的实际长度
}SString;
1
2
3
4
5
6
7
8
9
10
11
12
//动态存储:
#define MAXLEN 255
typedef struct{
char *ch; //按串长分配存储区,ch指向串的基地址
int length; //串的长度
}HString;

void test(){
HString S;
S.ch=(char*)malloc(MAXLEN *sizeof(char));
S.length=0;
}

存储方式

我们一般会考虑四种存储方式:

  1. ch数组空间正常存放数据,length空间存放有效串长度
  2. ch数组中的第一个空间存放有效串长度,剩余的空间存放数据,这样的话数组下标与串元素位序统一(都是从1开始)
  3. ch数组空间正常存放数据,最后一个位置存放’\0’(ASCII码第0位元素),没有length空间
  4. char数组中的第一个空间废弃不用,其他空间正常存放,length空间存放有效串长度,这样的话数组下标与串元素位序也得到统一(都是从1开始)

我们后面的示例都以第四种方法为例。

基本操作的实现

求子串

1
2
3
4
5
6
7
8
9
10
11
//求子串。用Sub返回串S的第pos个字符起长度为len的子串
bool SubString(SString *Sub,SString S,int pos,int len){
int i=0;
//子串范围越界
if(pos+len-1>S.length)
return false;
for(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
11
//比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
int StrCompare(SString S,SString T){
int i=1;
for(;i<=S.length&&i<=T.length;i++){
if(S.ch[i]!=T.ch[i]){
return (S.ch[i]-T.ch[i]>0)?1:-1;
}
}
//扫描过的所有字符都相同,则
return (S.length-T.length>0)?1:(S.length==T.length?0:-1);
}

寻找子串

1
2
3
4
5
6
7
8
9
10
11
12
13
//定位操作。若主串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相等的子串
}

链式存储

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

每个字符1B,每个指针4B,我们可以直观地感受到链式存储串的存储密度很低。

为了尽可能地改善存储密度,我们也可以将每个StringNode存储的字符多一点:

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

在最后一个结点中,如果存储串后有一些剩余位置空着,我们可以填充上一些特殊字符,例如#。


字符串模式匹配

定义

我们将我们待搜索的字符串统称为“主串”,将搜索的字符串称为“模式串”。
字符串模式匹配:在主串中找到与模式串相同的子串,并返回其所在位置。

模式串和子串:

  • 子串:主串的一部分,这是一定存在的
  • 模式串:不一定能在主串中找到的一部分字符串

模式匹配算法

  1. 朴素模式匹配算法
  2. KMP算法

朴素模式匹配算法

算法思路

主串长度为n,模式串长度为m。

朴素模式匹配算法:将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串,或所有子串都不匹配为止。

我们前面介绍的Index函数其实就是朴素模式匹配算法的实现。下面,我们来不使用字符串的基本操作,直接通过数组下标实现朴素模式匹配算法

具体实现

具体实现思路:

  1. 为主串S和模式串T分别设置两个指针,主串指针i指向首个子串的第一个位置,模式串指针j指向第一个位置。
  2. 比较两个指针的元素,当元素值不一样则匹配失败,则主串指针i指向下一个子串的第一个位置,模式串指针j回到模式串的第一个位置。
    • i=i-j+2
    • j=1
  3. 当j指的位置超出了模式串的长度,则当前子串匹配成功。返回当前子串的第一个字符的位置(i-T.length)

实现代码如下:

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

算法分析

  • 最后匹配到的最坏情况下,每个子串都要对比m个字符,共n-m+1个子串,复杂度=O((n-m+1)*m)=O(n*m)(n>>m)
  • 最后匹配到的最好情况下:每个子串的第一个字符都匹配失败,共n-m+1个子串,复杂度=O(n-m+1)=O(n)(n>>m)

KMP算法

算法思路

不要被KMP的名字吓到,它叫KMP仅是因为发明该算法的三个老头的名字中有K、M、P,所以发明出来该算法后就称为KMP算法

  1. 设主串S指针为i,模式串T指针为j,模式串为ababc。
  2. 当主串S与模式串T进行比较,比较到第五元素时,S[5]和T[5]不相等。
  3. 此时可知,S[1]=T[1]=’a’、S[2]=T[2]=’b’、S[3]=T[3]=’a’、S[4]=T[4]=’b’,即已经匹配的元素肯定是相等的。
  4. 此时,i指针不变,而j指针指向3,再开始新的匹配,这是正确的,因为i指针的前一个元素和再前一个元素为ab,T[1]、T[2]也分别为ab,故可以直接从T[3]比较。
  5. 如此往复,特别说明,当与模式串的第一个元素就匹配失败,j应当设置为0,而当j为0时,i指针和j指针应该同时加一
  6. 最后,若i指针或j指针超出各自串长度,则退出循环,而j指针若超出模式串长度,则i-j+1的位置即为目标子串的位置。

如上便是KMP算法的关键思路,主串S的指针i是不会回溯的

那么在实际操练中,我们需要逐个分析,当T的第x个元素不匹配时,j指针应该跳回那里(可见,这个j的新位置是只跟模式串有关,无所谓主串的内容)。

最后可以制成一个整型变量的一维数组next,位序即为x,内容即为j的新位置。这样就指出了出现不匹配时的j指针该何去何从。

具体实现

next数组

next数组的作用:当模式串的第j个字符匹配,从模式串的第next[j]的继续往后匹配。

next数组匹配规则:

  1. next[1]都无脑写0
  2. next[2]都无脑写1
  3. 其他next:在不匹配的位置前,划一条分界线,模式串一步一步往后退,直到分界线之前“能对上”,或模式串完全跨过分界线为止。此时j指向哪儿,next数组值就是多少。

KMP算法求子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//KMP算法
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)
return i-T.length; //匹配成功
else
return 0;
}

算法分析

设主串length为n,模式串长度为m。

KMP算法,最坏时间复杂度为O(m+n)

  • 求next数组时间复杂度为O(m)
  • 模式匹配过程最坏时间复杂度O(n)