串是什么，串存储结构及其实现（无师自通）

简介

无论学习哪种编程语言，操作最多的总是字符串。数据结构中，根据串中存储字符的数量及特点，对一些特殊的串进行了命名，比如说：
    空串：存储 0 个字符的串，例如 S = ""（双引号紧挨着）；
    空格串：只包含空格字符的串，例如 S = "     "（双引号包含 5 个空格）；
    子串和主串：假设有两个串 a 和 b，如果 a 中可以找到几个连续字符组成的串与 b 完全相同，则称 a 是 b 的主串，b 是 a 的子串。例如，若 a = "shujujiegou"，b = "shuju"，由于 a  中也包含 "shuju"，因此串 a 和串 b 是主串和子串的关系；
需要注意的是，空格串和空串不同，空格串中含有字符，只是都是空格而已。另外，只有串 b 整体出现在串 a 中，才能说 b 是 a 的子串，比如 "shujiejugou" 和 "shuju" 就不是主串和子串的关系。
另外，对于具有主串和子串关系的两个串，通常会让你用算法找到子串在主串的位置。子串在主串中的位置，指的是子串首个字符在主串中的位置。
例如，串 a = "shujujiegou"，串 b = "jiegou"，通过观察，可以判断 a 和 b 是主串和子串的关系，同时子串 b 位于主串 a 中第 6 的位置，因为在串 a 中，串 b 首字符 'j' 的位置是 6

实现方式

存储一个字符串，数据结构包含以下 3 种具体存储结构：

定长顺序存储
堆分配存储
块链存储

串的定长顺序存储结构（C语言）详解版

我们知道，顺序存储结构（顺序表）的底层实现用的是数组，根据创建方式的不同，数组又可分为静态数组和动态数组，因此顺序存储结构的具体实现其实有两种方式。

通常所说的数组都指的是静态数组，如 str[10]，静态数组的长度是固定的。与静态数组相对应的，还有动态数组，它使用 malloc 和 free 函数动态申请和释放空间，因此动态数组的长度是可变的。
串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。

使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。

例如，采用定长顺序存储结构存储 “data.biancheng.net”，通过目测得知此字符串长度为 18（不包含结束符 ‘\0’），因此我们申请的数组空间长度至少为 18，用 C 语言表示为：

char str[18] = "data.biancheng.net";

下面这段 C 语言代码给大家完美地展示了使用定长顺序存储结构存储字符串：

    #include<stdio.h>
    int main()
    {
        char str[20]="data.biancheng.net";
        printf("%s\n",str);
        return 0;
    }

根据实际情况，实现代码可包含一些函数，用于实现某些具体功能，如求字符串的长度等，由于这些知识都是学习编程语言的基础内容，因此不再过多赘述。

串的堆分配存储结构（C语言详解版）

堆区的内存空间需要程序员手动使用 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 的指向，也就是说，之前动态申请的存储空间虽然申请了，结果还没用呢就丢了

串的块链存储结构（C语言）详解

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

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

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

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

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

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

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

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

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

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define linkNum 3   

typedef struct Link {
    char a[linkNum]; 
    struct Link * next; //代表指针域，指向直接后继元素
}link; // nk为节点名，每个节点都是一个 link 结构体

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


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

    int length = strlen(str);   //strlen用来计算字符串的长度，不是类型占内存的大小
    int num = length / linkNum;   //（字符串长度/数组储存个数）=  需要的节点个数
    if (length % linkNum) {         //要知道，不论是判断语句还是循环语句（）内只要是非零，就代表{}内代码要执行

        num++;  //为了避免差一个节点，这里做出判断，要是余数不为0，就增加一个节点数，之所以如此是由运算符/造成的
    }

    //创建首元节点
    head = (link *) malloc(sizeof(link));
    head->next = NULL;
    link *temp = head;  //创建头指针指向首元节点head

    //初始化链表


    for (int i = 0; i < num; i++) {     //依据节点个数遍历

        //单个节点插入数据
        int k = 0;
        for (; k < linkNum; k++) {     //依据数组能纯属数据个数遍历

            if (i * linkNum + k < length) {

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

            } else {

                temp->a[k] = '#';

            }

        }

        //新建节点
        if (i * linkNum + k < length) {

            link *newlink = (link *) malloc(sizeof(link));
            newlink->next = NULL;
            temp->next = newlink;
            temp = newlink;     //你也可以写成 temp = temp->next;
        }

        return head;

    }

}
    //输出链表
    void displayLink(link * head) {
        link *temp = head;
            }
            temp = temp->next;
        }
    }
int main()
{
    link * head = NULL;
    head = initLink(head, "data.biancheng.net");
    displayLink(head);
    return 0;
}

BF算法（串模式匹配算法）C语言详解

原理：

其实就是暴力法，思路没什么新鲜的，直接看代码分析就行


    #include <stdio.h>
    #include <string.h>
    //串普通模式匹配算法的实现函数，其中 B是伪主串，A是伪子串
    int mate(char * B,char *A){
        int i=0,j=0;
        while (i<strlen(B) && j<strlen(A)) {
            if (B[i]==A[j]) {
                i++;
                j++;
            }else{
                i=i-j+1;
                j=0;
            }
        }
        //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
        if (j==strlen(A)) {
            printf("匹配成功\n");
            return 1;
        }
        //运行到此，为i==strlen(B)的情况
         printf("匹配失败\n");
         return -1;
    }
    int main() {
        mate("ababcabcacbab", "abcac");

        return 0;
    }

数据结构（C语言版）

06--串