数据结构之 串 的详解

欢迎大家来到IT世界,在知识的湖畔探索吧!

定义

内容受限的线性表

串(string):零个或者多个任意字符组成的有限序列
字串：串中任意个连续字符组成的字序列
主串：包含子串的串相应地 字符位置：字符在序列中序号为该字符在串中的位置
字串位置：字串第一个字符在主串中的位置 空格串：由一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等并且各个对应位置上字符相同时，这两个串才是相等的

数学表示

S=“a1a2……an”(n>=0)

注: – S为串名 – a1a2……an为串值 – n为串长

抽象类型定义

ADT String {
数据对象: D={ ai | ai∈ CharacterSet,记为 V,i=1 ,2 ,…, n,n≥ 0 }
结构关系: R={< ai,ai + 1 >| ai,ai + 1 ∈ V,i=1 ,…, n-1 ; n-1 ≥ 0 }
基本操作:
StrAssign(&T,chars)//串赋值
操作前提: chars 是字符串常量。
操作结果:生成一个值等于 chars 的串 T。

StrInsert( S,pos,T)//字串插入
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。
操作结果:在串 S 的第 pos 个字符之前插入串 T。

StrDelete( S,pos,len)
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。
操作结果:从串 S 中删除第 pos 个字符起长度为 len 的子串。

StrCopy( S,T)
操作前提:串 S 存在。
操作结果:由串 T 复制得串 S。

StrEmpty( S)
操作前提:串 S 存在。
操作结果:若串 S 为空串,则返回 TRUE,否则返回 FALSE。

StrCompare(S,T) //串比较
操作前提:串 S 和 T 存在。
操作结果:若 S>T,则返回值>0 ;如 S=T,则返回值=0 ;若 S<T,则返回值<0 。

StrLength(S)
操作前提:串 S 存在。
操作结果:返回串 S 的长度,即串 S 中的字符个数。

StrClear( S)
操作前提:串 S 存在。
操作结果:将 S 清为空串。

ConCat(&T，S1,S2)
操作前提:串 S1 、S2 和 T 存在。
操作结果:将串 S1 和 S2 的值连接在串 T 的后面。

SubString( Sub,S,pos)
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)且 1 ≤ len≤ StrLength( S)- pos+1
操作结果:用 Sub 返回串 S 的第 pos 个字符起的子串。

StrIndex( S,pos,T)
操作前提:串 S 和 T 存在,T 是非空串,1 ≤ pos≤ StrLength( S)。
操作结果:若串 S 中存在和串 T 相同的子串,则返回它在串 S 中第 pos 个字符 之后第一次出现的位置;否则返回 0 。

StrReplace( S,T,V)
操作前提:串 S、 T 和 V 存在且 T 是非空串。
操作结果:用 V 替换串 S 中出现的所有与 T 相等的不重叠的子串。

StrDestroy( S)
操作前提:串 S 存在。
操作结果:销毁串 S。
}ADT string

顺序存储结构

#define MAXSIZE 255
typedef struct{
char ch[MAXSIZE+1];//存储串的一维数组
int Length;//串的当前长度
}SString

链式存储结构

#define CHUNKSIZE 80 //块的大小可由用户定义
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head, *tail;//串的头指针和尾指针
int curlen;//串的当前长度
}LString;//字符串的块链结构

模式匹配算法

• 算法的目的： 确定主串中所含字串第一次出现的位置
• 算法的应用：搜索引擎、拼写错误、语言翻译、数据压缩
• 算法种类：BF算法KMP算法(速度快)

1.BF算法

Brute-Force简称BF算法，亦称为简单匹配算法，采用穷举法的思路

算法思路：从S的每一个字符开始依次与T的字符进行匹配

实现：
Index(S,T,pos) – 将主串的第pos个字符和模式串(字串)的第一个字符比较
– 若相等，继续逐个比较后续字符 – 若不等，从主串的下一个字符起，重新与模式串的第一个字符比较 – 直到主串的一个连续字串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功 – 否则，匹配失败，返回值为0

int Index_BF(SString S,SString T,int pos ){
int i = pos;
int j = 1;//字符的序号从1开始
while(i<=S.length && j<=T.length){
if(s.ch[i]==t.ch[j]){
++i;
++j;//主串和字串依次匹配下一个字符
}
else{
i = i – j + 2;//主串则向前移动一个字符
j = 1;//字串返回到第一个字符
}
}
//这里j>T.lngth是因为字串T的最后一个字符和主串的字符还是一样，那么进入while循环后又++j，所以只要j.length大于T的字符长度则说明全部字符都匹配成功
if(j>T.length) return i-T.length;//返回匹配的第一个字符的下标
else return 0;//模式匹配不成功

}

2.KMP算法

算法思想：利用已经部分匹配的结果而加快模式串的滑动速度，而主串S的指针i不必回溯，可提速到O(n+m)

主串和模式串不断比较，如果在比较失败，主串的i不用回溯到比较字符中第一个字符的第二个字符，而只用模式串j进行回溯，与主串再次进行下一轮比较，在这个过程中，我们用next[j]存储需要回溯到重新比较的值

image.png

代码实现

int Index KMP (SString S,SString T, int pos) {
i= pos,j =1;
while(i<S.length && j<T.length) {
if (j==0 S.chi]==T.ch[j]) {
i++;j++;
}
else{
j=next[j];//i不变，j后退
}

}
if (j>T.length) return i-T.length; //匹配成功
else return 0;//返回不匹配的标志

void get_next(SString T, int &next[]){
int i= 1;
next[1] = 0;
int j = 0;
while( i<T.length){
if(j==0||T.ch[i] == T.ch[j]){
++i; ++j;
next[i] = j;
}
else{
j = next[j];
}
}
}