考研数据结构与算法（四）字符串

考研数据结构与算法（四）字符串

一、基本概念

串（String）是由零个或多个字符组成的有限序列。一般记为： S = ′ a 1 a 2 … … a n ′ ( n > = 0 ) S='a_1a_2……a_n'(n>=0) S=′a1​a2​……an′​(n>=0) 其中 S S S 是串名，单引号括起来的字符串序列是串的值， a i a_i ai​ 可以是字母、数字、或者其他字符，串中的 n n n 代表的是串的长度，当 n = 0 n=0 n=0 时，称其为空串

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定在字符集中，在基本操作上也有很大的区别，例如线性表的操作通常是单个元素的操作，而串的操作是以子串（子串的大小是不确定的）为操作对象。

1.1 主串和字串

串中任意个连续的字符组成的子序列称为该串的 子串 。包含字串的串则称为该子串的 主串

例如，假设有一字串 abb 那么它的 主串 可以是 aabbb 也可以是 abbbc 或者其他任何包含该子串的串

1.2 串的操作函数 串的操作函数作用Concat(&T,S1,S2)将字符串 S 1 S1 S1 和 S 2 S2 S2 连接并复制给 T T T 串SubString(&Sub,S,pos,len)将字符串 S S S 从 p o s pos pos 到 p o s + l e n pos+len pos+len 的子串取出并赋值给 S u b Sub Sub 串StrCopy(&T,S)将字符串 S S S 的值复制给字符串 T T TStrLength(S)求字符串 S S S 的长度Index(S,T)如果 S S S 中存在子串 T T T 则返回第一次出现的位置，否则返回 0 0 0 二、存储结构 2.1 定长顺序存储

和线性表的顺序存储结构相同，用一组连续的空间存储字符序列，结构如下：

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];
    int length;
}SString;

串的长度最多能为 MAXLEN 但是考虑到字符串以 KaTeX parse error: Undefined control sequence: \0 at position 1: \̲0̲ 结尾，也就是需要给字符串结束标识符留一个位置，那么实际的串长为 MAXLEN-1 但是由于我们这里设计该字符串结构的时候有一个 length 表示，所以我们可以使用到完整的 MAXLEN 的长度

2.2 堆分配存储

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列 ，但它们的存储空间是在程序执行过程中 动态分配 得到的，结构如下：

typedef struct {
    char *ch;
    int length;
}SString;

我们在堆的这个自由存储区去定制话分配空间，在C语言中，通过 malloc 和 free 函数可以完成动态存储管理。利用 malloc ）为每个新产生的串分配一块实际串长所需的存储空间，若分配成功则会返回一个指向分配空间起始地址的一个指针，作为字符串的基地址，我们则可以通过 ch 指针来访问这块空间，若分配失败，则返回 NULL 。

当然这里通过堆分配存储的话，需要我们自动管理内存，所以每当我们 malloc 了一个空间，我们需要在合适的地方去 free 掉，不然申请的空间越来越多最后就会没有空间可以使用，造成内存泄漏

2.3 块链存储

这个就类似线性表的链式存储，不同的是对于每一个单元结点我们都将其当作一个定长字符串也就是一个块，那么不难得出如下结构：

#define MAXLEN 255
typedef struct SString{
    char ch[MAXLEN];
    struct SString * next;
}SString;

当然如果对于每一块的长度不定的话，我们同样可以通过堆空间的分配来做

#define MAXLEN 255
typedef struct SString{
    char *ch;
    int length;
    struct SString * next;
}SString;

那么可以想象到这个结构：

三、串的匹配算法

在串 S S S 中找到子串 T T T 第一次出现的位置，如果没找到则返回 − 1 -1 −1

3.1 暴力匹配

我们将串 T T T 不断的从串 S S S 的第一个位置往后一一比较，如果匹配失败则整体往后移动一位，操作如下图所示：

不难得出代码：

int Index(SString S,SString T) {
    for(int i = 0,len = S.length - T.length + 1;i