Question

串的存储结构与线性表相同，分为两种。

5.5.1　串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了，其实这还是需要占用一个空间，何必呢。

图5-5-1

刚才讲的串的顺序存储方式其实是有问题的，因为字符串的操作，比如两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度Max-Size。

说说我当年的一件囧事。手机发短信时，运营商规定每条短信限制70个字。大约八年前，我的手机每当我写了超过70个字后，它就提示“短信过长，请删减后重发。”后来我换了一个手机后再没有这样见鬼的提示了，我很高兴。一次，因为一点小矛盾需要向当时的女友解释一下，我准备发一条短信，一共打了79个字。最后的部分字实际是“……只会说好听的话，像‘我恨你’这种话是不可能说的”。点发送。后来得知对方收到的，只有70个字，短信结尾是“……只会说好听的话，像‘我恨你’”

图5-5-2

有这样截断的吗？我后来知道这个情况后，恨不得把手机砸了。显然，无论是上溢提示报错，还是对多出来的字符串截尾，都不是什么好办法。但字符串操作中，这种情况比比皆是。

于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

5.5.2　串的链式存储结构

对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全，如图5-5-3所示。

图5-5-3

当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。

但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。