定义字符串及其抽象操作,比较定长顺序存储、堆分配存储和块链存储,明确长度、结束符与字符编码之间的区别。
# 一、串的定义
字符串(String,简称串)是由零个或多个字符组成的有限序列。设字符集为 ,串 可表示为
其中 称为串的长度,记作 。长度为 的串称为空串,记作 。串中的字符有次序,因此一般有 。
若串 可由 中一段连续字符构成,则称 是 的子串, 是 的主串。若子串从 的第一个字符开始,它是 的前缀;若结束于 的最后一个字符,它是 的后缀。约定空串是任意串的子串、前缀和后缀。
串是特殊的线性表:线性表的元素可以是任意数据元素,而串的元素限定为字符。串上的比较、连接、求子串等操作会利用这一字符序列特征。
# 二、串的抽象数据类型
串的逻辑内容由字符序列决定,抽象数据类型不限定其具体存储方式。常用操作如下。
| 操作 | 语义 |
|---|---|
| StrAssign(S, chars) | 将字符序列赋给串 |
| StrLength(S) | 返回串长 |
| StrCompare(S, T) | 按字符次序比较两个串,返回小于、等于或大于 |
| Concat(S, T) | 返回 与 连接所得的新串 |
| SubString(S, pos, len) | 返回从指定位置开始、长度为 的子串 |
| Index(S, T) | 返回模式串 在主串 中首次出现的位置 |
| ClearString(S) | 将串置为空串 |
本文的数学描述采用从 开始的位置编号;代码示例采用 C 数组的从 开始的下标。空串、空字符和空指针不是同一概念:空串的长度为 ;空字符是值为 0 的字符;空指针不指向任何对象。
# 三、串的存储结构
# 1. 定长顺序存储
定长顺序存储以固定容量的数组保存字符,逻辑相邻的字符也在物理上相邻。可额外保存当前长度,避免每次扫描结束符来计算长度。
1 |
|
这里多出的一个单元用于保存 C 字符串结束符 '\0'。若串的抽象长度达到最大容量,写入结束符就需要额外空间;实现时必须把 “最多保存的字符数” 与 “数组总容量” 区分开。定长数组空间固定,操作简单,但容量不足时无法保存更长的串。
# 2. 堆分配顺序存储
堆分配存储按实际需要动态申请连续空间,常保存字符指针、串长和已分配容量。
1 | typedef struct { |
顺序存储支持按下标 访问第 个字符。若要在中间插入或删除字符,通常需要移动后续字符,代价为 ;连接操作可能需要重新分配更大的空间并复制字符。动态扩容可采用倍增策略,使连续追加的均摊代价较低,但单次扩容仍可能复制整个串。
# 3. 块链存储
块链存储把串分成多个定长字符块,再用链表连接各块。它避免一次申请很长的连续空间,插入、删除时也可能只改动少量块;代价是访问指定位置需要沿块链定位,还需维护块内偏移、空块和尾部未用空间。
1 |
|
flowchart LR
A[定长顺序存储<br/>空间固定、定位快] --> B[连续字符数组]
C[堆分配顺序存储<br/>按需扩容] --> D[连续动态空间]
E[块链存储<br/>字符分块] --> F[块1] --> G[块2] --> H[块3]| 存储方式 | 按位置访问 | 中间插入 / 删除 | 主要约束 |
|---|---|---|---|
| 定长顺序存储 | 通常 | 容量固定 | |
| 堆分配顺序存储 | 通常 | 需要扩容和释放资源 | |
| 块链存储 | 通常需定位块 | 可减少字符整体移动 | 结构和块空间管理更复杂 |
# 四、C 字符串与字符编码
C 语言常用以 '\0' 结尾的字符数组表示字符串。以结束符为边界的操作(如 strlen)会逐字节扫描到 '\0';如果数组没有正确终止,读取可能越过有效对象边界。若另存串长,长度字段和实际字符内容必须保持一致。
在 UTF-8 编码下,一个中文字符通常由多个 char 字节组成,因此 strlen 返回的是字节数,不一定是用户所见字符的个数。若按字节下标截取,可能切断一个多字节编码序列。文本系统还可能需要区分 Unicode 码点与用户感知字符(如带组合符的字素簇)。
不能把 “字符数组长度”“C 字符串字节数” 和 “用户看到的字符个数” 当成同一个量。题目若给出字符集或编码,应先明确串长按什么单位计数。
# 五、考场检查清单
- 空串长度为 ,但不等于含一个空字符的串。
- 串是字符受限的线性表,子串必须由连续字符组成。
- 顺序串随机访问为 ;中间插删通常要移动后缀字符。
- C 字符串需要正确的 '\0' 终止;长度字段表示法则需维护长度与内容一致。
- UTF-8 字节数不等于中文字符数,不能默认一个 char 就是一个完整字符。
