数据结构--串

数据结构基础（10)

串的定义

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

例如：

• S = “HelloWorld!”
• T = ‘iPhone 11 Pro Max?’

注意：

• 有的地方用双引号 (如 Java、C)

• 有的地方用单引号 (如 Python)

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

  Eg: ‘iPhone’，‘Pro M’ 是串 T 的子串

• 主串：包含子串的串。

  Eg: T 是子串 ‘iPhone’ 的主串

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

  Eg: ‘1’ 在 T 中的位置是 8 (第一次出现)

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

  Eg: ‘11 Pro’ 在 T 中的位置为 8

• 空串 v.S 空格串:

• M=“” M 是空串

N=’ ’ N 是由三个空格字符

• 组成的空格串，每个空格字符占 1B

注意：位序从 1 开始而不是从 0 开始

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

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

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

串的基本操作

假设有串 T="”，S="iPhone 11 Pro Max?”，W=“Pro”

• 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 (&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。

Eg：

执行基本操作 Concat (&T,S,W) 后，T=“iPhone 11 Pro Max?Pro”

执行基本操作 SubString (&T ,S, 4, 6) 后，T=“one 11”

执行基本操作 Index (S, W) 后，返回值为 11

• 串的比较

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

1. 从第一个字符开始往后依次对比，先出现更大字符的串就更大
2. 长串的前缀与短串相同时，长串更大
3. 只有两个串完全相同时，才相等

• 字符集编码：

任何数据存到计算机中一定是二进制数。需要确定一个字符和二进制数的对应规则这就是 “编码”

“字符集”：

• 英文字符 ——ASCII 字符集
• 中英文 ——Unicode 字符集

基于同一个字符集，可以有多种编码方案，如：UTF-8、UTF-16

串的存储结构

• 顺序存储
• 链式存储
• 基于顺序存储实现基本操作

串的顺序存储：

静态数组实现:

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

动态数组实现（堆分配存储）-- > 用完需要手动free

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

HString S;
S.ch = (char *) malloc(MAXLEN * sizeof(char));
S.length = 0;

串的链式存储

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

注意：不一定是上面的4，还可以是别的，看具体情况自己设定

此方法，存储密度高

串的基本操作–求子串

#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;
}

串的基本操作–比较大小

比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

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(sub, T)!=0)  ++i;
        else return i;  //返回子串在主串中的位置
    }
    return 0;   //S中不存在与T相等的子串
}

朴素模式匹配

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

子串：是主串的一部分，一定存在

模式串：不一定能在主串中找到

主串长度为n,模式串长度为m

普速模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串

• 若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置
• 若 j > T.length ,则当前子串匹配成功，返回当前子串第一个字符的位置 – i - T.length

代码实现：

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;
    else
        return 0;
}

设主串长度为n,模式串的长度为m,则最坏时间复杂度为 O(nm)

KMP算法

1. 根据模式串T，求出next数组
2. 利用next数组进行匹配（主串指针不回溯）

​ 在next数组中有：

if (S[I] != T[j])
j = next[j];
if(j  == 0)
{i++,j++}

3.next数组只和短短的模式串有关，和长长的主串无关

代码实现：

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)

​ 模式匹配过程中最坏的时间复杂度为O(n)

KMP算法和朴素算法的区别：

朴素：匹配失败时，主串指针 i 疯狂回溯

KMP:匹配失败是，主串指针 i 不回溯

next数组

• next数组的作用：当模式串的第 j 个字符匹配失败时，从模式串的第next[j] 的继续往后匹配

• 任何模式串都一样，第1个字符串不匹配时，只能匹配下一个子串，因此，往后余生，next[1]都无脑写0

• 任何模式串都一样，第2个字符串不匹配时，应尝试匹配模式串的第1个字符，因此，往后余生，next[2]都无脑写1

• 在不匹配的位置前边，划一根分界线，模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨国分界线为止

• 此时 j 指向哪儿，next 数组值就是多少

以google 为例

KMP算法的优化：

KMP算法的逻辑是没有变化的，优化的主要是next数组

next数组 – > 优化 – > nextval数组

先求出next数组，再由next数组求出nextval数组

例如 模式串 T = ababaa

代码实现：

nextval[1] = 0;
for (int j = 2; j <= T.length; j++) {
    if (T.ch[next[j]] == T.ch[j])
        nextval[j] = nextval[next[j]];
    else
        nextval[j] = next[j];
}