串（String）

逻辑结构：受限线性表

存储结构：

定长顺序存储表示

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

堆分配存储表示

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

链式存储表示

1
2
3
4
5
6
//size被自定义，表示一个结构体中存放多少个字符
#define size 4
typedef struct{
    char ch[size];
    LString *next;
}LString;

串的简单模式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int SMatch(char a[], char b[]) {
    char *ptra = a;
    char *temp = ptra;
    char *ptrb = b;
    while (*ptra != '\0') {
        temp = ptra;
        ptrb = b;
        while (*ptra == *ptrb && *ptrb != '\0') {
            ptra++;
            ptrb++;
        }
        if (*ptrb == '\0') {
            return 1;
        }
        ptra = temp + 1;
    }
    return 0;
}

int main(void) {
    char a[] = "ijijij";
    char b[] = "ijijij";
    printf("%d", Com(a, b));
}

简单模式匹配算法的时间复杂度为O(mn)