4.2.2　串的链式存储结构——链串

串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据域上。串的链式存储有单字符结点链和块链两种。

1.单字符结点链

单字符结点链就是每个结点的数据域只包括一个字符，其结构如图4－1所示。

图4－1 单字符结点链

单字符结点链的结构体定义为：

在上面的结构体定义中，每个字符域str所占的存储空间为一个字节，而每个指针域next所占的存储空间为两个或三个字节。当然，这要根据机器的不同而有所区别。因此，我们从中可以看出，单字符结点链的空间利用效率非常低。

2.块链

块链就是每个结点的数据域包括若干个字符的一种存储结构，如图4－2所示。

图4－2 块链

如果用C语言定义，则其结构体定义为：

其中，Number为每个结点数据域的字符个数。当Number数值比较大时，块链的空间利用效率比单字符结点链的空间利用效率显然要高很多。但每个结点数据域的字符个数很大时，其空间利用效率将和串的顺序存储结构的空间利用效率接近。