数据结构之串

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 3k 阅读时长 ≈ 3 分钟

第四章串

第一节串的概念和存储结构

1.串的概念

​ 由0个或多个字符组成的有效序列，一般记作
$$
S=‘a_1a_2a_3…a_n’~~~（n≥0）
$$

2.串的存储结构和基本算法的实现

（1）定长顺序存储表示

1
2
3
4
5
#define MAXLEN 255		//预定义最大串长255
typedef struct{
	char ch[MAXLEN];		//每个分量存储一个字符
	int length;				//串的实际长度
}SString;

（2）堆分配存储表示

1
2
3
4
typedef struct{
    char *ch;		//按串长分配存储区，ch指向串的基地址
    int length;		//串的长度
}HString;

（3）基本操作

1
2
3
4
5
6
7
8
9
10
StrAssign(&T,chars)：赋值操作。把串T赋值为chars。
StrCopy(&T,S)：复制操作。由串S复制得到串T。
StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrLength(S)：求串长。返回串S的元素个数。
ClearString(&S)：清空操作。将S清为空串。
Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
DestroyString(&S)：销毁中。将串S销毁。

第二节串的匹配算法

1.BF算法（简单模式匹配算法）

时间复杂度：最好O（n），最坏O（nm）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
int BF(string S,string T,int pos)
{
    int i = pos;
    int j = 1;
    while( i <= S.size() && j <= T.size() )
    {
        if( S[i-1] == T[j-1] )
        {
            i++;
            j++;
        }
        else
        {
            i = i-j+2;//i为母串S的匹配失败的位置，j为模式串S的匹配失败的位置，i-j为S第一次匹配位置之前的长度，
            //+2的原因是一个1是本次匹配的开始位置 ，另一个1是下一次匹配的开始位置。
            j = 1;//模式串的下一次匹配开始位置依旧是第一个字符
        }
    }
    if( j > T.size() )
        return i - T.size();
    return 0;
}
int main()
{
    int pos;
    string S,T;
    while( true )
    {
        cout<<"请输入母串：";
        cin>>S;
        cout<<"请输入模式串：";
        cin>>T;
        cout<<"请输入在母串中开始寻找的位置（小于等于"<<S.size()<<"）：";
        cin>>pos;
        while ( pos > S.size() )
        {
            cout<<"请重新输入在母串中开始寻找的位置（小于等于"<<S.size()<<"）：";
            cin>>pos;
        }
        cout<<"模式串在自母串第 "<<pos<<" 位开始出现的位置为 "<<BF(S,T,pos)<<endl<<endl;
    }
}

2.KMP算法

（1）next数组

以‘ababa’举例说明：

  • 'a’的前缀和后缀都是空集，最长相等前后缀长度为0；
  • 'ab’的前缀为{a}，后缀为{b}，{a}且{b}=空集，最长相等前后缀长度为0；
  • 'aba’的前缀是{a,ab}，后缀是{a,ba}，{a,ab}且{a,ba}={a}，最长相等前后缀长度为1；
  • 'abab’的前缀是{a,ab,aba}，后缀是{a,ba,bab}，{a,ab,aba}且{a,ba,bab}={a}，最长相等前后缀长度为1；
  • 'ababa’的前缀是{a,ab,aba,abab}，后缀是{a,ba,aba,baba}，{a,ab,aba,abab}且{a,ba,aba,baba}={a,aba}，最长相等前后缀长度为3；

时间复杂度：O（n+m）；优点：主串不回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <string.h>
void Next(char*T,int *next){
    int i=1;
    next[1]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int KMP(char * S,char * T){
    int next[10];
    Next(T,next);//根据模式串T,初始化next数组
    int i=1;
    int j=1;
    while (i<=strlen(S)&&j<=strlen(T)) {
        //j==0:代表模式串的第一个字符就和当前测试的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
        if (j==0 || S[i-1]==T[j-1]) {
            i++;
            j++;
        }
        else{
            j=next[j];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
        }
    }
    if (j>strlen(T)) {//如果条件为真，说明匹配成功
        return i-(int)strlen(T);
    }
    return -1;
}
int main() {
    int i=KMP("ababcabcacbab","abcac");
    printf("%d",i);
    return 0;
}

（2）nextval数组

j 1 2 3 4 5 6 7 8 9
模式串T a b a b a a a b a
next 0 1 1 2 3 4 2 2 3
nextval 0 1 0 1 0 4 2 1 0