一、链式存储结构
和线性表的存储结构类似,串也可以采用链表方式存储。
由于串结构的特殊性,即结构中的每个数据元素是一个字符。在用链表存储串值时,存在一个“结点大小”的问题。如下图所示。
串值的链表存储示意图
每个结点可以存放一个字符,也可以存放多个字符;当结点大小大于1时,由于串长不一定是结点大小的整数倍,则链表中的最后一个结点不一定全被串值占满,此时不上#或其他非串值字符。
为了实现串的基本操作,当以链表存储串值时,除头指针外还可以增设一个尾指针指示链表中的最后一个结点,并给出当前串的长度。
二、存储密度与效率
所谓存储密度是指串值所占的存储为除以实际分配的存储位的比值。
因此,一个结点中存储的字符个数越少,存储密度越小(如结点大小为1),此时运算处理比较方便,各种操作如同单链表操作。然而,存储空间占用量大,资源消耗多。
与顺序存储结构相比,链式存储结构中,串的连接操作比较方便;但总的来讲,在存储量、操作复杂度等方面都不如前者灵活。