String Structures

String Structures

五月 29, 2021

串

  1. 字符串的定义：由==零个==或==多个==字符组成的==有限序列==（记作：s=“a1 a2 … an”(n≥0)）

    1. 空串（null string）：零个字符（n为串的长度）
    2. 空格串：只含有（多个）空格
    3. 子串、主串：包含子串的串称主串
    4. 串的抽象数据类型：P107

  2. 串的比较：逐位比较

    1. 标准ASCII码：128（7位二进制组成）
    2. 扩展ASCII码：256（8位二进制组成）
    3. Unicode码：216（16位二进制组成 ≈ 6.5w）【前256位跟ASCII码相同】

  3. 串的存储结构

    1. 顺序存储结构：用一组==地址连续==的存储单元来存储串中的字符序列【定长数组】
      1. a[0]：数组第一位保存预定义最大串长度
      2. “\0”：串值终结（遍历长度：for(i ; a[i] != '\0' ; i++)）
      3. 弊端：超出数组长度Maxsize，发生上溢出，截尾
      4. 动态分配：由自由存储区“==堆==”调用C语言的malloc()、free()，进行动态分配管理
    2. 链式存储结构：一个结点对应一个字符或多个字符，“#”补全（方便连接串，存储性能不如顺序结构）

  4. 串的模式匹配算法（子串的定位）

    1. 朴素的模式匹配算法（主串（大循环）、子串（小循环）的循环遍历，比较指针回溯）【等概率原则：O(n+m)】

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      /*
      T[0]、S[0]：存放串长度
      1. 定义索引主串的指针i、索引子串的指针j=1（从头开始）
      2. 判断：当主串指针小于等于主串长度 且 子串指针小于等于子串长度
          1. 判断：数据相等
              a. 主串指针、子串指针++
          2. 数据不等
              a.主串指针退回上次匹配首位的下一位
              b.子串指针重置 1
      3. 判断：子串指针超出自串长度
              遍历完成，返回位置
      4. 无结果，返回0
      */
      int Index(String S,String T,int pos)
      {
          int i=pos;
          int j=1;	//1
          while(i<=S[0] && j<=T[0])	//2
          {
              if(S[i]==T[j])	//2.1
              {
                  i++;
                  j++;
              }
              else	//2.2
              {
                  i = i-j+2;	//2.a
                  j=1;	//2.b
              }
          }
          if(j>T[0])
          {
              return i-T[0];	//3
          }else{
              return 0;
          }
      }

    2. KMP模式匹配算法（时间复杂度O(n+m)）

      1. 最长模式串：前缀模式串 == 后缀模式串（小于整个模式串长度）

      2. 增加next数组进行==相似度查询==：j值 的大小取决于当前字符之前的串前后缀的相似度

      3. next[j] 数组：存放最长重合前后缀长度+1

      4. 【第二位往后（k!=0）】如果Pj ≠ Pnext[j]，那么next[j+1]可能的次大值为next[ next[ j ] ]+1，以此类推知道值为1

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        /*
        生成T串的next[]数组：
            1. 定义子串索引变量i=1 (T(0)存放串长度)，最长前缀表索引变量k=0
            2. next[1]数组首位为0
            3. 判断：当前位置i小于串长度
                1. 判断：前缀k==0 或 前缀最后一位数据==最长前缀k数据
                    a.++i,++k
                    b.记录第i位最长前缀k
                2. 数据不一样，回溯前一位匹配的k值（当前最长前缀不匹配，回朔至次长前缀接着比较）
        */
        void get_next(String T,int *next)
        {
            int i=1,k=0;	//1
            next[1]=0;	//2
            while(i<T[0])	//3
            {
                if(k==0 || T[i]=T[k])	//3.1
                {
                    ++i;
                    ++k;	//3.1.a
                    next[i]=k;	//3.1.b
                }
                else{
                    k=next[k];	//3.2
                }
            }
        }

      5. 经验总结：前后缀模式串n个字符相等，k值为n+1

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        /*
        1. 定义索引主串的i，索引子串j
        2. 生成预加载next数组长度；
        3. 调用函数get_next计算传入子串T的next数组
        4.判断子主串小于等于串长
            1. 判断j==0 或 主串值==子串值
                a.索引指针++
            2. 子串索引j按照next数组退回到合适位置
        4. 判断子串索引结束
            a.遍历完成，返回位置
        5. 不匹配，返回0
        */
        int Index_KMP(String S,String T,int pos)
        {
            int i=pos;
            int j=1;
            int next[MAXSIZE];	//2
            get_next(T,next);	//3
            while(i<=S[0] && j<=T[0])	//4
            {
                if(j==0 || S[i]==T[j])	//4.1
                {
                    i++;
                    j++;
                }
                else
                {
                    j=next[j];		//4.2
                }
            }
            if(j>T[0])	//5
            {
                return i-T[0];
            }
            else{
                return 0;	//6
            }
        }

    3. 改进版KMP模式匹配算法（改良next[]数组）

      1. 计算next数组值时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval
      2. 如果不等，则该a位的nextval值就是它自己的next的值
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      /*
      1.定义子串索引变量i=1 (T(0)存放串长度)，最长前缀表索引变量k=0
      2.nextval[1]数组首位为0
      3.判断：子串当前索引i小于子串长度
          1.判断：前缀长度k==0 或 当前i位置数据==最长前缀k数据
              a.i++,k++
              b.判断：当前i位置数据 ！= 最长前缀k位置的数据
                      当前k为此i位置的最长前缀，赋值给nextval数组
              c.当前位置数据 == 前缀k位置数据
                      k位置的nextval值赋值给当前i位置nextval值
          2.数据不相等，或k != 0，（k值回朔）次长前缀值nextval[k]赋值给当前索引k
      */
      void get_nextval(String T,int *nextval)
      {
          int i=1;
          int k=0;	//1
          nextval[1]=0;	//2
          while(i<T[0])
          {
              if(k==0 || T[i]==T[k])
              {
                  ++i;
                  ++k;	//3.1.a
                  if(T[i]!=T[k])
                  {
                      nextval[i]=k;	//3.1.b
                  }
                  else{
                      nextval[i]=nextval[k];	//3.1.c
                  }
              }
              else{
                  k=nextval[k];	//3.2
              }
          }
      }
  1. 1. 串
    1. 1.0.1. 字符串的定义：由==零个==或==多个==字符组成的==有限序列==（记作：s=“a1 a2 … an”(n≥0)）
    2. 1.0.2. 串的比较：逐位比较
    3. 1.0.3. 串的存储结构
    4. 1.0.4. 串的模式匹配算法（子串的定位）