扫码获取更多资源

●串的块链存储表示

和线性表的链式存储结构相类似，串也可以采用链表方式存储串值。由于串结构的特 殊性，即结构中的每个元素是一个字符，因此用链表存储串值时存在一个“结点大小”的问 题，即每个结点可以存放一个字符，也可以存放多个字符。

●堆分配顺序串的定义

在程序执行过程中，按照串的实际长度，在一个称之为“堆”的自由存储空间中，为其分 配存储区，把串中的字符按照其逻辑次序依次存放在这组地址连续的存储单元里的方式称 为串的堆分配存储表示，采用这种存储结构的串称为堆分配顺序串（Heap Sequential String） o

块链存储结构的定义

在串的链式存储结构中，依据结点大小有两种存储方式。

算法设计

串的存储空间是在程序执行过程中按照串值的实际大小分配的。在进行串操作时不会 发生“截断”现象。因此堆分配顺序串适应诸如插入、连接、替换等操作。

非压缩方式

一个结点只存储一个字符，其优点是操作方便，但存储利用率低，如图4-4所示。

压缩方式

为了提高存储空间利用率，一个结点可以存储多个字符。由于串长不一定是结点大小 的整数倍，因此链表中的最后一个结点不一定全被串值占满，此时补上，\0,或其他的非串值 字符（通常'（T不属于串的字符集，是串的结束标志），如图4-5所示。

为了便于串的操作，当以链表存储串值时，除了头指针外还可以附设一个尾指针，用来 指示链表中的最后一个结点，并给出当前串的有效长度。釆用这种存储结构的串称为块链 存储结构。

块链存储结构的类型定义

由于在一般情况下，对串进行操作时，只需要从头向尾顺序扫描即可，因此对串值不必 建立双向链表。设尾指针的目的是为了便于进行串连接操作，但应该注意连接时需要处理 第一个串尾的无效字符。

块链存储结构的主要特点

串值的块链存储结构对某些串操作，如连接操作等有一定的方便之处，但总的说来不如 前述两种存储结构灵活，它存储量大且操作复杂。串的块链存储压缩结构实质上是一种顺 序与链式相结合的结构，即块内采用顺序存储结构，块间采用链式存储结构。这种存储结构 增加了实现基本操作的复杂性，例如对改变串长的操作，可能涉及结点的增加与删除问题。在一个串的块链存储结构中插入子串的示例：在串"abcdefg"的第三个字符后 插入子串"xyz”

联系我们：