串的定义
串，也称为字符串，是由零个或多个字符组成的有限序列。它是一种特殊的线性表，仅由字符组成。一般记作：
S="a1a2......an"
其中，S是串名，n是串的长度，用双引号括起来的字符序列是串的值。ai可以是字母、数字和其他字符。当n=0时称为空串。
串的抽象数据类型的定义：
ADT Str{
数据对象；
数据关系；
基本操作：
StrAssign(&S,cstr[])
操作结果：将字符串cstr[]的字符赋给S
StrEmpty(S)
初始条件：存在串
操作结果：判断串是否为空，若为空返回1，否则返回0
StrLength(S)
初始条件：存在串
操作结果：返回串的长度
StrCopy(&T,S)
初始条件：存在串
操作结果：将串S的值赋给T
StrCompare(S,T)
初始条件：存在串
操作结果：比较串S和串T每个字符的ASCII值的大小，返回它们的差值
StrInsert(&S,pos,T)
初始条件：存在串
操作结果：将串T从S中第pos个位置开始插入
StrDelete(&S,pos,len)
初始条件：存在串
操作结果：将串S从第pos个位置开始往后删除len个元素
StrClear(&S)
初始条件：存在串
操作结果：将串S清空
}
串的顺序表示与实现
1.宏定义解释
#define MaxLength 60 //串的最大长度
2.结构类型
typedef struct {
char str[MaxLength]; //数组
int length; //长度
}
3.基本操作的实现
（1）串的赋值StrAssign
void StrAssign(SeqString *S,char cstr[]){
int i=0;
for(i=0;cstr[i]!='\0';i++){
S->str[i]=cstr[i];
S.length=i;
}
}
（2）判断串是否为空StrEmpty
int StrEmpty(SeqString S){
if(S.length==0){ //当串为空时返回1
return 1;
}
else{
return 0; //否则返回0
}
}
（3）串的长度StrLength
int StrLength(SeqString S){
return S.length;
}
（4）复制串StrCopy
void StrCopy(SqeString *T,SeqString S){
int i;
for(i=1;i<S.length;i++){
T->str[i]=S.str[i];
}
T->length=S.length;
}
（5）比较串StrCompare
int StrCompare(SeqString S,SeqString T){
int i;
for(i=0;i<S.length&&i<T.length;i++){
if(S.str[i]!=T.str[i]){
return (S.str[i]-T.str[i]); //如果不相等则返回二者的差值
}
else{
return (S.length-T.length); //如果比较完毕则返回二者长度的差值
}
}
}
（6）串的插入StrInsert
int StrInsert(SqeString *S,int pos,SqeString T){
//在S中的第pos个位置插入T
int i;
if(pos<0||pos-1>S->length){ //插入的位置不正确则返回0
return 0;
}
if(S->length+T.length<=MaxLength){ //若T可以完整的插入到S中
for(i=S->length+T.length-1;i>=pos+T.length-1;i--){ //将S中pos以后的字符向后移动
S->str[i]=S->str[i-T.length];
}
for(i=0;i<T.length;i++){ //开始插入
S->str[pos+i-1]=T.str[i];
}
S->length=S->length+T.length; //改变长度
return 1;
}
else if(pos+T.length<=MaxLength){ //T可以完全插入，但是S会被截断
for(i=MaxLength-1;i>T.length+pos-1;i--){ //将S中pos以后的字符向后移动
S->str[i]=S->str[i-T.length];
}
for(i=0;i<T.length;i++){ //开始插入
S->str[i+pos-1]=T.str[i];
}
S->length=MaxLength; //设置最长长度
return 0;
}
else{ //T不能完全插入到S中
for(i=0;i<MaxLength-pos;i++){
S->str[i+pos-1]=T.str[i]; //开始插入
}
S->length=MaxLength;
return 0;
}
}
（7）串的删除StrDelete
int StrDelete(SeqString *S,int pos,int len){
//在S中删除pos开始的len个字符
int i;
if(pos<0||len<0||pos+len>S->MaxLength){ //如果不合法则返回0
return 0;
}
else{
for(i=pos+len;i<=S->length-1;i++){ //将未删除的字符串移动到前面去
S->str[i-len]=S->str[i];
}
S->length=S->length-len; //修改长度
return 1;
}
}
（8）清空串StrClear
void StrClear(SeqString *S){
S->length=0; //j将长度设置为0
}
串的模式匹配
串的模式匹配也称为子串的定位操作，即查找子串在主串中出现的位置。模式匹配的算法主要有两种：BF算法和KMP算法。
1.BF算法
BF算法的主要思想是：从主串S中的第pos个字符开始与子串T的第一个字符比较，如果相等则继续逐一比较后续的字符；否则从主串的下一个字符开始与子串T的第一个字符开始比较，以此类推。如果在主串S中存在与子串T相等的连续字符序列，则匹配成功，返回子串T中第一个字符在主串S中的位置，否则返回0。
BF算法的代码描述如下：
int BFIndex(SeqString S,int pos,SeqString T){
//从S中的第pos个位置开始查找T
int i,j;
i=pos-1;
j=0;
while(i<S.length&&j<T.length){
if(S.str[i]==T.str[j]){ //如果相等，则继续往后寻找
i++;
j++:
}
else{
i=i-j+1; //如果中途断开，则从S的pos的下一个位置开始寻找
j=0; //T从头开始比较
}
}
if(j>=T.length){
return i-j+1; //如果找到则返回位置
}
else{
return 0;
}
}
网友评论