1 串
串是一种特殊的线性表,内容受限(数据元素是一个字符)。
1.1 串的顺序存储结构
静态分配
//串的定长顺序存储结构
#define MaxSize 255
typedef struct{
char ch[MaxSize+1];//下标从1开始记
int length;
}SString;
动态分配
//串的堆式存储结构
typedef struct{
char *ch;
int length;
}HString;
1.2 串的链式存储结构
考虑到存储效率和算法的方便性,串多采用顺序存储结构。
//串的链式存储结构
#define CHUNKSIZE 80
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail;
int length;
}LString;
1.3 串的模式匹配算法
串的模式匹配有两个字符串S和T,设S为主串,也称正文串;T为子串,也称模式。著名的模式匹配算法有BF算法和KMP算法。
1.3.1 BF算法
即朴素方法,时间复杂度O(n*m)。
1、分别用计数指针i和j指向主串S和模式T中当前正待比较的字符位置,i的初值为pos,j的初值为1。
2、如果两个串均为比较到串尾(i<=S.length&&j<=T.length),则:
- S.ch[i]==T.ch[j]时,指针后移比较下一个字符,i++,j++。
- S.ch[i] !=T.ch[j]时,指针i回溯,回到这次比较的起始位置的下一个,即 i=i-j+2(原来是从i-j+1开始往后比较的,所以要再+1到下一个位置),j回溯,j=1。
3、如果j>T.length,证明模式已经全部匹配了,成功。返回位置i-T.length。
BF算法实现
int IndexBF(SString S,SString T,int pos){
int i=pos,j=1;
while(i<=S.length&&j<=T.length){
if(S[i]==T[j]){
i++;
j++;
}else{
i=i-j+2;
j=1;
}
}
if(j>T.length) return i-T.length;//成功
else return 0;//匹配失败
}
1.3.2 KMP算法
KMP算法的时间复杂度:O(n+m)
改进思路:主串S指针i不回溯,不会回头,只有模式串指针回溯,但也不是无脑地回溯到1,根据next数组来回溯,j=next[j]。
next数组为当前字符不匹配时,j指针下一步该指向的位置。
1、分别用计数指针i和j指向主串S和模式T中当前正待比较的字符位置,i的初值为pos,j的初值为1。
2、如果两个串均为比较到串尾(i<=S.length&&j<=T.length),则:
- S.ch[i]==T.ch[j]时,指针后移比较下一个字符,i++,j++。
- S.ch[i] !=T.ch[j]时,j=next[j]。
3、如果j>T.length,证明模式已经全部匹配了,成功。返回位置i-T.length。
KMP算法实现:
int IndexKMP(SString S,SString T,int pos){
int i=pos,j=1;
while(i<=S.length&&j<=T.length){
if(j==0||S[i]==T[j]){//next[1]一定为0,j为0,继续比较下一个
i++;
j++;
}else{
j=next[j];//next数组已知,可通过手算得到
}
}
if(j>T.length) return i-T.length;//成功
else return false;//匹配失败
}
其中的next数组可以通过手算得到,也可以通过机算得到,但是逻辑有些不同。
手算:
当第j个字符匹配失败,由模式串T前j-1个字符组成的串即为s1。
next[j]=s1的最长相等前后缀长度+1。特别地,next[1]=0。
根据上述方法,其实在任何模式串中,next[1]=0,next[2]=1。
机算:
void get_next(SString T,int next[]){
next[1]=0;//已知
int i=1,j=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;
j++;
next[i]=j;
}else{
j=next[j];
}
}
}
以上即为KMP算法。但是,next数组可以进一步优化,将优化后的next数组记为nextval数组。
同样的,可以分为手算和机算实现。
手算:
先求next数组,再由next数组求nextval数组。
1、nextval[1]=0。
2、nextval[j](nextval[2]~nextval[T.length]):
- 如果第j个字符和第next[j]个字符相同,更新为第next[j]个字符的nextval值。即nextval[j]=nextval[next[j]]。
- 不相同,不更新。nextval[j]就还是等于next[j]。
手算的逻辑:
//手算逻辑
void get_nextval(SString T,int next[],int nextval[]){
nextval[1]=0;
for(int j=2;j<=T.length;j++){
if(T.ch[j]==T.ch[next[j]]){
nextval[j]=nextval[next[j]];
}else{
nextval[j]=next[j];
}
}
}
机算:
void get_nextval(SString T,int nextval[]){
nextval[1]=0;//已知
int i=1,j=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
i++;
j++;
if(T.ch[i]!=T.ch[j]){
nextval[i]=j;
}else{
nextval[i]=nextval[j];
}
}else{
j=nextval[j];
}
}
}
2 数组
多维数组可以看成是线性表的一种推广,即线性表的数据元素自身又是一个数据结构。如二维数组可以看成是一个数据元素为线性表的线性表。
3 广义表
广义表是线性表的推广,也称为列表。广义表一般记作:
LS=(a1,a2,a3,……,an)
其中ai(1<=i<=n)可以是单个元素,也可以是广义表,即原子和子表。
由于广义表中的数据元素可以有不同的结构(原子或列表),因此难以用顺序存储结构表示,通常采用链式存储结构。