第四章 串

Posted on Edited on In Views:

定义和基本操作

  • 串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = ‘a1a2……an‘（n >= 0)。其中，S 是串名，单引号（有的地方用双引号）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n = 0时的串称为空串（用∅表示）

  • 子串：串中任意个连续的字符组成 的子序列。

  • 主串：包含子串的串。

  • 字符在主串中的位置：字符在串中的序号。

  • 子串在主串中的位置：子串的第一个字符在主串中的位置。

  • 空串和空格串：

    • M = ‘’（空串）
    • N = ‘ ‘（三个空格符号组成的空格串，每个空格字符占1B）

  • 串是一种特殊的线性表，数据元素之间呈线性关系。

  • 串的数据对象限定为字符集（如中文字符、英文字符、数字字符和标点符号等）。

  • 串的基本操作，如增删改查等通常以子串为操作对象。

  • 基本操作：

    • StrAssign(&T, chars)：赋值操作。把串T赋值为 chars。
    • StrCopy(&T, S)：复制操作。由串 S 复制得到串 T。
    • StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
    • StrLength(S)：求串长。返回串 S 的元素个数。
    • ClearString(&S)：清空操作。将 S 清为空串。
    • DestroyString(&S)：销毁串。将串 S 销毁（回收存储空间）。
    • Concat(&Y, S1, S2)：串联接。用 T 返回由 S1 和 S2联接而成的新串。
    • SubString(&Sub, S, pos, len)：：求子串。用 sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
    • Index(S, T)：定位操作。若主串中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0。
    • StrCompare(S, T)：比较操作。若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。

  • 字符集：

    • 英文字符——ASCII字符集
    • 中英文——Unicode字符集
    • 基于同一个字符集，可以有多种编码方案。

存储结构

  • 顺序存储

    • 静态数组实现（定长顺序存储）

      1
      2
      3
      4
      5
      #define MAXLEN 255	//预定义最大串长为255
      typedef struct {
          char ch[MAXLEN];	//每个分量存储一个字符
          int length;	//串的实际长度
      } SString;

    • 动态数组实现（堆分配存储）

      • 用完需要手动 free
      1
      2
      3
      4
      5
      6
      7
      typedef struct {
          char *ch;	//按串长分配存储区，ch 指向串的基地址
          int length;	//串的长度
      } HString;
      HString S;
      S.ch = (char *)malloc(MAXLEN * sizeof(char));
      S.length = 0;

  • 四种顺序存储方案：

    • 最后一个位置放 length
    • 第一个位置放 length
    • 没有 length，以 ‘\0’ 表示结尾
    • ch[0] 废弃不用，最后一个位置放 length

  • 串的链式存储

    • 存储密度低：每个字符1B，每个指针4B

      1
      2
      3
      4
      typedef struct StringNode {
          char ch;	//每个结点存1个字符
          struct StringNode *next;
      } StringNode, * String;

    • 存储密度提高

      1
      2
      3
      4
      typedef struct StringNode {
          char ch[4];	//每个结点存多个字符
          struct StringNode * next;
      } StringNode, * String;

  • SubString(&Sub, S, pos, len)：：求子串。用 sub 返回串 S 的第 pos 个字符起长度为 len 的子串。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #define MAXLEN 255	//预定义最大串长为255
    typedef struct {
        char ch[MAXLEN];	//每个分量存储一个字符
        int length;	//串的实际长度
    } SString;

    //求子串
    bool SubString(SString &sub, SString S, int pos, int len) {
        //子串范围越界
        if (pos + len - 1 > S.length)
            return false;
        for (int i = pos; i < pos + len; i++)
            SUb.ch[i - pos + 1] = S.ch[i];
        Sub.length = len;
        return true;
    }

  • StrCompare(S, T)：比较操作。若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。

    1
    2
    3
    4
    5
    6
    7
    8
    int Strcompare(SString S, SString T) {
        for (int i = 1; i <= S.length && i <= T.length; i++) {
            if (S.ch[i] != T.ch[i])
                return S.ch[i] - T.ch[i];
    	}
        //扫描过的所有字符都相同，则长度长的串更大
        return S.length-T.length
    }

  • Index(S, T)：定位操作。若主串中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int Index(SString S, SString T) {
        int i = 1, n = Strlength(S), m = StrLength(T);
        SString sub;	//用于暂存子串
        while(i <= n - m + 1) {
            SubString(sub, S, i, m);
            if(StrCompare(sub, T) != 0)
                ++i;
            else 
                return i;	//返回子串在主串中的位置
    	}
        return 0;	//S 中不存在与 T 相等的子串
    }

朴素模式匹配算法

  • 字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

    • 子串——主串的一部分，一定能找到
    • 模式串——不一定能在主串中找到

  • 朴素模式匹配算法：主串长度为 n，模式串长度为 m。将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int Index(SString S, SString T) {
        int i = 1, j = 1;
        while(i <= S.length && j <= T.length) {
            if(S.ch[i] == T.ch[i]) {
                ++i;
                ++j;
            } else {
                i = i - j +2;
                j = 1;
            }
    	}
        if(j > T.length)
            return i-T.length;
        else
            return 0;
    }

    最坏时间复杂度：O(nm)

KMP算法

KMP算法的实现

  • 朴素模式匹配算法

    • 一旦发现当前这个子串中某个字符不匹配，就只能转而匹配下一个子串（从头开始）
    • 不匹配的字符之前，一定是和模式串一致的

  • KMP算法中主串指针不回溯。

  • 算法实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int Index_KMP(SString S, SString T, int next[]) {
        int i = 1, j = 1;
        while(i <= S.length && j <=T.length) {
            if(j == 0 || S.ch[i] == T.ch[j]) {
                ++i;
                ++j;	//继续比较后继字符
            }
            else
                j = next[j];	//模式串向右移动
        }
        if(j > T.length)
            return i - T.length;	//匹配成功
        else
            return 0;
    }

    KMP算法，最坏时间复杂度 O(m+n)，其中，求 next 数组时间复杂度 O(m)

求 next 数组

  • next 数组的作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配。
  • 任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串。因此，next[1] 都为0。
  • 任何模式串都一样，第二个字符不匹配时，只能匹配下一个子串。因此，next[2] 都为1。
  • 在不匹配的位置前边，划一条分界线。模式串一步一步往右移，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时 j 指向哪儿，next 数组值就是多少。

KMP算法的进一步优化

  • 求 nextval 数组

    1
    2
    3
    4
    5
    6
    7
    nextval[1] = 0;
    for (int j = 2; j <= T; j++) {
        if (T.ch[next[j]] == T.ch[j])
            nextval[j] = nextval[next[j]];
        else
            nextval[j] = next[j];
    }

    用 nextval 数组代替 next 数组进行计算。