5-串¶

串：0或N个字符组成的有限序列，一种限定了元素为字符的线性表。

长度：字符个数
空串：0个元素
子串：串中任意连续字符组成的子序列
主串：包含子串的串

存储结构：串的实现可以用定长数组，也可以用变长的动态数组实现。

// 定长数组
#define MAX_SIZE 100

typedef struct {
    char str[MAX_SIZE + 1];
    int length;
}Str;

// 变长动态数组

typedef struct {
    char *str;   // 串
    int length;  // 串长度
}Str;

基本操作：赋值、取长度、比较、连接、复制、求子串、清空

当然串的操作还有非常多，比如返回字符在字符串中的位置，返回子串在字符串中的位置等等。

代码实现¶

定义¶

// DataElement.h

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define OK 1
#define ERROR 0

typedef int Status;

/** 串结构 */
typedef struct {
    char* str;
    int length;
} Str;

#endif // DATAELEMENT_H_INCLUDED

赋值¶

Status Assign(Str* s, char* ch)
{
    int ch_length = 0;
    char* c = ch;
    while (*c) { // 计算ch字符串长度
        ++ch_length;
        ++c;
    }

    if (ch_length == 0) { // 如果是空串
        s->str = NULL;
        s->length = 0;
        return OK;
    } else {
        // 开辟一块空间，+1 是为了放 \0 结束符
        s->str = (char*)calloc(ch_length + 1, sizeof(char));
        // 分配失败返回ERROR
        if (s->str == NULL)
            return ERROR;

        // 逐个将ch的字符复制到s->str
        for (int i = 0; i <= ch_length; i++)
            s->str[i] = *(ch + i);

        s->length = ch_length;
        return OK;
    }
}

取长度¶

int Length(Str* s)
{
    return s->length;
}

比较¶

int compare(Str* s1, Str* s2)
{
    // 遍历时将两个字符串逐个比较
    for (int i = 0; i < s1->length && i < s2->length; i++) {
        if (s1->str[i] != s2->str[i]) {
            return s1->str[i] - s2->str[i];
        }
    }
    return 0;
}

遍历是串中较为重要的操作。

逐个比较字符的ASCII码，

若s1 < s2，返回负数；
若s1 > s2，返回正数；
若s1 = s2，返回0.

连接¶

连接分两种情况讨论

一种是定长数组实现的字符串的连接
- 如果A有剩余空间且剩余空间大于B长度，循环B长度逐个复制到A
- 如果A无剩余空间或剩余空间小于B长度，将A扩容，再循环B长度逐个复制到A
一种是变长数组实现的字符串的连接

变长数组一般没有剩余空间的情况，后面的空间是否是空闲空间也无从得知，所以变长数组的字符串在连接时，通常是开辟一块新的空间，长度为A的长度+B的长度，然后遍历A，逐个复制到新字符串，遍历B，逐个复制到新字符串A的后面，最后补\0。

// 将 s2 连接到 s1 后面
char* contact(Str* s1, Str* s2)
{
    // 创建一块新字符串空间，长度为 s1 + s2
    char* new = (char*)calloc(s1->length + s2->length, sizeof(char));

    int i = 0;
    while (i < s1->length) { // 把 s1 逐个字符赋值给新字符串
        new[i] = s1->str[i];
        i++;
    }
    i = 0;
    while (i < s2->length) { // 把 s2 逐个字符赋值给新字符串
        new[s1->length + i] = s2->str[i];
        i++;
    }
    new[s1->length + s2->length] = '\0';
    s1->length += s2->length;
    s1->str = new; // 让 s1 指向新字符串

    return new;
}

复制¶

char* copy(Str* dest, Str* src)
{
    int count = src->length < dest->length ? src->length : dest->length;

    for (int i = 0; i < count; i++) {
        dest->str[i] = src->str[i];
    }
    dest->str[count] = '\0';
    return dest->str;
}

复制的时候，逐个将 src 字符串的字符复制到 dest 字符串。

要注意的是，假设 dest 的长度为10，src 的长度为5，则将 src 覆盖到 dest 上，dest 上后面的几个字符但是不会被读取到

反过来则是 src 将 dest 整个覆盖，但是只能覆盖 dest 的字符个数，src 超出 dest 长度的字符会被丢弃。

所以在调用时要保证 dest 的长度比 src 的长。

Case 1Case 2

取子串¶

/**
 * @description 从主串 base 的第 idx+1 个开始截取 len 个字符组成新的字符串
 * @param base 主串
 * @param idx 截取的起始下标
 * @param len 截取字符数
 */
char* sub(Str* base, int idx, int len)
{
    // 越界或主串为空
    if (idx + len > base->length || base->length == 0) {
        return NULL;
    }

    // 分配空间，然后逐字符复制
    char* substring = (char*)calloc(len, sizeof(char));
    for (int i = 0; i < len; i++) {
        substring[i] = base->str[idx + i];
    }
    return substring;
}

清空¶

Status clear(Str* s)
{
    if (s->length == 0) {
        return OK;
    }
    for (int i = 0; i < s->length; i++) {
        s->str[i] = '\0';
    }
    s->length = 0;
    return OK;
}

串的模式匹配¶

Note

对某子串的定位操作。

主串也称作 目标串

子串也称作 模式串

思想：从主串首个位置起和模式串的首个字符比较，若相等，则逐一比较后续字符，否则从主串第二个字符开始，逐一比较后续字符，以此类推。匹配成功则返回模式串在主串中的位置，匹配失败则返回0.

KMP 算法¶

模式匹配主要有 BF 算法 和 KMP 算法。

BF 算法主要是一种暴力穷举，和上面介绍的思想一致。

KMP 算法就聪明多了，该算法充分体现了“失败是成功他妈”的道理，积极从上一次失败匹配中汲取信息，并应用到下一次匹配中，比起 BF 那种穷举法，KMP 会将模式串与失败位置对其再重新匹配。