阅读:0       作者:解学武

串存储结构,数据结构中的串(无师自通)

对于由多个字符(≥ 0)组成的字符串(例如 "http://data.biancheng.net"),数据结构单独提供了一种存储结构,称为串结构

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

特殊的串

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

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] = "http://data.biancheng.net";

2) 堆分配存储结构

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

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

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

3) 块链存储结构

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

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