1.串的定义
串,即字符串,由零个或多个字符组成的有限序列。
子串:串中任意个连续的字符组成的子序列。
主串:包含子串的串。
字符在主串中的位置:字符在串中的序号。
子串在主串中的位置:子串的第一个字符在主串中的位置。
2.串的基本操作
串的基本操作,如增删改查等通常以子串为操作对象。
(1)StrAssign(&T,chars):赋值操作。把串T赋值为chars。
(2)StrCopy(&T,S):复制操作。由串S复制得到串T。
(3)StrEmpty(S):判空操作。若S为空串,则返回TRUE,否则返回FALSE.
(4)StrLength(S):求串长。返回串S的元素个数。
(5)ClearString(&S):清空操作。将S清为空串。
(6)DestroyString(&S):销毁串。将串S销毁(回收存储空间)。
(7)Concat(&T,S1,S2):串连接。用T返回由S1和S2联接而成的新串。
(8)SubString(&Sub,S,pos,len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
(9)Index(S,T):定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0。
(10)StrCompare(S,T):比较操作。若S>T,返回值>0;若S=T,返回值=0;若S<T,则返回值<0。
3.串的存储结构
#define MAXLEN 255 //预定义最大串长为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;
串的链式存储
typedef struct StringNode{
char ch; //每个结点存1个字符
struct StringNode * next;
}StringNode, * String;
typedef struct StringNode{
char ch[4]; //每个结点存多个字符
struct StringNode * next;
}StringNode, * String;
4.基本操作的实现
(1)求子串
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString;
//求子串
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;
retrun true;
}
(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;
}
(3)定位操作(求串在主串中的位置)
若主串S中存在与串T值相同的子串,则返回它在主串中第一次出现的位置;否则函数值为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相等的子串
}
5.朴素模式匹配算法
(1)将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串,或所有子串都不匹配为止。
即定位操作。
(2)也可不适用字符串的基本操作,直接通过数组下标实现朴素模式匹配算法。若当前子串匹配失败,则主串指针i指向下一个子串的第一个位置,模式串指针j回到模式串的第一个位置;若j>T.length,则当前子串匹配成功,返回当前子串第一个字符的位置--i-T.length
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;
}
6.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;
}
next数组的机算算法
//求模式串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];
}
}