串的定义和实现

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统（如搜索引擎）、文本编辑程序（如 Word）、问答系统、自然语言翻译系统等，都是以字符串数据作为处理对象的。本章详细介绍字符串的存储结构及相应的操作。

串的定义

串（string）是由零个或多个字符组成的有限序列。一般记为 其中， 是串名，单引号括起来的字符序列是串的值；可以是字母、数字或其他字符；串中字符的个数 称为串的长度。 时的串称为空串（用 表示）。

• 串中任意个连续的字符组成的子序列称为该串的子串（包括空串）
• 包含子串的串相应地称为主串。
• 某个字符在串中的序号称为该字符在串中的位置（序号从1开始）。
• 子串在主串中的位置以子串的第一个字符在主串中的位置来表示。
• 当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。

需要注意的是，由一个或多个空格（空格是特殊字符）组成的串称为空格串（注意，空格串不是空串），其长度为串中空格字符的个数。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。

串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];  // 每个分量存储一个字符串
    int length;       // 串的实际长度
} SString;

串的实际长度只能小于等于 MAXLEN，超过预定义长度的串值会被舍去，称为截断。串长有两种表示方法：

• 一是如上述定义描述的那样，用一个额外的变量 length 来存放串的长度
• 二是在串值后面加一个不计入串长的结束标记字符“\0”， 此时的串长为隐含值。

在一些串的操作（如插入、联接等）中，若串值序列的长度超过上界 MAXLEN，约定用“截断”法处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

堆分配存储表示

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

#include <cstdlib>

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

int InitHString() {
    HString S;
    S.ch = (char *)malloc(MAXLEN * sizeof(char));
    S.length = 0;
}

在 C 语言中，存在一个称之为“堆”的自由存储区，并用 malloc() 和 free() 函数来完成动态存储管理。利用 malloc() 为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由 ch 指针来指示；若分配失败，则返回 NULL。已分配的空间可用 free() 释放掉。

上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅做简单介绍。

块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。最后一个结点占不满时通常用 # 补上。

typedef struct {
    char ch[4]; // 每个结点存多个字符
    struct StringNode * next;
} StringNode, * String;

串的基本操作

• StrAssign(&T,chars)：赋值操作。把串 T 赋值为 chars
• StrCopy(&T,S)：复制操作。由串 S 复制得到串 T
• StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE
• StrCompare(S, T)：比较操作。若 S>T，则返回值 >0 ；若S=T，则返回值 =0 ；若 S<T，则返回值 <0
• StrLength(S)：求串长。返回串 S 的元素个数
• SubString (&Sub,S,pos,len)：求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
• Concat (&T,S1,S2)：串联接。用 T 返回由 S1 和 S2 联接而成的新串
• Index(S,T)：定位操作。若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0
• ClearString(&S)：清空操作。将 S 清为空串
• DestroyString(&S)：销毁串。将串S销毁

不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中，串赋值 StrAssign、串比较 StrCompare、求串长 StrLength、串联接 Concat 及求子串 SubString 五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现；反之，其他串操作（除串清除 ClearString 和串销毁 DestroyString 外）均可在该最小操作子集上实现。

例如，可利用判等、求串长和求子串等操作实现定位函数 Index(S, T)。算法思想为：在主串 中取从第一个字符起、长度和串 相等的子串，与串 比较，若相等则求得函数值为 ，否则 值增1，直至串 中不存在和串 相等的子串为止。

实现求子串

// 求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
bool SubString(SString &Sub, SString S, int pos, int len) {
    // 子串范围越界
    if (pos + len - 1 > S.length) {
        return false;
    }
    for (int i = pos; i < pos + len; i++) {
        Sub.ch[i - pos + 1] = S.ch[i];
    }
    Sub.length = len;
    return true;
}

实现比较操作

// 比较操作。若 S>T，则返回值 >0 ；若S=T，则返回值 =0 ；若 S<T，则返回值 <0
int StrCompare(SString S, SString T) {
    for (int i = 1; i <= S.length && i <= T.length; i++) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
    }
    // 扫描过所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

实现定位操作

// 定位操作。
// 若主串 S 中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；
// 否则函数值为0
int Index(SString S, SString T) {
    int i = 1, n = S.length, m = T.length;
    SString sub;
    while (i <= n - m + 1) {
        SubString(sub, S, i, m);        // 求子串
        if (StrCompare(sub, T) != 0) {  // 比较操作
            ++i;
        } else {
            return i;  // 返回子串在主串中的位置
        }
    }
    return 0;
}