数据结构与算法教程，数据结构C语言版教程！（第四部分、字符串，数据结构中的串存储结构）二

第四部分、字符串，数据结构中的串存储结构

串存储结构，也就是存储字符串的数据结构。

很明显，字符串之间的逻辑关系也是“一对一”，用线性表的思维不难想出，串存储结构也有顺序存储和链式存储。

提到字符串，常做的操作就是串之间的匹配，因为，本章给初学者介绍 2 种串的模式匹配算法，BF 算法和 KMP 算法。

三、串的堆分配存储结构

串的堆分配存储，其具体实现方式是采用动态数组存储字符串。

通常，编程语言会将程序占有的内存空间分成多个不同的区域，程序包含的数据会被分门别类并存储到对应的区域。拿 C 语言来说，程序会将内存分为 4 个区域，分别为堆区、栈区、数据区和代码区，其中的堆区是本节所关注的。

与其他区域不同，堆区的内存空间需要程序员手动使用 malloc 函数申请，并且在不用后要手动通过 free 函数将其释放。

C 语言中使用 malloc 函数最多的场景是给数组分配空间，这类数组称为动态数组。例如：

char * a = (char*)malloc(5*sizeof(char));

此行代码创建了一个动态数组 a，通过使用 malloc 申请了 5 个 char 类型大小的堆存储空间。

动态数组相比普通数组（静态数组）的优势是长度可变，换句话说，根据需要动态数组可额外申请更多的堆空间（使用 relloc 函数）：

a = (char*)realloc(a, 10*sizeof(char));

通过使用这行代码，之前具有 5 个 char 型存储空间的动态数组，其容量扩大为可存储 10 个 char 型数据。

下面给大家举一个完整的示例，以便对串的堆分配存储有更清楚地认识。该程序可实现将两个串（"data.bian" 和 "cheng.net"）合并为一个串：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main()

{

????????char * a1 = NULL;

????????char * a2 = NULL;

????????a1 = (char*)malloc(10 * sizeof(char));

????????strcpy(a1, "data.bian");//将字符串"data.bian"复制给a1

????????a2 = (char*)malloc(10 * sizeof(char));

????????strcpy(a2, "cheng.net");

????????int lengthA1 = strlen(a1);//a1串的长度

????????int lengthA2 = strlen(a2);//a2串的长度

????????//尝试将合并的串存储在 a1 中，如果 a1 空间不够，则用realloc动态申请

????????if (lengthA1 < lengthA1 + lengthA2) {

????????????????a1 = (char*)realloc(a1, (lengthA1 + lengthA2+1) * sizeof(char));

????????}

????????//合并两个串到 a1 中

????????for (int i = lengthA1; i < lengthA1 + lengthA2; i++) {

????????????????a1[i] = a2[i - lengthA1];

????????}

????????//串的末尾要添加 \0，避免出错

????????a1[lengthA1 + lengthA2] = '\0';

????????printf("%s", a1);

????????//用完动态数组要立即释放

????????free(a1);

????????free(a2);

????????return 0;

}

程序运行结果：

data.biancheng.net

注意，程序中给 a1 和 a2 赋值时，使用了 strcpy 复制函数。这里不能直接用 a1 ="data.biancheng"，程序编译会出错，报错信息为 "没有 malloc 的空间不能 free"。因为 strcpy 函数是将字符串复制到申请的存储空间中，而直接赋值是字符串存储在别的内存空间（本身是一个常量，放在数据区）中，更改了指针 a1 和 a2 的指向，也就是说，之前动态申请的存储空间虽然申请了，结果还没用呢就丢了。

---

四、串的块链存储结构

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

本节实现串的块链存储使用的是无头节点的单链表。当然根据实际需要，你也可以自行决定所用链表的结构（双链表还是单链表，有无头节点）。

我们知道，单链表中的 "单" 强调的仅仅是链表各个节点只能有一个指针，并没有限制数据域中存储数据的具体个数。因此在设计链表节点的结构时，可以令各节点存储多个数据。

例如，图 1 所示是用链表存储字符串?shujujiegou，该链表各个节点中可存储 1 个字符：

图 1 各节点仅存储 1 个数据元素的链表

同样，图 2 设置的链表各节点可存储 4 个字符：

图 2 各节点可存储 4 个数据元素的链表

从图 2 可以看到，使用链表存储字符串，其最后一个节点的数据域不一定会被字符串全部占满，对于这种情况，通常会用 '#' 或其他特殊字符（能与字符串区分开就行）将最后一个节点填满。

初学者可能会问，使用块链结构存储字符串时，怎样确定链表中节点存储数据的个数呢？

链表各节点存储数据个数的多少可参考以下几个因素：

1. 串的长度和存储空间的大小：若串包含数据量很大，且链表申请的存储空间有限，此时应尽可能的让各节点存储更多的数据，提高空间的利用率（每多一个节点，就要多申请一个指针域的空间）；反之，如果串不是特别长，或者存储空间足够，就需要再结合其他因素综合考虑；
2. 程序实现的功能：如果实际场景中需要对存储的串做大量的插入或删除操作，则应尽可能减少各节点存储数据的数量；反之，就需要再结合其他因素。

以上两点仅是目前想到影响节点存储数据个数的因素，在实际场景中，还需结合实现环境综合分析。

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

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define linkNum 3//全局设置链表中节点存储数据的个数

typedef struct Link {

????????char a[linkNum]; //数据域可存放 linkNum 个数据

????????struct Link * next; //代表指针域，指向直接后继元素

}link; // nk为节点名，每个节点都是一个 link 结构体

link * initLink(link * head, char * str);

void displayLink(link * head);

int main()

{

????????link * head = NULL;

????????head = initLink(head, "data.biancheng.net");

????????displayLink(head);

????????return 0;

}

//初始化链表，其中head为头指针，str为存储的字符串

link * initLink(link * head, char * str) {

????????int length = strlen(str);

????????//根据字符串的长度，计算出链表中使用节点的个数

????????int num = length/linkNum;

????????if (length%linkNum) {

????????????????num++;

????????}

????????//创建并初始化首元节点

????????head = (link*)malloc(sizeof(link));

????????head->next = NULL;

????????link *temp = head;

????????//初始化链表

????????for (int i = 0; i<num; i++)

????????{

????????????????int j = 0;

????????????????for (; j<linkNum; j++)

????????????????{

????????????????????????if (i*linkNum + j < length) {

????????????????????????????????temp->a[j] = str[i*linkNum + j];

????????????????????????}

????????????????????????else

????????????????????????????????temp->a[j] = '#';

????????????????}

????????????????if (i*linkNum + 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) {

????????????????for (int i = 0; i < linkNum; i++) {

????????????????????????printf("%c", temp->a[i]);

????????????????}

????????????????temp = temp->next;

????????}

}

程序输出结果为：

data.biancheng.net