串文档之串

串 定义 概念

串是字符串的简称，是计算机中常见且非常重要的一种数据结构。

串本质上是由零个或多个字符组成的有限序列。

注：

• 串中字符个数是可以是零个，被称为空串。如：""。
• 串中的字符个数也可以是多个。如："helll wolrd"。
• 但串中的字符个数必须是有限个。
• 串中字符的个数称为串的长度。

如用 C 语言定义一个名为 str 的串：

char str[] = "abcdef";// 一个串

如用 Java 语言定义一个名为 str 的串：

String str = "abcdefg";// 一个串

注：通常串用一个字符数组来表示，在 Java 中 String 底层仍然是字符数组。从这个角度来看，数组 str 内存储的字符分别为 'a'、'b'、'c'、'd'、'e'、'f' 和 ''，其中 '' 是特别的，作为编译器识别串结束的标记。而串中字符实际为 'a'、'b'、'c'、'd'、'e'、'f'。因此数组 str 的长度为 7，而串 str 的长度为 6。

串中还有一些概念：

• 子串：串中任意连续的字符组成的子序列称为该串的子串。如串 abcd 中 a、ab、bc、abcd 都是该串的子串。
• 主串：包含子串的串称为主串。
• 字符的位置：通常把某个字符在串中的序号称为这个字符的位置。如串 abcde 中 'c' 字符的位置序号是 3，但如果用数组下标的方式说明 'c' 字符的位置则是 2。通常将子串第一个字符的位置作为子串在主串中的位置。
• 空格串：空格也是字符，也可以组成串。通常由一个或多个空格组成的串称为空格串。但注意，区分空格串与空串，空格串不是空串。

串的逻辑结构和线性表类似，串是限定了元素为字符的线性表。从操作上来看，串与线性表有很大的区别，线性表的操作主要针对表内的某一个元素（如查找、插入或删除某个元素），而串的操作主要针对串内的一个子串（如查找、插入或删除一个子串）。

但也因此串的许多操作的算法思想可以借鉴线性表操作的算法思想，它们是相近的。

结构体

定长顺序存储表示结构体定义：

typedef struct {
    
    char ch[MAXSIZE+1];// 存储字符，多出的一个位置存储字符串的结尾字符 ''；MAXSIZE 是已经定义好的常量，表示串的最大长度
    
    int length;
} String;

变长分配存储表示结构体定义：

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

注：

• 变长分配存储表示又叫做动态分配存储表示，因为是在程序执行过程中根据需要动态分配。所谓的动态分配就是需要多少个字符空间就分配多少个，而不是像定长分配那样先分配一个 MAXSIZE+1 的空间，可能会造成空间浪费。
• 这种方式在使用时会使用函数 malloc() 来分配一个长度为 length、类型为 char 型的连续存储空间，分配的空间可以用 free() 函数释放掉。如果用函数 malloc() 分配存储空间成功，则返回一个指向起始地址的指针，作为串的基地址，通常也是串第一个字符的地址，这个地址由 ch 指针来指向；如果分配失败，则返回 NULL。
• 对比两种分配方式，发现变长分配存储表示有顺序存储结构的特点（实际上也可以通过下标来访问），操作中还可以根据实际需要来设定串长，更加灵活，更常用。

除此之外，还有一种块链存储表示，就是用链式存储结构，这里不多说明，因为不常用。

特点

无。

基本操作 概述

串的常见操作如下：

• void init(String *str)：串的初始化。其中 str 表示未初始化的串。

• int assign(String *str, char *ch)：串的赋值操作不能直接用 = 直接实现。因为串是一个数组，如果将一个数组的值赋给另一个数组，直接用 = 是不可行的，必须对数组中的每个元素进行逐一赋值操作。功能是将一个常量字符串 ch 赋值给 str。其中 str 是未初始化的字符串，待赋予值；ch 是一个常量字符串。如果赋值成功则返回 1，否则返回 0 表示赋值失败。

• int copy(String *dest, String src)：复制字符串，从串 src 复制得到串 dest。其中 dest 表示目标串，是复制后的串；src 是源字符串，待复制的字符串。如果复制成功则返回 1，否则返回 0。

• int isEmpty(String str)：判断串是否为空。其中 str 表示串。如果串为空则返回 1，否则返回 0 表示非空。

• int length(String str)：获取字符串的长度。其中 str 表示字符串。返回字符串的实际字符个数，即长度。

• int compare(String s1, String s2)：比较字符串的大小。其中 s1 表示第一个待比较的字符串；s2 表示第二个待比较的字符串。如果返回正数则表示串 s1 大于串 s2；如果返回负数表示串 s1 小于串 s2；如果返回 0 表示两个串完全相等。

• int concat(String *str, String s1, String s2)：将两个串首尾相接，合并成一个字符串。其中 str 用来存储合并后的字符串；s1 表示待合并的第一个字符串；s2 表示待合并的第二个字符串。如果合并成功则返回 1，否则返回 0 表示合并失败。

• int substring(String *substr, String str, int pos, int len)：求从给定串中某一位置开始到某一位置结束后的串。其中 substr 用来存储得到的子串；str 是总串；pos 是起始位置，从 0 开始；len 表示待求的子串的长度。如果获取子串成功则返回 1，否则返回 0 表示失败。

• int index(String str, String substr)：对串 str 中某子串 substr 进行匹配。其中 str 是主串；substr 是子串，或称为模式串。如果匹配成功则返回子串 substr 在主串 str 中的位置；如果匹配不成功，则返回一个可区别于主串所有位置的标记。

• void clear(String *str)：清空串。其中 str 是待清空的字符串。

init

初始化串。由于用结构体声明的一个串（String str），其实是不能直接使用的，因为它的 ch 指针指向和 length 都不是初始状态。例如：

为了能够之后的使用不出现什么问题，所以我们要将 ch 指针指向 NULL，同时将 length 置为 0 表示是空串。初始化后如图：

实现步骤：

• 将串的 ch 指针指向 NULL。
• 将串的 length 置为 0 表示空串。

实现代码如下：

void init(String *str) {
    str->ch = NULL;
    str->length = 0;
}

assign

赋值操作。与普通变量赋值操作不同，串的赋值操作不能直接用 = 直接实现。因为串是一个数组，如果将一个数组的值赋给另一个数组，直接用 = 是不可行的，必须对数组中的每个元素进行逐一赋值操作。如下函数的功能是将一个常量字符串赋值给 str，赋值操作成功则返回 1，否则返回 0。以 ch="hello world" 为例如图所示：

实现步骤：

• 参数校验，如果串 str 是非空串，那么释放掉原来的空间。
• 统计常量字符串 ch 中字符个数 len。
• 如果常量字符串的长度 len 为 0 则直接将 str 初始化为空串然后返回；
• 如果常量字符串的长度 len 不为 0，则为 str 分配长度为 len+1 的存储空间，多分配一个存储空间是为了存储串的结束标记 ''字符。
• 如果分配成功则扫描常量字符串的每一个字符，将其一一赋值给新串 str。
• 赋值完毕后，修改新串的长度 length 为常量字符串的长度 len。
• 最后返回 1 表示赋值成功。

实现代码如下：

int assign(String *str, char *ch) {
    // 0.参数校验，如果 str 中已有字符，那么释放原串空间，因为我们会给它重新分配空间
    if (str->ch != NULL) {
        free(str->ch);
        str->ch = NULL;
    }

    // 1.统计常量字符串 ch 中的字符个数，只有知道它的字符个数，我们才能清楚为 str 分配多少个字符空间
    // 局部变量，存储常量字符串 ch 中的字符个数
    int len = 0;
    // 注意，我们不能直接操作 ch，因为是一个指针变量，在下面的操作后我们会移动指针，会修改掉 ch 原本的值，后面如果需要再使用就不是传入的参数值，所以要创建一个临时局部变量引用它的值来进行操作
    char *c = ch;
    // 从头到尾扫描常量字符串，以结束标记 '' 作为循环结束条件
    while (*c != '') {
        // 计数器加一
        len++;
        // 指针加一，继续下一个字符
        c++;
    }

    // 2.为串 str 分配空间并赋值
    // 2.1 如果常量字符串长度为 0，那么串 str 也该为一个空串
    if (len == 0) {
        str->ch = NULL;
        str->length = 0;
        return 1;
    }
    // 2.2 如果常量字符串长度不为 0，那么将常量字符串中所有字符赋给串 str
    else {
        // 2.2.1 给串分配 len+1 个存储空间，多分配一个空间是为了存放 '' 字符
        str->ch = (char *) malloc(sizeof(char) * (len + 1));
        // 2.2.2 判断是否分配空间成功
        // 2.2.2.1 如果分配空间失败，则返回 0
        if (str->ch == NULL) {
            // 如果分配空间失败，则返回 0
            return 0;
        }
        // 2.2.2.2 如果分配空间成功，则遍历常量字符串中的每个字符，依次赋给串 str
        else {
            // 局部变量，保存常量字符串 ch 的首地址，后续用于操作
            c = ch;
            // 2.2.2.2.1 扫描整个常量字符串，依次将每个字符赋给新串 str
            for (int i = 0; i <= len; i++) {// 之所以在循环条件中使用 <=。是为例将常量字符串最后的 '' 字符也复制到新串中作为结束标记
                str->ch[i] = *(c + i);// 其实也可以使用 str->ch[i]=c[i];
            }
            // 2.2.2.2.2 给新串赋予长度，即常量字符串的长度
            str->length = len;
            // 2.2.2.2.3 返回 1 表示赋值成功
            return 1;
        }
    }
}

copy

复制串操作。同上面的赋值操作类似，不同复制操作两个参数都是串结构体 String 类型的，而非常量字符串。将一个串中所有字符复制到另外一个串中。如果复制成功则返回 1，否则返回 0 表示复制失败。

实现步骤：

• 参数校验。
• 给目标串 dest 分配跟源串 src 一样长度加一的存储空间。
• 然后从头到尾扫描源串 src 中所有字符，依次赋值给目标串 dest。
• 将目标串 dest 的长度 length 修改为跟源串 src 一样的长度。
• 最后返回 1 表示复制成功。

实现代码如下：

int copy(String *dest, String src) {
    // 0.参数校验
    // 0.1 参数校验，如果 dest->ch 不为 NULL，则释放其空间
    if (dest->ch != NULL) {
        free(dest->ch);
        dest->ch = NULL;
    }
    // 0.2 参数校验，如果 src.ch 为 NULL，那么 dest 串一定是空串，返回 1 表示复制成功
    if (src.ch == NULL || src.length == 0) {
        dest->ch = NULL;
        dest->length = 0;
        return 1;
    }

    // 1.复制字符串
    // 1.1 为 str->ch 分配长度为 src.length+1 个空间，多分配一个空间是为了存放 '' 字符
    dest->ch = (char *) malloc(sizeof(char) * (src.length + 1));
    // 1.2 将串 src 中的每个字符依次赋值给串 dest
    for (int i = 0; i <= src.length; i++) {
        // src.ch 表示串 src.ch 的首地址
        // *src.ch 可以取出串 src.ch 的首个字符
        // *(src.ch+i) 可以取出 src.ch 的第 i 个字符
        // 其实也可以用数组下标的方式取值，如：dest->ch[i]=src.ch[i];
        dest->ch[i] = *(src.ch + i);
    }
    // 1.3 将串 src 的长度也赋值给 dest 的长度
    dest->length = src.length;
    // 1.4 返回 1 表示复制成功
    return 1;
}

isEmpty

判断串是否为空。

实现步骤：

• 只需要判断串长度 length 是否等于 0 即可。

实现代码如下：

int isEmpty(String str) {
    // 判断串的长度是否为零，即可以判断它是否是空串
    return str.length == 0;
}

length

获取串的长度，由于有一个成员 length 记录串中字符个数，所以直接返回即可。不需要从头到尾扫描串来统计字符个数。

实现步骤：

• 直接返回串的成员 length 即可。

实现代码如下：

int length(String str) {
    // 由于串的 length 属性记录了串的长度，所以直接返回即可，不需要遍历串中的所有字符去统计字符个数
    return str.length;
}

compare

串比较操作。通常比较串中字符的大小，是比较它们的 ASCII 码值大小。两个串 s1 和 s2 比较大小的规则如下：

• 如果串 s1 和 s2 中待比较的字符是 c1 和 c2，如果 c1 的 ASCII 码值小于 c2 的 ASCII 码值，则返回串 s1 小于 s2 的标记。通常是 c1-c2 ，即返回一个负数表示小于的情况。
• 如果 c1 的 ASCII 码值大于 c2 的 ASCII 码值，则返回串 s1 大于 s2 的标记。通常是 c1-c2，即返回一个正数表示大于的情况。
• 如果 c1 的 ASCII 码值等于 c2 的 ASCII 码值，则继续两个串中的下一对字符。
• 经过上述步骤，在没有比较出串 s1 和 s2 大小的情况下，先结束的为较小串，即 s1.length-s2.length 结果就是比较结果，两串同时结束则返回两串相等的标记，即 0。

以 s1="hello"; s2="hellx" 为例如图所示：

实现步骤：

• 声明变量 i，同时用来遍历串 s1 和 s2。
• 从头到尾同时扫描串 s1 和 s2，如果当前字符不相等，则返回它们之差。即如果差是一个正数则表示 s1 比 s2 大，如果是一个负数则表示 s1 比 s2 小。
• 如果当前字符相等，则继续判断两个串的下一对字符。
• 扫描结束后，返回 s1.length-s2.length，如果返回一个正数表示串 s1 比串 s2 长则表示 s1 更大；如果返回一个负数表示串 s1 比串 s2 短则表示 s2 更大；如果返回 0 表示两个串一样的长，并且相等。

实现代码如下：

int compare(String s1, String s2) {
    // 局部变量，同时用来遍历串 s1 和 s2
    int i = 0;
    // 同时扫描串 s1 和 s2 中相同下标处的字符
    while (i < s1.length && i < s2.length) {
        // 如果当前两个字符不等，那么两个串一定不等，两个字符的差值就是对应 ASCII 码的差值，如果是正数则表示前者的 ASCII 码值更大，那么也就是串更大，否则相反
        if (s1.ch[i] != s2.ch[i]) {
            return s1.ch[i] - s2.ch[i];
        }
        // 如果当前两个字符相等，则变量加一继续比较下一对字符
        i++;
    }
    // 循环完成后，表示前 i 个字符都相等并且两个串的长度不等，那么谁更长就更大
    return s1.length - s2.length;
}

concat

串连接操作，将两个串首尾相接，合并成一个新字符串。以 s1="hello"; s2="world" 为例如图所示：

实现步骤：

• 参数校验。
• 首先给新串 str 分配长度为 s1.length+s2.length+1 的空间，多分配一个空间是用来存放串的结束标记 '' 的。
• 接着将串 s1 中所有字符依次复制到串 str 中。
• 接着将串 s2 中所有字符依次复制到串 str 中，但是从 s1.length 位置开始复制的。
• 修改新串 str 的长度 length 为 s1.length+s2.length，表示合并后串的长度。
• 最后返回 1 表示连接成功。

实现代码如下：

int concat(String *str, String s1, String s2) {
    // 0.参数校验
    // 0.1 参数校验，如果 str 是非空串，则释放其原本的空间，因为要存储合并后的串内容
    if (str->ch != NULL) {
        free(str);
        str->ch = NULL;
    }
    // 0.2 参数校验，如果两个串的长度之和为 0，那么新串一定是一个空串
    if (s1.length + s2.length == 0) {
        str->ch = NULL;
        str->length = 0;
        return 1;
    }

    // 1.连接串 s1 和 s2
    // 1.1 为串 str->ch 分配空间，长度应该为 s1.length+s2.length+1，多出来的一个空间用来存放串的结束标记 '' 字符
    str->ch = (char *) malloc(sizeof(char) * (s1.length + s2.length + 1));
    // 如果分配空间失败则返回 0
    if (str->ch == NULL) {
        return 0;
    }
    // 1.2 先将串 s1 中的所有字符复制到串 str 中
    for (int i = 0; i < s1.length; i++) {
        str->ch[i] = *(s1.ch + i);
    }
    // 1.3 接着将串 s2 中的所有字符复制到串 str 中
    for (int i = 0; i <= s2.length; i++) {// 将串 s2 中的结束标记 '' 也复制过来
        str->ch[s1.length + i] = *(s2.ch + i);
    }
    // 1.4 为连接后的串指定长度
    str->length = s1.length + s2.length;
    // 1.5 返回 1 表示连接成功
    return 1;
}

substring

求子串操作。求从给定串中某一位置开始到到某一位置结束的串的操作叫做求子串操作，规定开始位置总是在结束位置前边。以下是求 str 串中从 pos 位置（包括本身）开始，长度为 len 的子串，子串用 substr 进行保存。以 str="hello world"; pos=3; len=6 为例如图所示：

实现步骤：

• 参数校验。
• 首先为子串分配长度为 len+1 的存储空间，多出来的一个空间用来存放串的结束标记 ''。
• 然后将主串中第 pos 位置（包括本身）之后的 len 个字符复制到子串中。
• 将子串最后一个位置赋予串的结束标记 ''。
• 置子串的长度为 len。
• 最后返回 1 表示求子串成功。

实现代码如下：

int substring(String *substr, String str, int pos, int len) {
    // 0.参数校验
    // 0.1 校验参数 pos，位置必须在 [0, str.length) 之间，即下标的范围内，否则就是不合法
    if (pos < 0 || pos >= str.length) {
        return 0;
    }
    //  0.2 校验参数 len，子串长度不能小于 0；也不能大于 length-pos
    if (len < 0 || str.length - pos < len) {
        return 0;
    }
    // 0.3 如果要求的子串长度为 0，那么返回的子串为空串，直接返回即可
    if (len == 0) {
        substr->ch = NULL;
        substr->length = 0;
        return 1;
    }

    // 1.求子串
    // 1.1 为子串分配长度为 len+1 的空间，多出来的一个空间用来存放串的结束标记 ''
    substr->ch = (char *) malloc(sizeof(char) * (len + 1));
    // 1.2 将主串中第 pos 个位置（包括本身）之后的 len 个字符复制到子串中
    int i = 0;
    for (i = 0; i < len; i++) {
        // 星号用来取值，其实也可以写成这样：substr->ch[i]=str.ch[pos+i];
        substr->ch[i] = *(str.ch + pos + i);
    }
    // 1.3 让串的最后一个字符是 ''，表示是串的结束标记
    substr->ch[i] = '';
    // 1.4 置子串的长度为 len
    substr->length = len;
    // 1.5 返回 1 表示求子串成功
    return 1;
}

index

简单模式串匹配，对一个串中某子串进行定义。算法的基本思想是：从主串的第一个位置（下标为 0）起和子串的第一个字符开始比较，如果相等，则继续逐一比较后续字符；如果不相等则从主串的第二个字符开始，再重新用上一步的方法与子串中的字符做比较。以此类推，直到比较完子串中的所有字符。若匹配成功，则返回子串在主串中的位置；若匹配失败，则返回一个可用于区别主串所有位置的标记，如 ''。以 str="helxworhellold"; substr="hello" 为例如图所示：

实现步骤：

• 声明变量 i 和 j，分别用于扫描主串和子串，初始为 0，表示串中的第一个字符的位置。
• 同时扫描主串和子串中的所有字符，比较 i 和 j 所指向的字符是否相等，如果相等则都加一，继续比较主串和子串中的下一对字符。
• 如果不相等，则恢复 i 为 i-j+1，即下一个字符；置 j 为 0，表示又从子串的第一个字符开始比较。
• 扫描完成后，如果 j==substr.length 表示子串存在于主串中，则返回子串在主串中第一次出现的位置。否则返回 '' 表示未找到。

实现代码如下：

int index(String str, String substr) {
    // 变量，i 记录串 str 中字符的下标，j 记录串 substr 中字符的下标
    int i = 0, j = 0;
    // 同时扫描主串 str 和子串 substr
    while (i < str.length && j < substr.length) {
        // 如果主串中的字符与子串中的字符相等，则继续比较下一对字符
        if (str.ch[i] == substr.ch[j]) {
            // 同时加一，指向串的下一个字符
            i++;
            j++;
        }
        // 如果不相等，那么就继续比较主串中下一个字符开始的串与子串，注意，需要恢复 i 和 j
        else {
            // 恢复主串中的 i，回到第 i-j 个字符，然后加一表示下一个字符
            i = i - j + 1;
            // 而 j 要恢复为子串的第一个字符的下标，即为 0，又要从 0 开始比较起走
            j = 0;
        }
    }
    // 如果循环结束 j 等于 length，那么表示主串中一定存在子串
    if (j == substr.length) {
        // 则返回子串第一次出现的位置
        return i - j;
    } else {
        // 如果不相等，则表示子串不存在于主串中，在返回标记 0
        return '';
    }
}

clear

清空串。

实现步骤：

• 释放串所指向的空间。
• 然后将其初始化，指针 ch 指向 NULL，长度 length 置为 0。

实现代码如下：

void clear(String *str) {
    // 释放原串空间
    if (str->ch != NULL) {
        free(str->ch);
    }
    // 然后指向 NULL 和将长度置为 0
    str->ch = NULL;
    str->length = 0;
}

注意事项 为什么要在结构体内定义一个 length

我们看串的结构体定义，无论是定长顺序存储还是变长顺序存储表示的结构体定义中都有一个 length 成员，该成员表示串的长度。

虽然串以 '' 字符作为串的结束标记，因此可以利用这一点来计算串的长度，但是求串长的时候需要扫描整个串来统计字符的出现个数，时间复杂度为 O(n)。

所以专门定义了一个变量 length 来存储串的长度，这样求串长就变成了时间复杂度为 O(1) 的操作。

注：不同参考资料中对串的结构体定义是有所不同的，有的用 '' 作为结束标记，有的不用。而本篇中同时用 '' 作为串尾的结束标记，也设定 length 表示串的长度。虽然会多一个存储空间，但更加方便。

练习题

• Example001-将串 str 中所有值为 ch1 的字符转换成 ch2 字符
• Example002-实现串 str 的逆转函数，如果 str 为空串，则什么都不做
• Example003-删除 str 中值为 ch 的所有字符
• Example004-从串 str 中的 pos 位置起，求出与 substr 串匹配的子串的位置
• Example005-采用定长顺序存储表示串，编写一个函数，删除串中从下标为 i 的字符开始的 j 个字符
• Example006-编写一个函数，将串 str1 中的下标 i 到下标 j 之间的字符（包括 i 和 j 两个位置上的字符）用串 str2 替换
• Example007-编写一个函数，计算一个子串在一个主串中出现的次数并且不考虑子串重叠
• Example008-构造串的链表结点数据结构（每个结点内存储一个字符），编写一个函数，找出串 str1 中第一个不在串 str2 中出现的字符