串的块链存储表示及其插入、删除操作

一、什么是串的块链存储

串（String）是由零个或多个字符组成的有限序列。

串的存储方式通常有：

• 顺序存储
• 链式存储

其中，块链存储是一种改进的链式存储结构。

二、块链存储的基本思想

普通链表通常：

一个结点存放一个字符

例如：

a → b → c → d

这种方式存在明显问题：

• 指针数量过多
• 空间利用率低
• 访问效率较差

因此提出：

一个结点存放多个字符

即“块链存储”。

例如：

[abc] → [def] → [gh]

其中：

• 每个方块称为“块（Chunk）”
• 一个块中可存放多个字符
• 块之间通过指针连接

三、块链结点结构

设每块大小为 3，则结点结构可表示为：

typedef struct Chunk {

char ch[3];

struct Chunk *next;

} Chunk;

其中：

• ch[3] 用于存放字符
• next 指向下一块

四、块链存储的特点

1. 减少指针数量

普通链表：

a → b → c → d → e

每个字符都需要一个指针。

块链：

[abc] → [de]

多个字符共享一个指针。

因此：

• 空间利用率更高
• 存储效率更高

2. 不要求连续存储空间

顺序串必须占用连续内存。

块链串：

• 各块可分散存储
• 扩展更方便

因此更适合：

• 长字符串
• 动态字符串
• 文件系统
• 外存结构

五、块链串的插入操作

1. 基本思想

插入时：

• 在目标块中腾出位置
• 若块满，则向后续块转移字符
• 必要时增加新块

2. 示例

原串：

[abc] → [def] → [gh]

在 c 后插入 X。

若块长固定为 3，则：

[abc]

变成：

[abcX]

超过容量。

于是需要：

[abc] → [Xde] → [fgh]

3. 插入特点

将移动限制在局部块之间

相比顺序串：

• 不一定移动整个串
• 不需要连续大规模搬移
• 块之间借字符

因此更灵活。

六、块链串的删除操作

1. 基本思想

删除字符后：

• 后续字符前移
• 必要时从后继块借字符

2. 示例

原串：

[abc] → [def] → [gh]

删除 b：

逻辑上会变为：

[acd] → [efg] → [h]

因此：

3. 删除特点

避免连续大规模整体移动

它更多是：

• 分块调整
• 局部移动

七、块链与顺序存储的比较

八、块链存储的进一步思考

教材中通常采用：

固定块长

例如：

[abc] → [def]

每块长度固定为 3。

这样做的原因是：

• 实现简单
• 结构统一
• 便于分析

但实际上：

块长也可以动态变化

例如：

[abce] → [def] → [gh]

这样插入时：

• 甚至无需移动后续元素
• 插入效率更高

这种思想在现代高级数据结构中十分常见，例如：

• Rope
• Gap Buffer
• Piece Table
• B树字符串结构

九、块链存储的本质

块链存储本质上是：

“数组 + 链表”的结合

其中：

• 块内部类似数组
• 块之间类似链表

因此：

块内部

具有：

• 顺序访问
• 局部移动

特点。

块之间

具有：

• 动态扩展
• 非连续存储

特点。

十、总结

串的块链存储是一种：

用“多个字符组成一个结点”的链式字符串存储结构。

它的核心思想是：

通过“分块”减少指针数量，并降低插入、删除时的大规模移动代价。

虽然块链存储在插入、删除时仍会发生字符移动，但它：

• 不需要连续整体搬移
• 更适合动态扩展
• 更适合长串管理

因此在许多实际系统中具有重要意义。