作者：解学武

串的块链存储，指的是用链表存储字符串。

前面章节中，我们学习了很多种链表结构，比如单链表、双向链表、循环链表等，每种链表可以带头结点，也可以不带头结点，实际场景中可以根据实际需求选用合适的链表结构。本节讲解块链存储结构选用的是无头结点的单链表。

所谓单链表，指的是链表中的每个结点只包含一个指针，但每个结点的数据域可以存储多个元素。例如，图 1 是用单链表存储字符串 shujujiegou，该链表的各个结点只存储了 1 个字符：
图 2 所示链表中，各个结点存储了 4 个字符：
当链表中各个结点存储多个（≥2）字符时，最后一个结点的数据域不一定会被占满。这种情况下，通常会用 '#' 或其它的特殊字符（能与字符串区分开就行）将数据域填满。

也就是说，使用块链结构存储字符串，链表中的各个结点可以存储多个字符。那么问题就出现了，怎样确定各个结点存储字符的个数呢？

链表的结点存储多少个字符，会直接影响后续操作字符串的效率。例如，每个结点只存储 1 个字符，好处是方便后续做字符串做插入和删除操作（时间复杂度为 O(1) ），但字符串的存储过于分散，存储空间的利用率不高（每多一个节点，就要多申请一个指针域的空间）。

链表中各个结点存储多少个字符，需结合具体情况综合分析，比如：

1. 串的长度和存储空间的大小：如果字符串很长，链表申请的存储空间有限，应尽可能地让各个节点多存储字符，提高空间的利用率；
2. 程序实现的功能：实际场景中，如果需要对存储的字符串做大量的插入或删除操作，应尽可能地减少各个节点存储字符的数量，提高程序的执行效率。

这里给出一个实现串的块链存储的 C 语言程序，以加深初学者对此字符串存储方式的认识：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LINK_NNM 3//链表中各个结点存储字符的个数

typedef struct link {
    char a[LINK_NNM]; //数据域可存放 LinkNum 个字符
    struct link* next; //代表指针域，指向直接后继结点
}Link;

//初始化链表，其中head为头指针，str为存储的字符串
Link* initLink(Link* head, char* str) {
    int i, length = strlen(str);
    Link* temp = NULL;
    //根据字符串的长度，计算出链表中使用节点的个数
    int num = length / LINK_NNM;
    if (length % LINK_NNM) {
        num++;
    }
    //创建并初始化首元节点
    head = (Link*)malloc(sizeof(Link));
    head->next = NULL;
    temp = head;
    //初始化链表
    for (i = 0; i < num; i++)
    {
        int j = 0;
        for (; j < LINK_NNM; j++)
        {
            if (i * LINK_NNM + j < length) {
                temp->a[j] = str[i * LINK_NNM + j];
            }
            else
                temp->a[j] = '#';
        }
        if (i * LINK_NNM + j < length)
        {
            Link* newLink = (Link*)malloc(sizeof(Link));
            newLink->next = NULL;
            temp->next = newLink;
            temp = newLink;
        }
    }
    return head;
}

//输出链表
void displayLink(Link* head) {
    Link* temp = head;
    while (temp) {
        int i;
        for (i = 0; i < LINK_NNM; i++) {
            printf("%c", temp->a[i]);
        }
        temp = temp->next;
    }
}

int main()
{
    Link* head = NULL;
    head = initLink(head, "http://data.biancheng.net");
    displayLink(head);
    return 0;
}

程序输出结果为：

http://data.biancheng.net##

总结

总的来讲，与串的定长顺序存储结构和堆分配存储结构相比，块链存储结构存储字符串的过程要复杂一些，不如前面两种方案灵活。

在块链存储结构中操作字符串，和在链表中操作数据的实现过程类似，本节不再给大家做详细赘述，感兴趣的读者可自行编码实现。