串的链式存储

一、链式存储结构

和线性表的存储结构类似,串也可以采用链表方式存储。

由于串结构的特殊性,即结构中的每个数据元素是一个字符。在用链表存储串值时,存在一个“结点大小”的问题。如下图所示。

串值的链表存储示意图

串值的链表存储示意图

每个结点可以存放一个字符,也可以存放多个字符;当结点大小大于1时,由于串长不一定是结点大小的整数倍,则链表中的最后一个结点不一定全被串值占满,此时不上#或其他非串值字符。

为了实现串的基本操作,当以链表存储串值时,除头指针外还可以增设一个尾指针指示链表中的最后一个结点,并给出当前串的长度。

二、存储密度与效率

所谓存储密度是指串值所占的存储为除以实际分配的存储位的比值。

因此,一个结点中存储的字符个数越少,存储密度越小(如结点大小为1),此时运算处理比较方便,各种操作如同单链表操作。然而,存储空间占用量大,资源消耗多。

与顺序存储结构相比,链式存储结构中,串的连接操作比较方便;但总的来讲,在存储量、操作复杂度等方面都不如前者灵活。

用户头像
登录后发表评论