4.2　串的存储方法

从串的表现形式看,串是字符的紧密排列,是一个有机的整体。在一般的程序设计语言中,通常都定义了字符串类型,并且把字符数组看成长度固定的串。当串作为进行输入/输出操作的常量时,其只存储串值即可。但在多数非数值处理的程序中,串也以变量的形式出现。下面介绍几种串常用的存储结构。

4.2.1　串的顺序存储

串的顺序存储结构就是把串所包含的字符序列依次存储在连续的存储单元中。根据串存储单元的分配方式,可以将顺序存储结构又分为定长顺序存储结构和堆分配存储结构。

1.定长顺序存储结构

在定长顺序存储中,按照预定义的大小,可为每个定义的串变量分配一个固定长度的存储区,在存储区中每个存储单元存储一个字符,可以用定长数组表示。

其中,SString[MAXSTRLEN＋1]是字符数组类型；SString S中的S是数组,其类型为SString[MAXSTRLEN＋1]。

在C语言中,为了表示串长,通常在串值后面加一个不计入串长的结束标识字符“＼0”来表示串值的终结。

2.堆分配存储结构

在顺序串中,如果在操作中出现串值序列的长度超过上界MAXSTRLEN时,约定用截尾法处理。为了解决这个问题,可以动态分配串值的存储空间,即仍用一组地址连续的存储单元存放串值字符序列,但是它们的存储空间是在程序执行过程中动态分配而得的,故将该存储方式称为串的堆分配存储结构。利用C语言的动态存储管理函数malloc（）和free（）,可根据实际需要动态分配或释放字符串所占的空间。

串的堆分配存储表示如下。

4.2.2　串的链式存储

同线性表的链式存储结构,可采用链表存储字符串值。将可利用的空间分成大小相同的若干连续的存储单元,每个结点有两个域,即data域和next域。其中,data域用于存放字符,next域用于存放指向下一个结点（首地址）的指针。结点中存放的字符数可以用“结点大小”表示,结点大小可以为1,也可以为一个常量值。当结点大小大于1时,由于串长不一定是结点大小的整数倍,则链表中的最后一个结点不一定完全占满,此时通常补上“＃”。图4－1所示是结点大小为1和4的两个链串。

图4－1　链串示意图

链串的定义如下。

使用链表之后,指针所占的空间会增加一定的开销。因此,为了减少开销,每个结点中应尽可能多存放字符。通常使用“存储密度”来衡量开销的大小。

在应用程序中,可将串的链式存储结构和串的顺序存储结构结合使用。例如,在正文编辑系统中,整个“正文”可以看成是一个串,每一行是一个子串,构成一个结点,即同一行的串用定长结构（80个字符）,而行与行之间用指针相链。