Skip to content

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.

连接

连接分两种情况讨论

  1. 一种是定长数组实现的字符串的连接

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

    变长数组一般没有剩余空间的情况,后面的空间是否是空闲空间也无从得知,所以变长数组的字符串在连接时,通常是开辟一块新的空间,长度为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 的长。

取子串

/**
 * @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 会将模式串与失败位置对其再重新匹配。