408

数据结构与算法-04-串

串的定义

  • 串 即 字符串（String）有零个或多个字符组成的有限序列
    • 记作 $S=‘a_1a_2a_3…a_n’$ (n>=0)
      • S 是串名
      • n=0 时的串 称为空串
  • 子串：串 中 任意个 连续字符 组成的子序列
  • 主串：包含子串的串
  • 字符在主串中的位置：字符在串中的序号 从1开始
    • 注意空格也是字符
  • 子串在主串中的位置：子串第一个字符在主串中的位置
  • 空串 不等于 字符串
  • 串 是一种特殊的线性表
    • 串的数据对象 限定为 字符集
  • 串的基本操作
    • 如增删改查
      • 通常 以 子串 作为操作对象

基本操作

  • 赋值操作
    • StrAssign(&T,chars)
      • 把 串 T 赋值为 chars
  • 复制操作
    • StrCopy(&T,S)
  • 判空操作
    • StrEmpty(S)
  • 求串长
    • StrLength(S)
      • 返回 S 的元素个数
  • 清空操作
    • ClearString(&S)
      • 将S清为空串
  • 销毁操作
    • DestoryString(&S)
      • 销毁串 回收 存储空间
  • 串联接
    • Concat(&T,s1,s2)
      • 需要额外的存储空间！？
  • 求子串
    • SubString(&Sub,S,pos,len)
    • 求第 pos 个字符起长度为 len 的子串
  • 定位操作
    • Index(S,T)
    • 寻找子串 在主串中的位置
  • 比较操作
    • StrCompare(S,T)
    • 比较字符串大小
  • 字符集
    • 英文字符– ASCII字符集
    • 中英文– Unicode字符集

存储结构

顺序存储

  • 几种实现方式

    1. 在数组的 末尾，最后一个位置 用来存放length
    2. char[0] 用来存放length
      • 好处是 字符的位序和 数组下标一致
    3. 没有length变量
      • 用 ‘\0’ 表示结尾
    4. 舍弃 char[0] 并在末尾最后一位 存放 length

  • 静态数组实现

    • 定长顺序存储
1
2
3
4
5

#define MAXLEN 255
typedef{
    char ch[MAXLEN];
    int length;
}SString;
  • 动态数组实现
    • 堆分配存储
      • 使用后 需要 手动释放 free
1
2
3
4
5
6

typedef struct{
    char *ch;
    int length;
}HString;
S.ch = (char *)malloc(sizeof(char));
S.length = 0;

链式存储 

1
2
3
4
5
6
7
8
9

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

typedef struct StringNode{
    char ch[4];  // 每个结点 存放多个字符  用于处理存储密度低的缺点
    struct StringNode *next;
}StringNode, *String;

基于顺序存储的基本操作

采用 方案4

 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

#define MAXLEN 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的子串依次与模式串进行比较，直到找到一个完全匹配的子串或所有的子串都不匹配为止
  • 最多对比 n-m+1 个子串

与 Index 方法一致：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int Index(SString S, SString T){
    int i=1, n=StrLength(S), m=StrLength(T);
    SString sub;       // 用于暂存子串
    while(i<=n-m+1){   // 最多对比n-m+1个子串
        SubString(sub,S,i,m); // 取出从i开始 m 长度的子串
        if(StrCompare(sub,T)!=0) ++i; // 子串和模式串对比，不匹配则下一个
        else return i;
    }
    return 0;
}

不使用基本操作，直接通过数组下标操作实现：

 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)
    • 最坏情况下，
      • 每个子串要对比m个字符，共 n-m+1 个子串
      • 字符串匹配时 通常 n»m
      • 复杂度 O((n-m+1)m) = O(nm)

KMP算法

  • 朴素模式匹配算法

    • 当 出现不匹配的字符时
      • 不匹配字符之前的字符一定是和模式串一致的
    • 优化后 主串指针 不往回走

  • 算法思路

    • 根据模式串 T , 求出 next 数组
    • 利用 next 数组进行匹配，实现指针不回溯
      • next 数组只和模式串有关
     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;
    }
}

  • 最坏时间复杂度

    • O(m+n)
      • 其中求 next数组 预处理的 时间复杂度 O(m)
      • 模式匹配过程最坏时间复杂度 O(n)

  • next 数组的作用是 当 模式串和主串中的子串的某一个位置不匹配时，给出这个位置对应的 模式串 指针 应该指向的下一个位置

  • 需要学 如何 手动求 next数组，通常在选择题中考察

求 next 数组（手算）

  • next 数组
    • 当模式串的第j个字符 不匹配时，
      • 从模式串的 第 next[j] 个 继续往后匹配
    • 模式串的位序 等于 next数组下标
      • next[0] 为空
  • 任何模式串都一样
    • 第 1 个字符不匹配时 只能匹配 下一个子串
      • 因此 所有的 next[1]=0
    • 第 2 个字符不匹配时 应该尝试匹配模式串这种的第1个字符
      • 因此 所有的 next[2]=1
  • 在不匹配的情况下
    • 在不匹配的位置 i 之前划一条分界线
    • 接下来让模式串 一步一步的 右移
    • 直到分界线之前的都能对上
    • 或者 模式串的完全跨过分界线
    • 此时 的 j 指向 哪，next数组的值就是多少

next数组进一步优化

优化后的 叫做 nextval 数组

  • 也就是 当原来 的不匹配情况下
    • 即子串中元素 和 模式串的第j位对应字符不匹配
      • 则要找到此时 第 j 位对应 的 next [j] 对应的字符
        • 如果 next [j] 对应的字符 和 第 j 位对应字符 一样
          • 那 nextval [j] 等于 nextval[next[j]]
        • 否则 next [j] 对应的字符 和 第 j 位对应字符 不一样
          • nextval [j] 就等于 next [j]
  • 注意 并不是所有的 next 数组都能优化
1
2
3
4
5
6
7
8

nextval[i] = 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]
}
© 2025 - 2026 Penna_a
共 0 次浏览

发布了 25 篇文章 | 共 115505 字

使用 Hugo 构建
主题 Stack 由 Jimmy 设计