一、什么是串的块链存储
串（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树字符串结构
九、块链存储的本质
块链存储本质上是：
“数组 + 链表”的结合
其中：
- 块内部类似数组
- 块之间类似链表
因此：
块内部
具有：
- 顺序访问
- 局部移动
特点。
块之间
具有：
- 动态扩展
- 非连续存储
特点。
十、总结
串的块链存储是一种：
用“多个字符组成一个结点”的链式字符串存储结构。
它的核心思想是：
通过“分块”减少指针数量，并降低插入、删除时的大规模移动代价。
虽然块链存储在插入、删除时仍会发生字符移动，但它：
- 不需要连续整体搬移
- 更适合动态扩展
- 更适合长串管理
因此在许多实际系统中具有重要意义。