@[TOC]

  在数据结构中，字符串要独自用一种存储构造来存储，称为串存储构造。这里的串指的就是字符串。无论学习哪种编程语言，操作最多的总是字符串。咱们平时应用最多的存储构造无疑是利用定长数组存储。然而这种存储构造须要提前调配空间，当咱们不晓得字符串长度的时候，过大的分配内存无疑是一种节约。因而，正当的抉择字符串的存储形式显得分外重要。上面将顺次介绍三种存储形式。

定长顺序存储

  字符串的定长顺序存储构造，能够了解为采纳 "固定长度的顺序存储构造" 来存储字符串，因而限定了其底层实现只能应用动态数组。
  应用定长顺序存储构造存储字符串时，需联合指标字符串的长度，事后申请足够大的内存空间。
  例如，采纳定长顺序存储构造存储 "feizhufeifei"，通过目测得悉此字符串长度为12（不蕴含结束符 '\0'），因而咱们申请的数组空间长度至多为 12，用 C 语言示意为：

char str[18] = "feizhufeifei";

  上面是具体的C语言实现

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

  这种存储形式根本是初学者都应该把握的。上面介绍第二种存储形式。

动静数组存储

  首先咱们应该明确两个概念：堆和栈。
  堆是由咱们程序员本人治理的，当过程调用malloc等函数分配内存时，新调配的内存就被动态分配到堆上，当利用free等函数开释内存时，被开释的内存从堆中被剔除。 
  栈又称堆栈，是用户存放程序长期创立的变量，也就是咱们函数{}中定义的变量，但不包含static申明的变量，static意味着在数据段中寄存变量。除此之外，在函数被调用时，其参数也会被压入发动调用的过程栈中，并且待到调用完结后，函数的返回值也会被寄存回栈中，因为栈的先进后出特点，所以栈特地不便用来保留、复原调用现场。从这个意义上讲，咱们能够把堆栈看成一个存放，替换长期数据的内存区。
  当咱们调用malloc时，就会在堆上划分一块空间给咱们应用，具体代码如下：

//创立了一个动静数组str，通过应用 malloc 申请了 10个 char 类型大小的堆存储空间。char * str = (char*)malloc(10*sizeof(char));

  动静数组的劣势是长度可变，依据须要动静进行调配。当我不想申请新的变量，然而又想要扩充str的空间怎么办呢？这个时候realloc函数就起作用了。

//通过应用这行代码，之前具备10 个 char 型存储空间的动静数组，其容量扩充为可存储 20 个 char 型数据。str = (char*)realloc(str, 20*sizeof(char));

  上面通过一个合并两个字符串的例子来更好地了解下动态分配过程。

/* * @Description: 字符串的堆动静堆分配内存 * @Version:   V1.0 * @Autor: Carlos * @Date: 2020-05-25  * @LastEditors: Carlos * @LastEditTime: 2020-05-25  */ #include <stdio.h>#include <stdlib.h>#include <string.h>//打印测试语句#define DEBUG 0#if DEBUG#define DBG_PRINTF(fmt, args...)  \do\{\    printf("<<File:%s  Line:%d  Function:%s>> ", __FILE__, __LINE__, __FUNCTION__);\    printf(fmt, ##args);\}while(0)# else# define DBG_PRINTF(fmt, args...)#endifint main(){    char *s1 = NULL;    char *s2 = NULL;    s1 = (char *)malloc(5*sizeof(char *));    strcpy(s1,"test");     DBG_PRINTF("s1:%s\r\n",s1);    s2 = (char *)malloc(7*sizeof(char *));    strcpy(s2,"string");     DBG_PRINTF("s2:%s\r\n",s2);    int length1 = strlen(s1);    int length2 = strlen(s2);    //尝试将合并的串存储在 s1 中，如果 s1 空间不够，则用realloc动静申请    if(length1<length1+length2)        s1 =(char*) realloc(s1,(length1 + length2+1) * sizeof(char));     //合并两个串到 s1 中    for(int i = length1; i < length1 + length2;i++)         s1[i] = s2[i - length1];     //串的开端要增加 \0，防止出错    s1[length1 + length2] = '\0';    printf("s1+s2:%s", s1);    //用完动静数组要立刻开释    free(s1);    free(s2);    return 0;}

块链存储

  块链存储就是利用链表来存储字符串。本文应用的是无头结点的链表构造（即链表的第一个头结点也存储数据）。
咱们晓得，单链表中的 "单" 强调的仅仅是链表各个节点只能有一个指针，并没有限度数据域中存储数据的具体个数。因而在设计链表节点的构造时，能够令各节点存储多个数据。
  例如，咱们要用链表存储feizhu字符串，链表构造如下所示：

  咱们也能够每个链表存储四个字符，那么最初一个节点必定不会占满。这时，咱们能够应用#或者其余符号将其填满。

  怎么确定链表中每个节点存储数据的个数呢？
  链表各节点存储数据个数的多少可参考以下几个因素：
  串的长度和存储空间的大小：若串蕴含数据量很大，且链表申请的存储空间无限，此时应尽可能的让各节点存储更多的数据，进步空间的利用率（每多一个节点，就要多申请一个指针域的空间）；反之，如果串不是特地长，或者存储空间足够，就须要再联合其余因素综合思考；
  程序实现的性能：如果理论场景中须要对存储的串做大量的插入或删除操作，则应尽可能减少各节点存储数据的数量；反之，就须要再联合其余因素。
  上面是具体的代码实现。

/* * @Description: 字符串的块链表存储(无头结点的链表) * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-25  * @LastEditors: Carlos * @LastEditTime: 2020-05-25  */ #include<stdio.h>#include<stdlib.h>#include<string.h>//全局设置链表中节点存储数据的个数#define linkNum 3typedef struct link {    //数据域可寄存 linkNum 个数据    char a[linkNum];     //代表指针域，指向间接后继元素    struct link * next; }Link; /** * @Description: 遍历链表，打印 * @Param: Link * head 构造体头结点指针 * @Return: 无 * @Author: Carlos */void PrintLink(Link * head){     Link * p = head;    while (p)    {    for (int i = 0; (i < linkNum) &&(p->a[i]!='#'); i++)     {        printf("%c", p->a[i]);    }     p = p->next;    }}/** * @Description: 初始化链表 * @Param: Link * head 构造体头结点指针。char * str 要操作的字符串 * @Return: Link *构造体指针 * @Author: Carlos */Link * InitLink(Link * head, char * str){    int length = strlen(str);    //须要的节点个数 向上取整    int nodenum = length/linkNum;    Link *p = head;    int j;     //将数据寄存到每个节点的数组中    for(int i = 0;i<=nodenum;i++)    {               for( j = 0;j < linkNum;j++)          {            if (i*linkNum + j < length)            {                 p->a[j] = str[i*linkNum+j];            }             //应用#填充未满的节点数组空间            else            {                p->a[j] = '#';            }                              }        //链接新旧两个节点        if (i*linkNum + j < length)        {            Link* q = (Link*)malloc(sizeof(Link));            q->next = NULL;            p->next = q;            p = q;        }    }       return head;}int main(){    Link* head = (Link*)malloc(sizeof(Link));    head->next=NULL;    InitLink(head,"blockchain");    PrintLink(head);    return 0;}

  对于链表不明确的能够参考这篇博客史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
  文中代码均已测试，有任何意见或者倡议均可分割我。欢送学习交换！
  如果感觉写的不错，请点个赞再走，谢谢！

如遇到排版错乱的问题，能够通过以下链接拜访我的CSDN。

**CSDN:[CSDN搜寻“嵌入式与Linux那些事”]