数据结构-串(4)

4.1 串的定义和实现

串的定义

串，即**字符串（String）**是由零个或多个字符组成的有限序列。一般记为

S=‘a1a2…. an’

其中，S是串名，单引号括起来的字符序列是串的值。

\(n=0\) 的串，称为空串（用 \(\emptyset\) 表示）

串中的连续子序列被称作该串的子串，而该串就是该字串的主串。子串在主串中的位置，用以其第一个字符在主串中的对应位置表示。

串的存储结构

1.定长顺序存储表示

1
2
3
4
5
#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

2.堆分配存储表示

1
2
3
4
typedef struct{
    char *ch;
    int length;
}HString;

在 \(C\) 语言中，存在一个称为堆 的自由存储区。可通过调用 malloc 为新生成的串动态分配一块大小等于串长的连续存储空间。分配成功则返回起始地址的指针，否则返回NULL。

3.块链存储

类似于线性表的链式存储结构，串也可采用链表形式存储。考虑到串的特殊性（每个元素仅为单个字符），每个结点可存放一个或多个字符，每个结点称为一个块，最后一个块不满时，用 “#” 补齐。

4.2 串的模式匹配

简单的模式匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length&&j<=T.length()){
        if(T.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; // 匹配失败
}

KMP算法

求解 \(next\) 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
        }else
            j=next[j]; 
    }
}
int Index_KMP(SString S,SString T,int next[]){
    int i=1,j=1;
    while(i<=S.length&&<=T.length){
        if(j==0||S.ch[i]==S.ch[j]){
            ++i;++j; // 继续比较后继字符
        }else 
            j = next[j]; // 模式串向右移动
    }
    if(j>T.length)
        return i-T.length; // 匹配成功
    else return 0;
}

KMP算法的进一步优化

优化 \(next\) 数组，当模式串字符 \(p_j=p_{next[j]}\) 进行特殊处理

匹配算法不变

1
2
3
4
5
6
7
8
9
10
11
void get_next(SString T,int next[]){
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;++j;
            if(T.ch[i]!=T.ch[j]) next[i]=j;
            else next[i]=next[j];
        }else j = next[j];
    }
}