【数据结构】第四章：串

本篇笔记课程来源：王道计算机考研 数据结构

一、串的定义

• 串，即字符串（String）是由零个或多个字符组成的有限序列（特殊的线性表），数据元素之间呈线性关系。一般记为 $$S{=}^{\prime }{a}_1{a}_2......a_n^{\prime }(n\ge 0)$$其中，$S$ 是串名，单引号括起来的字符序列是串的值；
  $a_i$ 可以是字母、数字或其他字符；
  串中字符的个数 $n$ 称为串的长度。$n=0$ 时的串称为空串（用 $Ø$ 表示）。
• 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
• 子串：串中任意个连续的字符组成的子序列。
• 主串：包含子串的串。
• 字符在主串中的位置：字符在串中的序号。
• 子串在主串中的位置：子串的第一个字符在主串中的位置。

二、串的存储结构

1. 串的顺序存储

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

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

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

  typedef struct {char *ch;       // 按串长分配存储区，ch指向串的基地址int length;     // 串的长度
  }HString;
  

2. 串的链式存储

• 定义

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

三、串的基本操作

1. 举例

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

2. 实现

#include <cstdio>
#define MAXLEN 10      // 预定义最大串长为10// 0下标舍弃不用，从1开始，因此只能存放MAXLEN-1个字符
typedef struct {char ch[MAXLEN]; // 每个分量存储一个字符int length; // 串的实际长度
} SString;// 初始化
bool InitSString(SString &s) {s.length = 0;return true;
}// 赋值操作
bool StrAssign(SString &s, char *str) {int i, flag = 0;for (i = 0; *(str + i) != '\0'; i++) {if (i >= MAXLEN - 1) {flag = 1;break;}s.ch[i + 1] = str[i];}if (flag) {s.length = 0;return false;}s.length = i;return true;
}// 复制操作
bool StrCopy(SString &T, SString S) {T.length = S.length;for (int i = 1; i <= T.length; i++) {T.ch[i] = S.ch[i];}return true;
}// 判空
bool StrEmpty(SString S) {return S.length;
}// 求串长
int StrLength(SString S) {return S.length;
}// 清空操作
bool ClearString(SString &S) {S.length = 0;return true;
}// 串联接
bool Concat(SString &S, SString s1, SString s2) {if (s1.length + s2.length > MAXLEN - 1)return false;S.length = s1.length + s2.length;int i;for (i = 1; i <= s1.length; i++) {S.ch[i] = s1.ch[i];}for (; i <= S.length; i++) {S.ch[i] = s2.ch[i - s1.length];}return true;
}// 求子串
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;
}// 比较操作
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;
}// 定位操作
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(S, sub) != 0) ++i;else return i;  // 返回子串在主串中的位置}return 0;           // S中不存在与T相等的子串
}// 输出字符串
void ShowStr(SString s) {for (int i = 1; i <= s.length; i++) {printf("%c", s.ch[i]);}printf("\t 字符长度：%d\n", s.length);
}

四、模式匹配

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

1. 朴素模式匹配算法

• 算法思想：

  • 设主串长度为 n，模式串长度为 m，主串指针 i，模式串指针 j
  • 将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。（最多对比 n-m+1 个子串）
  • 若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置

• 时间复杂度 —— 设主串长度为 n，模式串长度为 m，最坏时间复杂度：O(nm)

• 算法实现

  int index(SString S, SString T) {int i = 1, j = 1;while (i <= S.length && j <= T.length) {if (S.ch[i] == T.ch[j]) {++i; ++j;       // 继续比较后继字符} else {i = i - j + 2;j = 1;          // 指针后退重新开始匹配}}if (j > T.length)return i - T.length;elsereturn 0;
  }
  

2. KMP算法

• 步骤：
  1. 根据模式串 T，求出 next 数组（next 数组只和模式串有关，与主串无关）
  2. 利用 next 数组进行匹配（主串指针不回溯）
• 最坏时间复杂度：O(m+n)，其中
  • 求 next 数组时间复杂度 O(m)
  • 模式匹配过程最坏时间复杂度 O(n)

例如：对于模式串 T=‘abaabc’

• 当第6个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=3
• 当第5个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
• 当第4个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
• 当第3个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
• 当第2个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
• 当第1个元素匹配失败时，匹配下一个相邻子串，令 j=0, i++, j++

• 实现基本原理

  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;           // 继续比较后继字符} elsej = next[j];        // 模式串向右移动}if (j > T.length)return i - T.length;    // 匹配成功elsereturn 0;
  }
  

• 求 next 数组
  1. next[1] 都无脑写 0
  2. next[2] 都无脑写 1
  3. 其他 next：在不配的位置前，划一根分界线，模式串一步一步往后退，直到分界线之前能对上，或模式串完全跨过分界线为止。此时 j 指向哪儿，next 数组值就是多少
• next 数组优化为 nextval 数组
  1. 先求 next 数组
  2. nextval[1] 固定为 0
  3. 若 next[j] 所对应的模式串字符等于模式串第 j 个字符（意思是即使移动了指针也会匹配失败） T.ch[next[j]] == T.ch[j]，则 nextval[j] = nextval[next[j]]
  4. 否则不变：nextval[j] = next[j]