计算机上的非数值处理对象，很多是以字符串为单位的：源程序与目标程序、顾客的姓名地址、信息检索系统的关键词、文本编辑的内容，都是字符串。可计算机硬件天生是为数值计算设计的，于是串的存储和操作都得单独想办法。不同应用中串的特点差别很大——长度是否固定、拼接是否频繁、要不要随机访问、是不是流式输入——只有按实际情况选对存储结构，串处理才高效。这一节先把串的基本概念与抽象数据类型定下来，再说字符在计算机里怎么编码，最后讲三种存储表示。
学习目标
- 区分空串、空格串、子串、主串、位置等术语，理解空串与空格串的差别；
- 理解串的抽象数据类型（ADT String）与最小操作子集，能由最小子集组合出其他操作；
- 说明字符、字符集与编码的关系（ASCII、UTF-8、GBK），理解"串长不等于字节数"及其对截断、取子串等操作的影响；
- 比较三种存储表示（定长顺序、堆分配、块链）的分配方式、操作代价与适用场景；
- 实现求长、取子串、定位、拼接等基本操作并分析复杂度；
- 通过文本编辑的例子理解"以串的整体为操作对象"的实际意义。
串的定义与基本术语
串（string，或字符串） 是零个或多个字符组成的有限序列，一般记为
其中 " "，其长度就是空格字符的个数。
空串与空格串
"" 是空串，长度为 0；" " 是空格串，长度至少为 1。判断"串是否为空"用的是空串，不是空格串。
串中任意个连续字符组成的子序列称为该串的子串，包含子串的串称为主串；子串在主串中的位置以子串第一个字符在主串中的位置表示。例如：
| 串 | 长度 | 说明 |
|---|---|---|
"data" | 4 | 是 "datastructure" 的子串，位置 1 |
"structure" | 9 | 是 "datastructure" 的子串，位置 5 |
"datastructure" | 13 | 主串 |
两个串相等，当且仅当它们的长度相等且各个对应位置的字符都相同。串值必须用引号括起来以区别于变量名或数值常量，例如 x = '123' 表示把字符序列 123 赋给串变量 x；引号本身不属于串值。
串的逻辑结构与抽象数据类型
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象被约束为字符集。真正的差别体现在基本操作上：线性表大多以单个元素为操作对象（查找某个元素、求取某个元素、在某个位置插入/删除一个元素），而串通常以串的整体为操作对象（查找子串、求取子串、插入/删除子串、替换子串）。
| 对比维度 | 线性表 | 串 |
|---|---|---|
| 数据对象 | 任意同类元素 | 字符 |
| 典型操作对象 | 单个元素 | 串（子串）的整体 |
| 典型操作 | 按位查找、插入、删除元素 | 子串查找、截取、拼接、替换 |
这一差别决定了串的存储设计重点：不仅要能随机存取字符，更要让"取一段、拼一段、找一段"这类整体操作高效。
串的抽象数据类型可以形式化地定义如下：
ADT String {
数据对象: D = { ai | ai ∈ CharacterSet, i = 1, 2, …, n, n ≥ 0 }
数据关系: R = { <a(i-1), ai> | a(i-1), ai ∈ D, i = 2, …, n }
}常用操作如下表所示（★ 表示最小操作子集）：
| 操作 | 功能 |
|---|---|
★ StrAssign(&T, chars) | 生成一个值等于字符常量 chars 的串 T |
★ StrCompare(S, T) | 字典序比较：S>T 返回正值，相等返回 0，S<T 返回负值 |
★ StrLength(S) | 返回串的长度 |
★ Concat(&T, S1, S2) | 用 T 返回 S1 与 S2 联接而成的新串 |
★ SubString(&Sub, S, pos, len) | 用 Sub 返回 S 中第 pos 个字符起长度为 len 的子串 |
Index(S, T, pos) | 返回 T 在 S 中第 pos 个字符之后首次出现的位置，否则 0 |
Replace(&S, T, V) | 用 V 替换 S 中出现的所有与 T 相等的不重叠子串 |
StrInsert(&S, pos, T) | 在 S 的第 pos 个字符之前插入 T |
StrDelete(&S, pos, len) | 从 S 中删除第 pos 个字符起长度为 len 的子串 |
其余如 StrCopy、StrEmpty、ClearString、DestroyString 等辅助操作不再逐一列出。
StrAssign、StrCompare、StrLength、Concat、SubString 五种操作构成串类型的最小操作子集：它们不可能利用其他串操作来实现；反之，除 ClearString 和 DestroyString 外，其余操作都可以在这个最小操作子集上实现。直觉上这五者各回答一个问题：StrAssign 从零构造一个串，是其他操作的输入来源；StrLength、SubString、Concat、StrCompare 分别回答"多长、截一段、拼一段、比一比"，其余操作（定位、替换、插入、删除）都是这四类动作的编排。
以定位函数 Index 为例，看最小子集如何组合：从 pos 起依次尝试每个可能的起点 i，用 SubString 取出与 T 等长的子串，再用 StrCompare 与 T 比较，相等即返回 i；直到 i 超过
串比较不是长度比较
"ab" < "abc"，因为短串是长串的前缀时短串更小；"abc" < "abd"，因为第一个不同字符 c < d。比较必须逐字符按字典序进行，而不是先比长度。
字符、字符集与编码
字符是组成字符串的基本单位。C/C++ 中 char 通常占 1 字节（8 bits），用 ASCII 码对 128 个符号编码——这 128 个符号构成的集合就是字符集（charset）：数字、大小写字母、标点与控制字符各有一个 0～127 的编号。
字符集回答"系统里有哪些字符"，编码回答"每个字符用怎样的字节序列表示"。ASCII 是两者合一的单字节编码：一个字符恰好一字节。真实世界的字符远多于 128 个，于是出现了多字节编码：
| 编码 | 字节形态 | 特点 |
|---|---|---|
| ASCII | 固定 1 字节 | 覆盖 128 个符号，单字节编码的基准 |
| UTF-8 | 变长 1～4 字节 | 兼容 ASCII；英文 1 字节、中文 3 字节，互联网事实标准 |
| GBK | 变长 1～2 字节 | 中文 Windows 常用；中文 2 字节 |
UTF-8 的字节结构
UTF-8 变长的秘密在于"前导字节"的二进制前缀：一个字符占几个字节，由第一个字节的高位决定，后续字节统一以 10 开头：
| 字符范围 | 字节数 | 编码形态 |
|---|---|---|
| U+0000 – U+007F | 1 | 0xxxxxxx |
| U+0080 – U+07FF | 2 | 110xxxxx 10xxxxxx |
| U+0800 – U+FFFF | 3 | 1110xxxx 10xxxxxx 10xxxxxx |
| U+10000 – U+10FFFF | 4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx |
英文（ASCII 字符）落在第一行，占 1 字节；绝大多数常用汉字在 U+0800 – U+FFFF 区间，UTF-8 下占 3 字节，GBK 下占 2 字节——这就是同一个文档在两种编码下字节数不同的原因。
读取时如何判断一个字符占几个字节？看当前字节的开头：以 0 开头是单字节字符；以 110、1110、11110 开头分别是 2、3、4 字节字符的第一个字节；以 10 开头的字节不能作为字符起点。例如 "中" 的 UTF-8 编码是 E4 B8 AD（3 字节），若程序按字节从第二个字节截断，得到 E4 B8，它不是一个完整字符，显示出来就是乱码或替换符——这正是"半个字符"问题的根源。
乱码的另一个成因是"同一字节序列被不同编码解读"：一段 UTF-8 编码的中文按 GBK 打开时，字节被按错误的边界切开，于是显示成无法理解的内容。
编码直接决定串的存储与长度问题：strlen("中a") 返回 4（3 + 1 字节），而字符数只有 2。取子串、截断、遍历都必须明确"按字符计数还是按字节计数"，否则可能从多字节字符中间切开。
串长不等于字节数
多字节编码下字符数与字节数不相等。C 的 strlen、std::string::size() 都按字节计数；需要按字符处理时必须先解码（如按上面的规则逐字节判定字符边界），不能直接按下标截断。
串的存储表示
串有 3 种机内表示方法：定长顺序存储、堆分配存储、块链存储。它们分别对应不同的取舍。
定长顺序存储
与线性表的顺序存储结构类似，用一组地址连续的存储单元存放串值。先想一个问题：顺序表与顺序串在存储结构设计上有什么不同？顺序表往往预留备用空间，给插入新结点留扩充余地；而串的基本操作以"串的整体"为主，插入删除少，反而必须知道串的实际长度。于是串长成为存储时必须已知的一个参数，常见的表示方案有三种：
| 表示方式 | 做法 | 特点 |
|---|---|---|
| 尾指针 | 用一个指针指示最后一个字符的位置 | 由首尾指针差求长 O(1)，便于串尾操作 |
| 计数器 | 用独立变量或下标 0 的单元记录字符个数（如 PASCAL） | 求长 O(1)，操作方便 |
| 结束标记 | 串值末尾加 '\0' 等不计入长度的特殊字符（C 语言风格） | 长度隐含，需扫描求得 |
三种方案各付出不同代价：计数器求长 O(1)，但要为长度域多留一个单元；结束标记与字符数组、指针天然兼容，strlen 扫描求长 O(n)，换来"不需要显式传长度"；尾指针则最适合频繁在串尾操作的结构。本教程的定长串采用"计数器"方案（0 号单元存长度）：
#define MAXSTRLEN 255 // 用户可在 255 以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1]; // 0 号单元存放串的长度2
这种布局的示意（串 "abcd"）：
下标: 0 1 2 3 4 5 6 ...
[ 4 ] a b c d ? ?在这种结构下实现串操作，基本动作就是"字符序列的复制"。以串联接 Concat 为例，T = S1 + S2 的结果取决于两个串的长度之和与 MAXSTRLEN 的关系，可能出现三种情况：
// 用 T 返回 S1 与 S2 联接而成的新串；未截断返回 true，截断返回 false
bool concat(SString& T, const SString& S1, const SString& S2) {
bool uncut;
if (S1[0] + S2[0] <= MAXSTRLEN) { // 情况 1：未截断
for (int i = 1; i <= S1[0]; ++i) T[i] = S1[i];
for (int i = 1; i <= S2[0]; ++i) T[S1[0] + i] = S2[i];
T[0] = S1[0] + S2[0];
uncut = true;
} else if (S1[0] < MAXSTRLEN) { // 情况 2：S2 被截断
for (int i = 1; i <= S1[0]; ++i) T[i] = S1[i];
for (int i = 1; i <= MAXSTRLEN - S1[0]; ++i) T[S1[0] + i] = S2[i];
T[0] = MAXSTRLEN;
uncut = false;
} else { // 情况 3：仅取 S1
for (int i = 0; i <= S1[0]; ++i) T[i] = S1[i];
uncut = false;
}
return uncut;
}2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
代码讲解：三个分支与上面的三种情况一一对应。分支 1 先把 S1 的全部字符复制到 T 的前段，再把 S2 接在后面，最后写 T[0] 记录总长度；分支 2 中 S2 只复制前 MAXSTRLEN - S1[0] 个字符，T[0] 记为 MAXSTRLEN，表示缓冲区已满；分支 3 中 T 直接以 S1 为结果，S2 一个字符都没有进入 T。
用一个具体例子看分支 2 和 3 的区别。设 MAXSTRLEN = 4：
S1 = "ab"、S2 = "cdef"（2 + 4 > 4 且 2 < 4），命中情况 2，T 得到"abcd"，"ef"被舍去，返回 false；S1 = "abcd"、S2 = "ef"（S1 已满），命中情况 3，T 就是"abcd"，S2 完全没拼上，返回 false；- 只有长度之和不超限（如
"a" + "bc"）才命中情况 1，返回 true。
取子串 SubString 只是把 S[pos .. pos+len-1] 复制到 Sub，复杂度 O(len)，唯一要留心的是参数合法性检查：1 ≤ pos ≤ StrLength(S) 且 0 ≤ len ≤ StrLength(S) - pos + 1，越界应返回失败。这个操作没有算法上的难点，不再贴代码。
评价：定长顺序存储访问任意字符是 O(1)，缓存友好，实现也简单；代价是最大长度在编译期就固定，超长只能按"截断或失败"的约定处理，拼接、插入都要整段搬移字符。
截断语义要在接口层约定
定长串的 concat、insert 超长时，是"截尾保留前缀"还是"返回失败"，不同实现做法不同。接口文档必须写清，否则调用方会拿到静默错误的数据。
堆分配存储
堆分配存储仍以一组地址连续的存储单元存放串值，但空间是在程序执行过程中按串的实际长度动态分配的。C 语言中由 malloc()、realloc()、free() 管理：
struct HString {
char* ch = nullptr; // 非空串时按串长分配存储区，空串为 nullptr
int length = 0; // 串长度
};2
3
4
赋值、比较、取子串的实现与定长版本思路相同（复制字符序列 / 逐字符比较），差别只在空间按需分配，这里以拼接为例。
Status concat(HString& T, const HString& S1, const HString& S2) { // 拼接
free(T.ch); // 释放旧空间
T.ch = (char*)malloc((S1.length + S2.length) * sizeof(char));
if (!T.ch) return OVERFLOW;
for (int i = 0; i < S1.length; ++i) T.ch[i] = S1.ch[i];
for (int i = 0; i < S2.length; ++i) T.ch[S1.length + i] = S2.ch[i];
T.length = S1.length + S2.length;
return OK;
}2
3
4
5
6
7
8
9
代码讲解：第一行 free(T.ch) 先释放 T 原来的空间——T 可能已经持有旧串，不释放就会泄漏（函数返回后旧空间无人管理）；随后按 S1.length + S2.length 一次分配新空间，两次循环分别复制 S1、S2，最后更新长度。malloc 可能失败，所以要有 OVERFLOW 分支。整体复杂度
此堆非彼堆
这里的"堆"指内存管理中由 malloc/free 管理的动态内存区，与数据结构里的堆（一种树形结构）不是一回事。C 程序的内存布局里，栈由系统自动分配释放（函数参数、局部变量），空间小、连续；堆由开发人员申请和释放，空间大、可能有碎片，不释放时程序结束时由操作系统回收。堆分配串的"堆"就是后者——在运行时按串的实际长度申请内存。
循环逐字符拼接为什么是 O(k²)
若在循环里用 concat 逐字符追加，第 i 次拼接要重新分配并把前 i 个字符全部复制一遍，总代价为 std::string）。
评价：堆分配串既有顺序存储访问方便的特点，又对串长没有任何限制，是串处理程序中最常用的方案；代价是每次拼接、截取都可能涉及内存分配与整体复制，频繁小操作时分配开销明显。
块链存储
与线性表的链式存储类似，串也可以用链表存储。串结构的特殊性在于每个数据元素是字符，于是出现"结点大小"问题：每个结点可以只存 1 个字符，也可以存多个字符。结点大小大于 1 时称为块链：
#define BLOCK_SIZE 4
struct BlockNode { // 块结点
char data[BLOCK_SIZE];
BlockNode* next = nullptr;
};
struct Blstring { // 块链串
BlockNode* head = nullptr; // 头指针
BlockNode* tail = nullptr; // 尾指针：便于在串尾操作
int length = 0; // 当前串长
};2
3
4
5
6
7
8
9
10
串 "abcdefghi" 用结点大小为 4 的块链存储示意（最后一块用不属于串字符集的 # 填充）：
head → | a b c d | → | e f g h | → | i # # # | ⋀结点大小是空间与操作的权衡，可以用存储密度来衡量：
- 结点大小为 1 时，每个字符配一个指针（例如 8 字节指针配 1 字节字符），存储密度低、空间浪费严重，但操作最简单；
- 结点大小大于 1 时存储密度提高，但最后一个结点不一定被占满，需要填充
#之类的非串值字符；块内多字符也使得插入、删除字符时通常要在块间搬移字符，操作更复杂。
块间搬移的具体代价：块长 4 的串 "abcdefgh" 布局为 [abcd][efgh]。若在 'd' 后插入 "XY"，结果 "abcdXYefgh" 的布局变成 [abcd][XYef][gh##]——第二块原内容 "efgh" 必须整体后移，其中 "gh" 还要跨块搬进新块。可见块链的插入、删除不是 O(1)：要么在块内搬移字符，要么在块间搬移，块长越大单次搬移的字符越多，但指针开销越小；块长越小搬移越少，指针开销却越大。
评价：访问第 i 个字符需要沿链接行走
三种存储方式对比
| 维度 | 定长顺序 | 堆分配 | 块链 |
|---|---|---|---|
| 存储分配 | 编译期固定 | 运行时按需 | 按块分配 |
| 最大长度 | 有上限，可能截断 | 无固定上限 | 无固定上限 |
| 随机访问第 i 个字符 | O(1) | O(1) | O(i) |
| 拼接 | O(n)，可能截断 | O(n)，重新分配 | O(块数)，不截断 |
| 插入/删除字符 | O(n)，整段搬移 | O(n)，扩容搬移 | 块内/块间搬移，不截断 |
| 空间开销 | 无指针开销 | 无指针开销 | 指针 + 块内填充 |
| 适用场景 | 长度已知、频繁随机访问 | 通用，拼接/比较为主 | 超长文本、流式批量处理 |
应用举例：文本编辑中的串
文本编辑的实质是修改字符数据的形式或格式，基本操作是串的查找、插入和删除。可以把整个文本看成一个文本串，用换页符、换行符划分为若干页与行——页是文本串的子串，行是页的子串。进入编辑时，程序为文本串建立页表和行表（各子串的存储映像）：页表记录页号与该页起始行号，行表记录每行的行号、起始地址和长度。例如某文本串只占一页，其行表如下：
| 行号 | 起始地址 | 长度 |
|---|---|---|
| 100 | 201 | 8 |
| 101 | 209 | 17 |
| 102 | 226 | 24 |
| 103 | 250 | 17 |
| 104 | 267 | 15 |
在某行内插入或删除若干字符，只需更新该行的长度；若超出行分配的存储空间，则重新分配并修改起始地址。插入或删除整行，则涉及行表的插入/删除；若删除的是页的起始行，还要更新页表。由于访问以页表、行表为索引，删除行或页时只需改表，不必删除涉及的字符本身，从而节省大量时间。
这个例子与三种存储结构是呼应的：正文按行存放，行内字符连续存放（可用堆分配；行内编辑频繁时也可用块链减少大段搬移）；插入删除整行只改行表，代价与行内长度无关；而行内插入删除仍要搬移该行的字符。它同时说明了两点：一是串处理中"以串的整体为操作对象"（行是子串，文本是主串）是常态；二是存储结构与索引结构分离（字符存储 + 行表）可以大幅降低编辑代价。
小结
串是值域限定为字符集的线性表，操作粒度从“单个元素”转为“整体子串”（比较、拼接、定位），存储结构围绕这三类操作设计。字符编码（定长/变长）决定逻辑字符与物理字节的映射关系：定长编码支持O(1)随机偏移，变长编码（如UTF-8）下按字符索引需前缀解码，退化为O(n)。
三种存储的技术取舍：
- 定长顺序（静态数组）：连续内存，存取O(1)，缓存友好；长度硬上限，超长截断或报错。适用长度固定的短串（如定长字段）。
- 堆分配（动态数组）：连续内存，动态扩容；拼接操作触发整体重分配与拷贝，时间复杂度O(n+m)，频繁拼接开销大，工程上通常预分配capacity摊薄成本。通用场景首选。
- 块链（链表+节点内缓冲）：非连续存储，插入/追加仅修改局部指针，顺序扫描效率高；随机访问需沿链表遍历块，时间复杂度O(n / block_size)，指针开销影响缓存命中率。适用超长文本、流式处理、编辑器场景。
选型准则：高频随机访问/比较选连续存储（定长或堆分配）；高频拼接选堆分配（带预扩容）或块链；顺序处理大文本选块链。
下一节将上述存储模型作为底层访问接口，讨论模式匹配问题。重点分析BF、KMP、BM算法在连续存储与链式存储下的实际效率差异，以及变长编码对“字符比较”带来的非预期开销。
练习
- 空串与空格串有什么区别？它们的长度分别是多少？"判断串为空"应该用哪个？
- UTF-8 中一个常用汉字占几个字节？如何判断一个字符占几个字节？为什么说"串长不等于字节数"？
- 顺序表与顺序串在存储结构设计上有什么不同？串长有哪三种表示方案，各有什么特点？
- 循环中逐字符拼接为什么是
- 用最小操作子集（StrLength、SubString、Concat）实现
StrDelete(&S, pos, len)。 - 块链存储中，访问第 i 个字符的复杂度是多少？若每个结点只存 1 个字符，空间开销会怎样变化？"存储密度"怎么描述这个问题？
- 文本编辑中删除一行时，为什么只需改行表而不动字符存储？这体现了串的什么操作特点？
"中"的 UTF-8 编码是E4 B8 AD，若程序按字节截断成前两个字节E4 B8会怎样？为什么？