定义字符串及其抽象操作,比较定长顺序存储、堆分配存储和块链存储,明确长度、结束符与字符编码之间的区别。

# 一、串的定义

字符串(String,简称串)是由零个或多个字符组成的有限序列。设字符集为 Σ\Sigma,串 SS 可表示为

S=a1a2⋯an,ai∈Σ,n≥0.S=a_1a_2\cdots a_n,\qquad a_i\in\Sigma,\qquad n\ge0.

其中 nn 称为串的长度,记作 ∣S∣|S|。长度为 00 的串称为空串,记作 ∅\varnothing。串中的字符有次序,因此一般有 ab≠baab\ne ba。

若串 TT 可由 SS 中一段连续字符构成,则称 TT 是 SS 的子串,SS 是 TT 的主串。若子串从 SS 的第一个字符开始,它是 SS 的前缀;若结束于 SS 的最后一个字符,它是 SS 的后缀。约定空串是任意串的子串、前缀和后缀。

串是特殊的线性表:线性表的元素可以是任意数据元素,而串的元素限定为字符。串上的比较、连接、求子串等操作会利用这一字符序列特征。

# 二、串的抽象数据类型

串的逻辑内容由字符序列决定,抽象数据类型不限定其具体存储方式。常用操作如下。

操作语义
StrAssign(S, chars)将字符序列赋给串 SS
StrLength(S)返回串长
StrCompare(S, T)按字符次序比较两个串,返回小于、等于或大于
Concat(S, T)返回 SS 与 TT 连接所得的新串
SubString(S, pos, len)返回从指定位置开始、长度为 lenlen 的子串
Index(S, T)返回模式串 TT 在主串 SS 中首次出现的位置
ClearString(S)将串置为空串

本文的数学描述采用从 11 开始的位置编号;代码示例采用 C 数组的从 00 开始的下标。空串、空字符和空指针不是同一概念:空串的长度为 00;空字符是值为 0 的字符;空指针不指向任何对象。

# 三、串的存储结构

# 1. 定长顺序存储

定长顺序存储以固定容量的数组保存字符,逻辑相邻的字符也在物理上相邻。可额外保存当前长度,避免每次扫描结束符来计算长度。

1
2
3
4
5
6
7
8
#include <stddef.h>

#define MAX_STRING_LENGTH 100

typedef struct {
char data[MAX_STRING_LENGTH + 1];
size_t length;
} FixedString;

这里多出的一个单元用于保存 C 字符串结束符 '\0'。若串的抽象长度达到最大容量,写入结束符就需要额外空间;实现时必须把 “最多保存的字符数” 与 “数组总容量” 区分开。定长数组空间固定,操作简单,但容量不足时无法保存更长的串。

# 2. 堆分配顺序存储

堆分配存储按实际需要动态申请连续空间,常保存字符指针、串长和已分配容量。

1
2
3
4
5
typedef struct {
char *data;
size_t length;
size_t capacity;
} HeapString;

顺序存储支持按下标 O(1)O(1) 访问第 ii 个字符。若要在中间插入或删除字符,通常需要移动后续字符,代价为 O(n)O(n);连接操作可能需要重新分配更大的空间并复制字符。动态扩容可采用倍增策略,使连续追加的均摊代价较低,但单次扩容仍可能复制整个串。

# 3. 块链存储

块链存储把串分成多个定长字符块,再用链表连接各块。它避免一次申请很长的连续空间,插入、删除时也可能只改动少量块;代价是访问指定位置需要沿块链定位,还需维护块内偏移、空块和尾部未用空间。

1
2
3
4
5
6
7
8
9
10
11
#define STRING_BLOCK_SIZE 16

typedef struct StringBlock {
char data[STRING_BLOCK_SIZE];
struct StringBlock *next;
} StringBlock;

typedef struct {
StringBlock *head;
size_t length;
} BlockString;

flowchart LR
    A[定长顺序存储<br/>空间固定、定位快] --> B[连续字符数组]
    C[堆分配顺序存储<br/>按需扩容] --> D[连续动态空间]
    E[块链存储<br/>字符分块] --> F[块1] --> G[块2] --> H[块3]

存储方式按位置访问中间插入 / 删除主要约束
定长顺序存储O(1)O(1)通常 O(n)O(n)容量固定
堆分配顺序存储O(1)O(1)通常 O(n)O(n)需要扩容和释放资源
块链存储通常需定位块可减少字符整体移动结构和块空间管理更复杂

# 四、C 字符串与字符编码

C 语言常用以 '\0' 结尾的字符数组表示字符串。以结束符为边界的操作(如 strlen)会逐字节扫描到 '\0';如果数组没有正确终止,读取可能越过有效对象边界。若另存串长,长度字段和实际字符内容必须保持一致。

在 UTF-8 编码下,一个中文字符通常由多个 char 字节组成,因此 strlen 返回的是字节数,不一定是用户所见字符的个数。若按字节下标截取,可能切断一个多字节编码序列。文本系统还可能需要区分 Unicode 码点与用户感知字符(如带组合符的字素簇)。

不能把 “字符数组长度”“C 字符串字节数” 和 “用户看到的字符个数” 当成同一个量。题目若给出字符集或编码,应先明确串长按什么单位计数。

# 五、考场检查清单

  1. 空串长度为 00,但不等于含一个空字符的串。
  2. 串是字符受限的线性表,子串必须由连续字符组成。
  3. 顺序串随机访问为 O(1)O(1);中间插删通常要移动后缀字符。
  4. C 字符串需要正确的 '\0' 终止;长度字段表示法则需维护长度与内容一致。
  5. UTF-8 字节数不等于中文字符数,不能默认一个 char 就是一个完整字符。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝