2025年第四章串

大家好，我是讯享网，很高兴认识大家。

goole引擎以串为输入数据，word也是对字符串进行编辑操作的软件

4.1串的类型的定义

4.1.1 串的定义

串是由0个或多个字符组成的有限序列，串中字符的个数为串的长度，含有0个元素的串叫空串。

char str[]="abcdef"；//1

讯享网

对于上面的str来说，若str表示的为数组，那么这个数组的长度为7，若str表示的为字符串，则str的长度为6

串中任意元素组成的子序列称为串的子串，包含子串的串称为主串

串的逻辑结构和线性表类似，串是限定了元素为字符的线性表。从操作集上讲，串与线性表有很大的区别，线性表的操作主要针对表内的某一元素，而串的操作主要针对主串中的一个子串

4.2.2 串的存储结构

1、定长顺序存储表示

此处采用的是在字符串的末尾加上‘\0’，同时也设置一个length用于存储字符串的长度，原因是如果只是在字符串的末尾加上‘\0’的话，那么求串的长度的时候需要遍历n次，时间复杂度是O(n)，但是如果有了length，那么求穿的长度的时候时间复杂度就是O（1）

1、定长顺序表示结构体为

讯享网//定长顺序存储 typedef struct{ char str[maxSize+1]; int length; }SSTR;

2、变长分配存储表示结构体

在程序执行过程中可以根据需要，动态的分配结构体

//变长分配存储 typedef struct{ char *ch; int length; }DSTR;

这种方式在使用时，需要用malloc（）来分配一个长度为length、类型为char的连续存储空间，分配的空间可以用函数free（）释放掉，用函数malloc（）分配空间如果成功的话，则返回一个指向起始地址的指针，作为串的基地址，这个地址由ch指针来指向，如果分配失败，则返回NULL

4.1.3串的基本操作

1、赋值操作（strassign（））

讯享网//赋值操作 int strassign(DSTR &str,char *ch){ if(str.ch)//如果原串有数据则释放原串 free(str.ch); int len=0; char *c=ch; while(*c){//感觉*c与c[]一个性质 ++c; ++len; } if(len==0){ str.ch=NULL; str.length=0; return 1; } else{ str.ch=(char*)malloc(sizeof(char)*(len+1)); if(str.ch==NULL)//如果空间分配失败 return 0; else{ c=ch; for(int i=0;i<len;++i,++c) str.ch[i]=*c; str.length=len; return 1; } } }

2、取串长度操作

//取串的长度的操作 int strlength(DSTR str){ return str.length; }

3、串比较操作

讯享网//核心操作，串比较操作,在没有比较出大小的情况下，先结束的为较小串， //若两串同时结束则返回两串相等标记 int strcmp(DSTR str1,DSTR str2){ for(int i=0;i<str1.length&&i<str2.length;i++) if(str1.ch[i]!=str2.ch[i]) return str1.ch[i]-str2.ch[i]; return str1.length-str2.length; }

4、串连接操作

//串链接操作 int concat(DSTR &s,DSTR s1,DSTR s2){ if(s.ch)//如果原串有数据存在，则释放他 free(s.ch); s.ch=(char*)malloc(sizeof(char)*(s1.length+s2.length+1)); if(s.ch==NULL) return 0; int i=0; for(;i<s1.length;i++) s.ch[i]=s1.ch[i]; for(int j=0;j<s2.length;i++,j++) s.ch[i]=s2.ch[j]; s.length=s1.length+s2.length; return 1; }

5、求子串操作

讯享网//求子串的操作 int substring(DSTR &substr,DSTR str,int pos,int len){ if(pos<0||pos>=str.length||len<0||len>str.length-pos) return 0; if(substr.ch){ free(substr.ch); substr.ch=NULL; } if(len==0){ substr.ch=NULL; substr.length=0; return 1; } else{ substr.ch=(char*)malloc(sizeof(char)*(str.length+1)); int i=pos; int j=0; while(i!=pos+len){ substr.ch[j]=str.ch[i]; ++j; ++i; } substr.ch[j]='\0'; substr.length=len; return 1; } }

6、串清空操作

//串清空操作 int clearstring(DSTR &str){ if(str.ch){ free(str.ch); str.ch=NULL; } str.length=0; return 1; }

4.2串的模式匹配算法

4.2.1简单模式匹配

最简单的匹配方法，代码如下

讯享网

讯享网//简单模式匹配算法 int index(DSTR str,DSTR substr){ int i=0,j=0,k=i; while(i<str.length&&j<substr.length){ if(str.ch[i]==substr.ch[j]){ i++; j++; } else{ j=0; i=++k;//匹配失败，i从主串的下一个位置开始，k中记录了上一次的起始位置 } } if(j==substr.length) return k; else return 0; }

4.2.2KMP算法

KMP算法简单来说就是运用一个next数组存储模式串（要匹配的串）的每一个字符前面的字符串的最长公共前后缀的长度，即要回溯到的位置，然后在与主串匹配时，如果发生不相等的冲突，则将当前的模式串下标转移到next数组的对应位置，这样可以减少重复匹配的次数，从而高效的进行匹配

下面以串的首地址为0为例展示了next数组的形式，其中next[5]=2，表示d的前面的字符串的最长公共前后缀长度为2，即为aa，此处要注意数组中的-1位置是扩展出来的，实际上是不存在的，它的存在是为了后续的匹配更加方便，它所虚拟存储的字符可以与任意字符匹配

求next的代码

void getnext(DSTR substr,int next[]){ int i=0,j=-1; next[0]=-1; while(i<substr.length&&j<substr.length){ if(j==-1||substr.ch[i]==substr.ch[j]){ //j==0时就意味着可以从头开始找子串 //substr.ch[i]==substr.ch[j]意味着此时可以继续向下匹配字符 i++; j++; next[i]=j; } else //若不满足上面的条件的话，则说明出现了不同的字符，需要从上一个相同的部分重新匹配 j=next[j]; } }

匹配算法

讯享网int KMP(DSTR str,DSTR substr,int next[]){ int i=0,j=0; while(i<str.length&&j<substr.length){ if(j==-1||str.ch[i]==substr.ch[j]){ i++; j++; } else j=next[j]; } if(j==substr.length) return i-substr.length; else return 0; }

完整代码：

若串以0为首地址的话

//KMP算法 void getnext(DSTR substr,int next[]){ int i=0,j=-1; next[0]=-1; while(i<substr.length&&j<substr.length){ if(j==-1||substr.ch[i]==substr.ch[j]){ //j==0时就意味着可以从头开始找子串 //substr.ch[i]==substr.ch[j]意味着此时可以继续向下匹配字符 i++; j++; next[i]=j; } else //若不满足上面的条件的话，则说明出现了不同的字符，需要从上一个相同的部分重新匹配 j=next[j]; } } int KMP(DSTR str,DSTR substr,int next[]){ int i=0,j=0; while(i<str.length&&j<substr.length){ if(j==-1||str.ch[i]==substr.ch[j]){ i++; j++; } else j=next[j]; } if(j==substr.length) return i-substr.length; else return 0; }

若串以1为首地址的话KMP算法的形式

讯享网void getnext(DSTR substr,int next[]){ int i=1,j=0; next[1]=0; while(i<substr.length){ if(j==0||substr.ch[i]==substr.ch[j]){ //j==0时就意味着可以从头开始找子串 //substr.ch[i]==substr.ch[j]意味着此时可以继续向下匹配字符 i++; j++; next[i]=j; } else //若不满足上面的条件的话，则说明出现了不同的字符，需要从上一个相同的部分重新匹配 j=next[j]; } } void KMP(DSTR str,DSTR substr,int next[]){ int i=1,j=1; while(i<=str.length&&j<=substr.length){ if(j==0||str.ch[i]==substr.ch[j]){ i++; j++; } else j=next[j]; } if(j>substr.length) return i-substr.length; else return 0; }

4.2.3KMP算法的改进

有一种特殊的情况，比如对于字符串AAAAAB来说，它的next数组是-，也就意味着，如果第五个字符不匹配的话，将会回溯5次到-1的位置为止，这样会产生浪费，所以引进nextval数组，该数组的形成规则是

1、若j=0，则赋值nextval[i]=-1

2、若j==-1 || substr[i]==substr[j],则i++，j++,再进行判断

1）若substr[i]==substr[j] 则nextval[i]=nextval[j]

2) 若substr[i]==substr[j] 则nextval[i]=j

3、若substr[i]！=substr[j],则j=nextval[j]

代码如下，匹配算法，同上

//KMP算法的改进 void getnextval(DSTR substr,int nextval[]){ int i=0,j=-1; nextval[0]=-1; while(i<substr.length&&j<substr.length){ if(j==-1||substr.ch[i]==substr.ch[j]){ i++; j++;//未改进之前后面是next[i]=j;所以就相当于j就是next[i] //根据获得nextval的条件，如果substr.ch[i]与substr.ch[next[i]]相等的话，那么nextval[i]=nextval[j] //这样会减少重复判断的次数 //如若substr.ch[i]与substr.ch[next[i]]不相等，那么意味着不会出现重复判断，所以nextval[i]=j if(substr.ch[i]==substr.ch[j]) nextval[i]=nextval[j]; else nextval[i]=j; } else j=nextval[j]; } }

串操作完整代码如下（可执行）

讯享网#include<stdlib.h> #include <iostream.h> #define maxSize 100 typedef struct{ char *ch; int length; }DSTR; //赋值操作 int strassign(DSTR &str,char *ch){ if(str.ch)//如果原串有数据则释放原串 free(str.ch); int len=0; char *c=ch; while(*c){//感觉*c与c[]一个性质 ++c; ++len; } if(len==0){ str.ch=NULL; str.length=0; return 1; } else{ str.ch=(char*)malloc(sizeof(char)*(len+1)); if(str.ch==NULL)//如果空间分配失败 return 0; else{ c=ch; for(int i=0;i<len;++i,++c) str.ch[i]=*c; str.length=len; return 1; } } } //取串的长度的操作 int strlength(DSTR str){ return str.length; } //核心操作，串比较操作,在没有比较出大小的情况下，先结束的为较小串， //若两串同时结束则返回两串相等标记 int strcmp(DSTR str1,DSTR str2){ for(int i=0;i<str1.length&&i<str2.length;i++) if(str1.ch[i]!=str2.ch[i]) return str1.ch[i]-str2.ch[i]; return str1.length-str2.length; } //串链接操作 int concat(DSTR &s,DSTR s1,DSTR s2){ if(s.ch)//如果原串有数据存在，则释放他 free(s.ch); s.ch=(char*)malloc(sizeof(char)*(s1.length+s2.length+1)); if(s.ch==NULL) return 0; int i=0; for(;i<s1.length;i++) s.ch[i]=s1.ch[i]; for(int j=0;j<s2.length;i++,j++) s.ch[i]=s2.ch[j]; s.length=s1.length+s2.length; return 1; } //求子串的操作 int substring(DSTR &substr,DSTR str,int pos,int len){ if(pos<0||pos>=str.length||len<0||len>str.length-pos) return 0; if(substr.ch){ free(substr.ch); substr.ch=NULL; } if(len==0){ substr.ch=NULL; substr.length=0; return 1; } else{ substr.ch=(char*)malloc(sizeof(char)*(str.length+1)); int i=pos; int j=0; while(i!=pos+len){ substr.ch[j]=str.ch[i]; ++j; ++i; } substr.ch[j]='\0'; substr.length=len; return 1; } } //串清空操作 int clearstring(DSTR &str){ if(str.ch){ free(str.ch); str.ch=NULL; } str.length=0; return 1; } //简单模式匹配算法 int index(DSTR str,DSTR substr){ int i=0,j=0,k=i; while(i<str.length&&j<substr.length){ if(str.ch[i]==substr.ch[j]){ i++; j++; } else{ j=0; i=++k;//匹配失败，i从主串的下一个位置开始，k中记录了上一次的起始位置 } } if(j==substr.length) return k; else return 0; } //KMP算法 void getnext(DSTR substr,int next[]){ int i=0,j=-1; next[0]=-1; while(i<substr.length&&j<substr.length){ if(j==-1||substr.ch[i]==substr.ch[j]){ //j==0时就意味着可以从头开始找子串 //substr.ch[i]==substr.ch[j]意味着此时可以继续向下匹配字符 i++; j++; next[i]=j; } else //若不满足上面的条件的话，则说明出现了不同的字符，需要从上一个相同的部分重新匹配 j=next[j]; } } int KMP(DSTR str,DSTR substr,int next[]){ int i=0,j=0; while(i<str.length&&j<substr.length){ if(j==-1||str.ch[i]==substr.ch[j]){ i++; j++; } else j=next[j]; } if(j==substr.length) return i-substr.length; else return 0; } //KMP算法的改进 void getnextval(DSTR substr,int nextval[]){ int i=0,j=-1; nextval[0]=-1; while(i<substr.length&&j<substr.length){ if(j==-1||substr.ch[i]==substr.ch[j]){ i++; j++;//未改进之前后面是next[i]=j;所以就相当于j就是next[i] //根据获得nextval的条件，如果substr.ch[i]与substr.ch[next[i]]相等的话，那么nextval[i]=nextval[j] //这样会减少重复判断的次数 //如若substr.ch[i]与substr.ch[next[i]]不相等，那么意味着不会出现重复判断，所以nextval[i]=j if(substr.ch[i]==substr.ch[j]) nextval[i]=nextval[j]; else nextval[i]=j; } else j=nextval[j]; } } void main(){ DSTR a,b,c,d; char *e; a.ch=NULL;//此处必须加上，若不加的话被创建时不会自动成为NULL指针。在Debug模式下，VC++编译器会把未初始化的栈内存上的指针全部填成 0xcccccccc ，当字符串看就是 “烫烫烫烫……”； b.ch=NULL; c.ch=NULL; d.ch=NULL; //初始化串 strassign(a,"abcdef"); strassign(b,"abcdef"); e=a.ch; for(int i=0;i<a.length;i++,e++) cout<<*e; cout<<endl; e=b.ch; for(i=0;i<b.length;i++,e++) cout<<*e; cout<<endl; //计算串的长度 cout<<"计算串的长度"<<strlength(a)<<endl; //对比串 cout<<"对比串"<<strcmp(a,b)<<endl; //连接串 concat(c,a,b); cout<<"连接串"<<endl; e=c.ch; for(i=0;i<c.length;i++,e++) cout<<*e; cout<<endl; //求子串 substring(d,a,1,2); cout<<"求子串"<<endl; for(i=0;i<d.length;i++) cout<<d.ch[i]; cout<<endl; //求子串的位置 strassign(a,"abcdef"); strassign(b,"cde"); cout<<"求子串的位置"<<index(a,b)<<endl; //KMP int next[10]; strassign(a,"abababb"); strassign(b,"adcababababb"); getnext(a,next); for(i=0;i<a.length;i++) cout<<next[i]<<" "; cout<<endl; cout<<"KMP:"<<KMP(b,a,next)<<endl; //KMP改进 int nextval[10]; strassign(a,"abababb"); strassign(b,"adcababababb"); getnextval(a,nextval); for(i=0;i<a.length;i++) cout<<nextval[i]<<" "; cout<<endl; cout<<"KMP:"<<KMP(b,a,nextval)<<endl; }

2025年第四章 串