串：字符串的存储与基础操作

在线性结构里，串看起来像是一个很熟悉、甚至有点“太常见以至于容易被忽略”的主题。因为无论是 C 里的字符数组，还是 Java、Go、Python 里的字符串对象，我们几乎每天都在用。但越是常用的东西，越容易只停留在“会用”的层面，而忽略它在数据结构里的独立意义。

从数据结构视角看，串并不只是“一段文本”，而是一类非常特殊的线性表：它的每个元素通常都是字符，而很多操作都围绕模式匹配、子串查找、拼接、比较展开。也正因为这个特点，串虽然本质上仍属于线性结构，但它的应用场景、性能关注点和后续延伸内容，都和一般线性表不太一样。

这一篇先把串的基础认知建立起来：它到底是什么、常见存储方式有哪些、基础操作关心什么，以及为什么后面字符串匹配会成为一个单独而重要的方向。

一、什么是串

串通常可以定义为：

由零个或多个字符组成的有限序列。

例如：

  • "hello"
  • "data structure"
  • "abcabc"

这里有两个点需要特别注意。

1. 串是线性结构

字符在串中有明确的先后顺序，因此它本质上仍然是一种线性表。

2. 串的元素通常是字符

这让它和一般线性表区分开来。在线性表里，元素可以是任意类型；而串通常更强调“字符序列”这一语义。

也正因为元素类型更固定，串会发展出很多特别适合文本处理的操作。

二、串和一般线性表有什么区别

从抽象角度看，串当然可以看成元素类型为字符的线性表。但在实际使用中，串通常有更强的语义约束。

例如：

  • 更高频的操作是比较、查找子串、提取子串、拼接；
  • 很多问题不关心单个字符插入删除，而更关心模式匹配；
  • 串常常和编码、文本表示、存储压缩等主题联系在一起。

所以说，串既是线性表的一种特殊情况，又是一类非常重要、足以单独成章的数据结构对象。

三、串中几个常见概念

1. 空串

长度为 0 的串叫空串，通常记作 ""。

2. 串长

串中字符个数就是串长。

3. 子串

串中任意连续的一段字符序列，叫原串的子串。

例如："abcde" 的子串可以是 "abc"、"bcd"、"e" 等。

4. 主串与模式串

在匹配问题里，通常把被搜索的较长串叫主串，把要查找的较短串叫模式串。

这些概念在后面学字符串匹配算法时会反复出现。

四、串的常见存储方式有哪些

虽然从逻辑上看串只是字符序列，但在底层存储上，不同语言和实现方式差别很大。

1. 定长顺序存储

最直观的做法，是用一段固定长度的连续空间来存放字符。

例如在教学场景里，可能会直接定义一个最大长度为 MAXLEN 的字符数组。它的优点是：

  • 存储简单；
  • 访问方便；
  • 下标定位快。

但缺点也明显：

  • 长度固定，不够灵活；
  • 太大可能浪费空间；
  • 太小又可能装不下。
2. 堆分配或动态存储

现实语言里更常见的是动态分配空间：

  • 需要多长就分多长；
  • 或者预留一定容量并支持扩展；
  • 底层依然常常是连续存储，只是更灵活。

这种方式更贴近真实开发，因为它兼顾了方便使用和空间管理。

3. 链式存储

理论上，串也可以用链表存储，把字符分散放在不同节点里。但这种方式在实际通用语言容器里并不常见，因为：

  • 随机访问差；
  • 单个字符开销大；
  • 对很多文本处理场景并不划算。

不过在一些特殊文本结构、块链、rope 等高性能编辑场景里，链式思想仍然有价值。

五、为什么大多数语言里的字符串更像顺序存储

因为字符串最常见的需求通常是：

  • 顺序遍历；
  • 按位置读取；
  • 做比较、切片、匹配；
  • 保证较好的缓存局部性。

这些操作都更适合连续存储结构。所以虽然字符串本质上是抽象类型，但大多数主流实现都会更偏向顺序存储或其变体。

这和前面学顺序表时的结论一致：

当你特别重视按位置访问和顺序扫描时，连续存储通常会更自然。

六、串最常见的基础操作有哪些

1. 赋值与创建

也就是生成一个新的串对象或初始化字符序列。

2. 求长度

获取串中字符个数。

3. 比较

判断两个串是否相等，或者按字典序比较大小。

4. 连接

把两个串拼成一个更长的串。

5. 求子串

从原串中截取一段连续字符。

6. 查找子串

判断某个模式串是否出现在主串中，以及出现在哪个位置。

7. 插入与删除

在某些实现里也支持，不过很多现代语言里的字符串会通过不可变对象或新建结果来间接完成。

这些操作里，最值得重点关注的通常是比较、截取和模式匹配，因为它们在实际文本处理中最常见。

七、串的比较为什么不是简单“看长度”

字符串比较往往采用字典序，也就是从前往后逐字符比较：

  • 如果某一位先分出大小，就以该位为准；
  • 如果前面都相同，再看后续；
  • 如果一个串是另一个串的前缀，通常较短者更小。

这种比较方式在排序、查找、字典结构里都非常常见。

也正因为串比较通常不是 O(1)，在大量字符串参与的系统里，字符串比较成本本身就可能成为一个重要因素。

八、子串查找为什么会成为单独主题

因为它实在太常见了。

例如：

  • 文本编辑器里搜索关键词；
  • 日志系统里查找错误标记；
  • 搜索框做前缀或模式匹配；
  • 协议解析里定位某段标识；
  • 编译器和解释器处理源代码文本。

最朴素的方法当然是逐个位置尝试匹配，但这样效率并不总理想。于是后面会专门引出：

  • 朴素匹配；
  • KMP；
  • BM；
  • Sunday；
  • Rabin-Karp。

所以这一篇可以看成是后面字符串算法部分的基础垫子。

九、串和字符编码有什么关系

这是现实开发里必须知道的一点。

从数据结构定义看，串由字符组成；但在机器里，字符最终要编码成字节。于是就会涉及：

  • ASCII
  • UTF-8
  • UTF-16
  • Unicode

这意味着“字符个数”和“字节个数”不一定相等。

例如：

  • 英文字符常常占 1 个字节；
  • 中文在 UTF-8 下通常占多个字节。

所以在真实工程里处理字符串时，一定要区分：

  • 逻辑字符长度；
  • 底层字节长度；
  • 按字符切分还是按字节切分。

这不是狭义数据结构课本里的重点，但在工程里非常重要。

十、不可变字符串为什么常见

很多现代语言里的字符串对象是不可变的，例如 Java 的 String。这样设计有几个典型好处：

  • 更安全，避免共享状态被意外修改；
  • 更适合缓存和常量池；
  • 在多线程场景里更容易使用。

但代价也很明显：

  • 频繁拼接可能产生很多新对象；
  • 需要借助额外结构，例如 StringBuilder、缓冲区等来优化。

这再次说明：

数据结构不仅关心“逻辑定义”，还和具体实现中的性能取舍紧密相关。

十一、串在真实开发里常见在哪里

其实几乎无处不在：

  • 日志与配置处理；
  • 网络协议和报文解析；
  • URL、路径、文件名处理；
  • 搜索、推荐、NLP 的基础文本输入；
  • 编译器、解释器、正则表达式引擎；
  • 数据清洗与 ETL。

很多时候，看起来是在“处理文本”，本质上其实就是在高频操作字符串。

十二、学习串时最容易踩的坑

1. 把串完全等同于普通数组

串当然可以顺序存储，但它的核心操作和问题模式远比普通数组更偏文本处理。

2. 忽略编码问题

尤其是处理中英文混合文本、截取、长度统计时，按字节和按字符很容易混淆。

3. 频繁拼接却不考虑代价

在不可变字符串实现里，这种写法可能带来明显性能问题。

4. 只会用字符串 API，不理解底层代价

知道某个库函数会用，不代表理解它的时间和空间成本。

总结

串的重要性，不只是因为它常见，而是因为它把“字符序列处理”这类问题单独抽象成了一类高频结构。真正值得先建立起来的，是这些核心认识：

  • 串本质上是字符组成的线性序列，但它的操作语义比一般线性表更偏文本处理；
  • 顺序存储是字符串最常见的实现基础，因为它适合顺序扫描和按位置访问；
  • 串的核心操作包括比较、连接、求子串和模式匹配；
  • 子串查找之所以重要，是因为它广泛存在于真实文本处理与系统实现中；
  • 在工程里处理字符串时，还必须考虑编码、不可变性和拼接代价；
  • 真正学会串，不只是会调库，而是知道不同操作的底层代价和适用场景。

把这一篇理解透之后，后面再去学字符串匹配算法时，你会更容易明白：为什么 KMP 这些算法值得单独花一整篇去讲，因为它们并不是抽象技巧，而是在解决字符串世界里最核心的一类问题。

参考资源：