• 数据结构-字符串详解

    shuan本章主要内容：字符串的三种存储方式和两种常见算法。

    三种存储结构：

            1、定长顺序存储：实际上就是用普通数组（又称静态数组）存储。例如 C 语言使用普通数据存储字符串的代码为 char a[20] = "data.biancheng.net"。

            2、堆分配存储：用动态数组存储字符串。

            3、块链存储：用链表存储字符串。

    两种常见算法：

            1、BF算法：串模式匹配算法。

            2、KMP算法：快速模式匹配算法。

    一、什么是字符串

            1、字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。

            2、对一些特殊的串进行的命名，比如说：      

                     空串：存储 0 个字符的串，例如 S = ""（双引号紧挨着）；

                     空格串：只包含空格字符的串，例如 S = "     "（双引号包含 5 个空格）；

                    子串和主串：假设有两个串 a 和 b，如果 a 中可以找到几个连续字符组成的串与 b 完全相同，则称 a 是 b 的主串，b 是 a 的子串。 

    注意：空格串和空串不同，空格串中含有字符，只是都是空格而已。另外，只有串 b 整体出现在串 a 中，才能说 b 是 a 的子串，比如 "shujiejugou" 和 "shuju" 就不是主串和子串的关系。

     二、三种存储结构

    1、定长顺序存储结构        

            顺序存储的底层实现是顺序表，也就是数组，根据创建方式不同，可分为静态数组和动态数组：通常所说的数组都指的是静态数组，如 str[10]，静态数组的长度是固定的。与静态数组相对应的，还有动态数组，它使用 malloc 和 free 函数动态申请和释放空间，因此动态数组的长度是可变的。

            串的定长顺序存储结构，可以简单地理解为采用 "固定长度的顺序存储结构" 来存储字符串，因此限定了其底层实现只能使用静态数组。

            使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。
            例如，采用定长顺序存储结构存储 "data.biancheng.net"，通过目测得知此字符串长度为 18，因此我们申请的数组空间长度至少为 19（最后一位存储字符串的结束标志 '\0'），用 C 语言表示为：

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

    完整静态存储代码：

    1. #include
    2. int main()
    3. {
    4.     char str[19]="data.biancheng.net";
    5.     printf("%s\n",str);
    6.     return 0;
    7. }

     

    2、堆分配存储结构

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

            通常，编程语言会将程序占有的内存空间分成多个不同的区域，拿C语言来说，程序会将内存分为 4 个区域，分别为堆区、栈区、数据区和代码区，与其他区域不同，堆区的内存空间需要程序员手动使用 malloc 函数申请，并且在不用后要手动通过 free 函数将其释放。

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

    char *str=(char*)malloc(6*sizeof(char));

    此代码创建了一个动态数组str，通过malloc申请了6个char类型大小的堆存储空间。动态数组相比普通数组（静态数组）的优势是长度可变，换句话说，根据需要动态数组可额外申请更多的堆空间（使用 relloc 函数）：

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

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

    代码示例：将“hello”和“world”两个字符串和为一个字符串。

    1. #include
    2. #include 
    3. #include
    4.  
    5. int main()
    6. {
    7.     char*a1=NULL;
    8.     char*a2=NULL;
    9.     a1=(char*)malloc(10*sizeof(char));
    10.     a2=(char*)malloc(10*sizeof(char)); 
    11.     strcpy(a1,"hello ");//将"hello "赋值给a1
    12. 	strcpy(a2,"world");//将"world"赋值给a2 
    13.     //获取字符串的长度 
    14.     int len1=strlen(a1); 
    15.     int len2=strlen(a2);
    16.     //合并两个字符串
    17. 	if(len1//扩大存储空间 
    18. 		a1=(char*)realloc(a1,(len1+len2+1)*sizeof(char));
    19. 	}
    20. 	for(int i=len1;i
    21. 		a1[i]=a2[i-len1];
    22. 	}
    23. 	//串的末尾要添加 \0，避免出错
    24.     a1[len1 + len2] = '\0';
    25.     printf("%s", a1);
    26.     //用完动态数组要立即释放
    27.     free(a1);
    28.     free(a2);
    29.     return 0;
    30. }

    输出结果：

     

     

    3、块链存储结构

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

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

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

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


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


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


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


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

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

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

    代码示例：

    1. #include
    2. #include 
    3. #include
    4. #define linkNum 3//全局设置链表中节点存储数据的个数
    5. typedef struct Link{
    6. 	char a[linkNum]; //数据域可存放 linkNum 个数据
    7.     struct Link * next; //代表指针域，指向直接后继元素
    8. }link; // nk为节点名，每个节点都是一个 link 结构体
    9.  
    10. link*initLink(link*head,char*str);
    11. void displayLink(link*head);
    12.  
    13. int main()
    14. {
    15. 	link * head = NULL;
    16.     head = initLink(head, "data.biancheng.net");
    17.     displayLink(head);
    18. 	return 0;
    19. } 
    20.  
    21. //初始化链表，其中head为头指针，str为存储的字符串
    22. link * initLink(link * head, char * str) {
    23.     int length = strlen(str);
    24.     //根据字符串的长度，计算出链表中使用节点的个数
    25.     int num = length/linkNum;
    26.     if (length%linkNum) {
    27.         num++;
    28.     }
    29.     //创建并初始化首元节点
    30.     head = (link*)malloc(sizeof(link));
    31.     head->next = NULL;
    32.     link *temp = head;
    33.     //初始化链表
    34.     for (int i = 0; i
    35.     {
    36.         int j = 0;
    37.         for (; j
    38.         {
    39.             if (i*linkNum + j < length) {
    40.                 temp->a[j] = str[i*linkNum + j];
    41.             }          
    42.             else
    43.                 temp->a[j] = '#';
    44.         }
    45.         if (i*linkNum + j < length)
    46.         {
    47.             link * newlink = (link*)malloc(sizeof(link));
    48.             newlink->next = NULL;
    49.             temp->next = newlink;
    50.             temp = newlink;
    51.         }
    52.     }
    53.     return head;
    54. }
    55. //输出链表
    56. void displayLink(link * head) {
    57.     link * temp = head;
    58.     while (temp) {
    59.         for (int i = 0; i < linkNum; i++) {
    60.             printf("%c", temp->a[i]);
    61.         }
    62.         temp = temp->next;
    63.     }
    64. }

    输出结果：

     

     

    三、两种常见算法

    1、BF算法

            串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法。

            主串与子串：如果串 A（如 "shujujiegou"）中包含有串 B（如 "ju"），则称串 A 为主串，串 B 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。

    实现串的模式匹配的算法主要有以下两种：

    1. 普通的模式匹配算法；
    2. 快速模式匹配算法；

     BF算法就是其中的一种——普通的模式匹配

    普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

    例如，使用普通模式匹配算法判断串 A（"abcac"）是否为串 B（"ababcabacabab"）子串的判断过程如下：

    （1）首先，将串 A 与串 B 的首字符对齐，然后逐个判断相对的字符是否相等

     （2）由于串 A 与串 B 的第 3 个字符匹配失败，因此需要将串 A 后移一个字符的位置，继续同串 B 匹配

    （3）两串匹配失败，串 A 继续向后移动一个字符的位置，

    （4）两串的模式匹配失败，串 A 继续移动，一直移动至下图的位置才匹配成功： 

    由此，串 A 与串 B 以供经历了 6 次匹配的过程才成功，通过整个模式匹配的过程，证明了串 A 是串 B 的子串（串 B 是串 A 的主串）。

             BF 算法的实现思想是：将用户指定的两个串 A 和串 B，使用串的定长顺序存储结构存储起来，然后循环实现两个串的模式匹配过程，C 语言实现代码如下：

    代码实现：
     

    1. #include
    2. #include
    3. int mate(char *B,char *A){//假设B是伪主串，A是伪子串 
    4. 	int i=0,j=0;
    5. 	while(i<strlen(B)&&j<strlen(A)){
    6. 		if(B[i]==A[j]){
    7. 			i++;
    8. 			j++;
    9. 		}else{
    10. 			i=i-j+1;//串A开始移动，(i-j)是上次匹配的相同字符个数 
    11. 			j=0; 
    12. 		}
    13. 		   //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
    14. 	}
    15. 	if (j==strlen(A)) {//匹配成功 
    16.         return i-strlen(A)+1;//1 
    17.     }
    18.     //运行到此，为i==strlen(B)的情况
    19.     return 0;//匹配失败 
    20. } 
    21. int main() 
    22. {
    23.     int number=mate("ababcabcacbab", "abcac");
    24.     printf("%d",number);
    25.     return 0;
    26. }

            该算法最理想的时间复杂度 O(n)，n 表示串 A 的长度，即第一次匹配就成功。
            BF 算法最坏情况的时间复杂度为 O(n*m)，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 "0000000001"，而串 A 为 "01"，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。 

    2、KMP算法

    快速模式匹配算法，简称 KMP 算法，是在 BF 算法基础上改进得到的算法。KMP 算法不同，它的实现过程接近人为进行模式匹配的过程。例如，对主串 A（"ABCABCE"）和模式串 B（"ABCE"）进行模式匹配，如果人为去判断，仅需匹配两次。

    示例：

    第一次人为匹配：

    第二次人为匹配： 

     

     至此，匹配成功。若使用 BF 算法，则此模式匹配过程需要进行 4 次。

    由此可以看出，每次匹配失败后模式串移动的距离不一定是 1，某些情况下一次可移动多个位置，这就是 KMP 模式匹配算法。

    假设主串 A 为 "ababcabcacbab"，模式串 B 为 "abcac"，则 KMP 算法执行过程为：

    第一次匹配：

    第二次匹配： 

     

    第三次匹配: 

     

    使用 KMP 算法只需匹配 3 次，而同样的问题使用 BF 算法则需匹配 6 次才能完成。

    KMP 算法的完整 C 语言实现代码为： 

    1. #include 
    2. #include 
    3. //调用了普通求 next 的方式，这里并未直接对 next[1] 赋值为 1，但通过函数第一次运行，也可以得出它的值为 1
    4. void Next(char*T,int *next){
    5.     int i=1;
    6.     next[1]=0;
    7.     int j=0;
    8.     while (i<strlen(T)) {
    9.         if (j==0||T[i-1]==T[j-1]) {
    10.             i++;
    11.             j++;
    12.             next[i]=j;
    13.         }else{
    14.             j=next[j];
    15.         }
    16.     }
    17. }
    18. int KMP(char * S,char * T){
    19.     int next[10];
    20.     Next(T,next);//根据模式串T,初始化next数组
    21.     int i=1;
    22.     int j=1;
    23.     while (i<=strlen(S)&&j<=strlen(T)) {
    24.         //j==0:代表模式串的第一个字符就和当前测试的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
    25.         if (j==0 || S[i-1]==T[j-1]) {
    26.             i++;
    27.             j++;
    28.         }
    29.         else{
    30.             j=next[j];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
    31.         }
    32.     }
    33.     if (j>strlen(T)) {//如果条件为真，说明匹配成功
    34.         return i-(int)strlen(T);
    35.     }
    36.     return -1;
    37. }
    38. int main() {
    39.     int i=KMP("ababcabcacbab","abcac");
    40.     printf("%d",i);
    41.     return 0;
    42. }

    输出结果：

     原文链接：

    KMP算法（快速模式匹配算法）C语言详解 (biancheng.net)

  • 相关阅读:
    禁忌搜索算法在求解取送货路径问题中的应用
    numpy函数使用大全python
    字节青训营 浅尝Type Script
    Linux安全之SSL基础
    【Linux信号专题】二、信号是如何产生的
    java中的static关键字几个注意点
    cookie是什么？有什么用？cookie详解，一篇文章彻底搞懂cookie
    IT面试真题详解SQL（领取SQL详解一份）
    如何在windows系统环境下使用tail命令查看日志
    独立站运营和facebook投放怎么做
  • 原文地址：https://blog.csdn.net/qq_51701007/article/details/126282228