串是什么，数据结构中的串（小白必读）

对于由多个字符（≥ 0）组成的字符串（例如 "abcd"），数据结构单独提供了一种存储结构，称为串结构。

字符串中的字符之间具有“一对一”的逻辑关系，所以严格意义上讲，串存储结构也属于线性存储结构。和顺序表、链表、栈、队列这些线性存储结构不同的是，串存储结构专门用来存储字符串。

特殊的串

数据结构中，根据串中存储字符的数量及特点，对一些特殊的串进行了命名。

1) 空串

空串指的是未存储任何字符的串，整个串的长度为 0。

C语言中，空串可以这样表示：

const char * str = "";

双引号表示的字符串内没有任何字符，str 就是一个空串。

2) 空格串

空格串指的是由多个（＞0）空格字符组成的串结构，整个串的长度为包含空格字符的个数。

仍以 C 语言为例：

const char * str = "     ";

str 是一个包含 5 个空格字符的空格串，它的长度为 5。

注意：空格串和空串不同，空串中不含任何字符，而空格串中含有的是空格字符。

3) 子串和主串

假设有以下两个串 A 和 B：

A：shujujiegou B：shuju

在串 A 中可以找到几个连续的字符，它们和串 B 相同。我们可以这样描述它们之间的关系：A 是 B 的主串，B 是 A 的子串。

有些实际场景中，给定主串和子串，让我们设计算法找到子串在主串中的位置。子串在主串中的位置，指的是子串首个字符在主串中的位置。例如，串 A 为 "shujujiegou"，串 B 为 "jiegou"，通过观察可以判断 A、B 是主串和子串的关系，即在主串 A 中可以找到 B，B 的第一个字符 'j' 是串 A 中的第 6 个字符，因此子串 B 在主串 A 中的位置就是 6。

本章，我们会学习两种模式匹配算法专门解决此类问题。

串存储结构的具体实现

串存储结构的具体实现方式有 3 种，分别是：

1) 定长顺序存储结构

和顺序存储结构类似，将字符串中的所有字符集中存放在一整块存储空间中，相邻的两个字符之间紧挨着，没有任何空隙。

在 C 语言中，定长顺序存储通常用数组来实现，例如：

char str[30] = "abcd";

2) 堆分配存储结构

和定长顺序存储结构一样，堆分配存储结构也是将所有字符集中存放在一整块内存空间中，不同之处在于，堆分配存储方式使用堆空间来存储字符串。所谓堆空间，即程序执行过程中动态申请的内存空间。

在 C 语言中，可以调用 malloc() 函数动态申请堆内存，动态申请的堆空间必须调用 free() 函数手动释放。

和定长顺序存储结构相比，堆分配存储结构可以动态调整堆空间的大小，使用起来更加灵活。

3) 块链存储结构

块链存储是一种用链表存储字符串的方案，这里不再做详细介绍。

以上 3 种存储结构会在后续文章中作详细介绍。