串、数组和广义表

串的定义

串（string）（或字符串）是由零个或多个字符组成的有限序列。串中字符的数目n称为串的长度。零个字符的串称为空串（null string），其长度为零。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

称两个串是相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应的位置的字符都相等时才相等。

由一个或多个空格组成的串" "称为空格串（blank string，请注意：此处不是空串），其长度为串中空格字符的个数。

符号 "\(\varnothing\)" 来表示“空串”。这也是空集的符号。

串的类型定义、存储结构及其运算

串的抽象类型定义

串的存储结构

与线性表类似，串也有两种基本存储结构：顺序存储和链式存储。但考虑到存储效率和算法的方便性，串多采用顺序存储结构。

1. 串的顺序存储
2. 串的链式存储

串的模式匹配算法

子串的定位运算通常称为模式匹配或串匹配。

串的模式匹配设有两个字符串 \(S\) 和 \(T\) ，设 \(S\) 为主串，也称正文串；设 \(T\) 为子串，也称为模式。在主串 \(S\) 中查找与模式 \(T\) 相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符在主串 \(S\) 中出现的位置。

1. BF（Brute-Force）算法。（暴力算法）

   /* 字符串序号从1开始 */
   /* i指针回退：i = i - j + 2 */
   int index_BF(char* s1, char* s2)
   {
       int i = 0, j = 0;
   
       for (i = 0; s1[i] != '\0'; i += 1)
       {
           for (j = 0; s2[j] != '\0'; j += 1)
           {
               if (s1[i + j] != s2[j])
               {
                   break;
               }
           }
           if (s2[j] == '\0')
           {
               return i + 1;
           }
       }
       return 0;
   }
   

2. KMP算法

   /* 计算next数组 */
   /*
       next数组的本质是：前缀与后缀相同。
   
       当前前缀与后缀不同，那就试一试前缀的前缀能不能形成新的相同前后缀。
   
       方法是：
       1. 如果当前后缀相同，则长度继续加1。
       2. 如果不同，则缩短当前前缀为前缀的前缀。
   
       当前的next数组存储的是前缀的长度而非跳转位置。即：length = next[length - 1]
   */
   void get_next(char* str, int* next)
   {
       int i = 1;
       int length = 0;
   
       next[0] = length;
       while (str[i] != '\0')
       {
           /* 相同，长度加1 */
           if (str[i] == str[length])
           {
               length += 1;
               next[i] = length;
               i += 1;
               continue;
           }
   
           /* 不匹配且长度为0，则长度依然为0 */
           if (length == 0)
           {
               next[i] = 0;
               i += 1;
               continue;
           }
   
           /* 不同则得到当前前缀的前缀 */
           length = next[length - 1];
       }
       return;
   }
   
   /* KMP算法。找到第一个匹配的位置（从1开始计算） */
   int index_KMP(char* s1, char* s2)
   {
       int i = 0, j = 0;
       int next[SIZE] = { 0 };
   
       get_next(s2, next);
   
       while (s1[i] != '\0')
       {
           if (s1[i] == s2[j])
           {
               i += 1;
               j += 1;
   
               if (s2[j] == '\0')
               {
                   return i - j + 1;
               }
   
               continue;
           }
   
           if (j == 0)
           {
               i += 1;
               continue;
           }
   
           j = next[j - 1];
       }
   
       return 0;
   }
   

算法示例

next数组中存储的是其下一次跳转的位置。即j = next[j]。

next数组的值可以从0开始，也可以从-1开始。本质上都是从前缀数量上得来的

前缀  0 0 1 0 1 2 3
next -1 0 0 1 0 1 2    在前缀数组上右移
next  0 1 1 2 1 2 3    在上一个next上+1

• 计算next函数值

  void get_next(char* str, int* next)
  {
      int i = 1, j = 0;
      next[1] = 0;
  
      while (str[i] != '\0')
      {
          if (j == 0 || str[i] == str[j])
          {
              i += 1;
              j += 1;
              next[i] = j;
          }
          else
          {
              j = next[j];
          }
      }
  
      return;
  }
  

• 计算next函数修正值

  void get_nextval(char* str, int* nextval)
  {
      int i = 1, j = 0;
      nextval[1] = 0;
  
      while (str[i] != '\0')
      {
          if (j == 0 || str[i] == str[j])
          {
              i += 1;
              j += 1;
              if (str[i] != str[j])
              {
                  nextval[i] = j;
              }
              else
              {
                  nextval[i] = nextval[j];
              }
          }
          else
          {
              j = nextval[j];
          }
      }
  
      return;
  }
  

数组

数组的类型定义

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受\(n(n\ge1)\)个线性关系的约束，每个元素在n个线性关系中的序号\(i_{1}, \space i_{2}, \space ..., \space i_{n}\)称为该元素的下标，可以通过下标访问该数据元素。因为数组中每个元素处于\(n(n\ge1)\)个关系中，故称该数组为n维数组。数组可以看成是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。

数组的顺序存储

特殊矩阵的压缩存储

1. 对称矩阵
2. 三角矩阵
3. 对角矩阵
4. 稀疏矩阵

广义表

广义表的定义

顾名思义，广义表是线性表的推广，也称为列表。广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。

广义表的存储结构

1. 头尾链表的存储结构
2. 拓展线性链表的存储结构

案例分析与实现

算法示例

• 病毒感染检测

  void get_nextval(char* str, int* nextval)
  {
      int i = 1, j = 0;
      nextval[1] = 0;
  
      while (str[i] != '\0')
      {
          if (j == 0 || str[i] == str[j])
          {
              i += 1;
              j += 1;
              if (str[i] == str[j])
              {
                  nextval[i] = nextval[j];
              }
              else
              {
                  nextval[i] = j;
              }
          }
          else
          {
              j = nextval[j];
          }
      }
  }
  
  int Index_KMP(char* s1, char* s2, int* next)
  {
      int i = 1, j = 1;
  
      get_nextval(s2, next);
  
      while (s1[i] != '\0' && s2[j] != '\0')
      {
          if (j == 0 || s1[i] == s2[j])
          {
              i += 1;
              j += 1;
          }
          else
          {
              j = next[j];
          }
      }
  
      if (s2[j] == '\0')
      {
          return i - j + 1;
      }
      return 0;
  }
  
  int main()
  {
      /*
          病毒是baa是环形的，所以将其拓展2倍，每次截取原长度进行匹配。
      */
      char s1[] = "*aaabbbba";
      char s2[] = "*baabaa";
      int next[100] = { 0 };
      int index = 0;
      char tmp[100] = { '\0' };
  
      int i = 0, j = 0, size = 3;
  
      for (i = strlen(s2) - size; i >= 1; i -= 1)
      {
          tmp[0] = '*';
          tmp[size + 1] = '\0';
  
          for (j = 1; j <= size; j += 1)
          {
              tmp[j] = s2[i + j - 1];
              printf("%c", tmp[j]);
          }
          printf("\n");
  
          index = Index_KMP(s1, tmp, next);
          printf("%d\n", index);
      }
  
      return 0;
  }