CosmosNing的个人博客

探索·好奇

0%

数据结构复习笔记3-串

发表于 更新于 分类于
本文字数： 7.3k 阅读时长 ≈ 7 分钟
整理一下串的知识

4. 串

字符串的定义、存储和操作

定义

  • 串：是由零个或多个字符组成的有序序列，一般记为 s = ’\(a_1a_2\cdots a_n\)‘
  • 长度：串中字符数目 \(n\) 称为串的长度
  • 空串：零个字符的串称为空串
  • 子串：串中任意个连续的字符组成的子序列称为该串的子串
  • 主串：包含子串的串称为主串
  • 位置：字符在序列中的序号
  • 相等：当且仅当两个串值相等（长度相等，对应位置的元素值相等）

存储与操作

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
// 算法 4.1
// 若 T 为非空串。若主串 S 中第 pos 个字符之后存在与 T 相等的子串
// 则返回第一个这样的子串在 S 中的位置，否则返回 0

/*
算法流程：
1. 若 pos 输入合法( > 0 )，则转入第 2 步；否则返回 0 结束
2. 计算 S 的长度(记作 n )，T 的长度(记作 m )
3. 循环取 S 第 i 个位置起，长度为 T 的长度(即 m)的子串，并与 T 进行比较。
若相等，则返回位置 i ; 否则，继续循环
4. 循环结束后，还未找到，返回 0
*/

int Index(String S, String T, int pos)
{
    if(pos > 0)
    {
        n = StrLength(S);	m = StrLength(T);	i = pos;
        
        while(i <= n - m + 1)
        {
            SubString(sub, S, i, m);
            if(StrCompare(sub, T) != 0)	++i;
            else return i;
        }
    }
    
    return 0;
}

定长顺序存储表示

  • 存储
1
2
3
4
5
// 串的定长顺序表示

#define MAXSTRLEN 255                          // 最大长度 255

typedef unsigned char SString[MAXSTRLEN + 1];  // 0 号单元存放串的长度
  • 操作
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
39
40
41
// 算法 4.2 
// 串联接
// 用 T 返回由 S1 和 S2 联接而成的新串。若未截断，则返回 TRUE，否则，FALSE。

/*
算法流程：
判断三种情况，进行三种操作，具体如下：

S1[0] + S2[0] <= MAXSTRLEN：未截断，依次将 S1 和 S2 中的字符拷贝到 T 中，并修改 T 的长度（即令 T[0] = S1[0] + S2[0]）

S1[0] < MAXSTRLEN：截断（ S1 全部保留，S2 前一段保留），依次将 S1 全部和 S2 前一部分中的字符拷贝到 T 中，并修改 T 的长度（即令 T[0] = MAXSTRLEN）

else：截断（仅取 S1 ），依次将 S1 前一部分中的字符拷贝到 T 中，并修改 T 的长度（即令 T[0] = MAXSTRLEN）
*/


Status Concat(SString &T, SString S1, SString S2)
{
    if(S1[0] + S2[0] <= MAXSTRLEN)    // 未截断
    {
        T[1, ..., S1[0]] = S1[1, ..., S1[0]];
        T[S1[0]+1, ..., S1[0]+S2[0]] = S2[1, ..., S2[0]];
        T[0] = S1[0] + S2[0];
        uncut = TRUE;
    }
    if(S1[0] < MAXSTRLEN)            // 截断
    {
        T[1, ..., S1[0]] = S1[1, ..., S1[0]];
        T[S1[0]+1, ..., MAXSTRLEN] = S2[1, ..., MAXSTRLEN - S1[0]];
        T[0] = MAXSTRLEN;
        uncut = FALSE;
    }
    else                             //截断（仅取 S1）
    {
        T[1, ..., MAXSTRLEN] = S1[1, ..., MAXSTRLEN];
        T[0] = MAXSTRLEN;
        uncut = FALSE;
    }
    
    return uncut;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 算法 4.3
// 求子串
// 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
// 其中，1 ≤ pos ≤ StrLength(S) 且 0 ≤ len StrLength(S) - pos + 1

/*
算法流程：
1. pos 和 len 的合法性判断（具体范围见上）：若不满足，则返回错误；否则，第二步
2. 依次拷贝 S 中对应位置元素到 Sub 中，并修改 Sub 的长度（Sub[0] = len;），返回成功
*/

Status SubString(SString &Sub, SString S, int pos, int len)
{
    if(pos < 1 || pos > StrLength(S) || len < 0 || len > S[0] -pos + 1)
        return ERROR;
    
    Sub[1, ..., len] = S[pos, ..., pos + len - 1];
    Sub[0] = len;
    
    return OK;
}

堆分配存储表示

  • 存储
1
2
3
4
5
6
// 串的堆分配存储表示

typedef struct{
    char *ch;        // 若是非空串，则按串长分配存储区，否则 ch 为 NULL；
    int  length;     // 串长度
}HString;
  • 操作
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
// 算法 4.4
// 1 ≤ pos ≤ StrLength(S)。在串 S 的第 pos 个字符之前插入串 T

/*
算法流程：
1. pos 合法性判断（具体范围见上）：若不满足，则返回错误；否则，第二步
2. 若 T 非空，则重新分配空间（长度为两个串长度之和）：若空间申请失败，则溢出，退出；否则，循环腾出插入位置，将 T 插入，并修改结果串的总长度。
*/

Status StrInsert(HString &S, int pos, HString T)
{
    if(pos < 1 || pos > StrLength + 1)// pos 不合法
        return ERROR;
    if(T.length) // T 非空，S 重新分配空间，将 T 插入
    {
        if(!(S.ch = (char *)realloc(S.ch, sizeof(char)*(S.length + T.length))))// 注意写法
            exit(OVERFLOW);
        
        for(i = S.length - 1; i >= pos - 1; --i)// 为插入T而腾出位置
        {
            S.ch[i + T.length] = S.ch[i];
        }
        S.ch[pos-1, ..., pos + T.length - 2] = T[0, ..., T.length - 1];//插入 T
        S.length += T.length;
    }
    
    return OK;
}
  • 以下为基本操作（最小操作子集）
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
// 串的新建赋值
// 生成一个其值等于串常量 chars 的串 T

/*
算法流程：
1. 若 T 的 ch 域非空，则释放原有空间
2. 计算 chars 的长度
3. 若 chars 的长度为为 0，则置 T 的 ch 域为空，length 为 0；
否则，申请新空间（若申请失败，则溢出，退出），依次复制 chars 中的字符到 T 的 ch 域的对应位置，并更新 T 的 length 。
*/

Status StrAssign(HString &T, char* chars)
{
    if(T.ch)	free(T.ch);              // 释放 T 原有的空间（注意别漏掉）
    
    for(i = 0, c = chars; *c; ++i, ++c); // 求 chars 的长度
    
    if(! i)
    {
        T.ch = NULL;
        T.length = 0;
    }
    else
    {
        if(!(T.ch = (char*)malloc(i * sizeof(char))))
            exit(OVERFLOW);
        
        T.ch[0, ..., i - 1] = chars[0, ..., i - 1];
        
        T.length = i;// 别漏掉
    }
    
    return OK;
}
1
2
3
4
5
6
7
// 串的长度
// 返回 S 的元素个数，称为串的长度
 
int StrLength(HString S)
{
    return S.length;
}
1
2
3
4
5
6
7
8
9
10
11
12
// 串的比较( 实现巧妙 )
// 若 S > T ，则返回值 > 0；
// 若 S = T ，则返回值 = 0；
// 若 S < T ，则返回值 < 0；

int StrCompare(HString S, HString T)
{
    for(i = 0; 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 串的清空
// 将 S 清为空串

int ClearString(HString &S)
{
    if(S.ch)
    {
        free(s.ch);
        S.ch = NULL;
    }
    
    S.length = 0;
    
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 串的联接
// 用 T 返回由 S1 和 S2 联接而成的新串

/*
算法流程：
1. 若 T 的 ch 域非空，则释放原有空间
2. 为 T 的 ch 申请空间。若申请失败，溢出，退出；否则，转入第 3 步
3. 依次将 S1 、 S2 中的值复制到 T 的 ch 对应位置，并更新 T.length，返回成功。
*/

int Concat(HString &T, HString S1, HString S2)
{
    if(T.ch)	free(T.ch);
    
    if(!(T.ch = (char*)malloc((S1.length + S2.length) * sizeof(char))))
            exit(OVERFLOW);
    
    T.ch[0, ..., S1.length - 1] = S1[0, ..., S1.length - 1];
    T.length = S1.length + S2.length;
    T[S1.length + 1, ..., T.length - 1] = S2[1, ..., S2.length - 1];
    
    return OK;
    
}
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
// 求串的子串
// 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
// 其中，1 ≤ pos ≤ StrLength(S) 且 0 ≤ len ≤ StrLength(S) - pos + 1

/*
算法流程：
1. pos 和 len 的合法性判断（具体范围见上）：若不满足，则返回错误；否则，第二步
2. 若 Sub 的 ch 域非空，则释放原有空间
3. 若 chars 的长度为为 0，则置 Sub 的 ch 域为空，length 为 0；
否则依次拷贝 S 中对应位置元素到 Sub 中，并修改 Sub 的长度（Sub.length = len;），返回成功
*/

int SubString(HString &Sub, HString S, int pos, int len)
{
    if(pos < 1 || pos > S.length) || len < 0 || len > S.length -pos + 1)
        return ERROR;
    
    if(Sub.ch)	free(Sub.ch);
    if(! len)	
    {
        Sub.ch = NULL;
        Sub.length = 0;
    }
    else
    {
        Sub.ch = (char *)malloc(sizeof(char) * len);
        Sub.ch[0, ..., len - 1] = S.ch[pos - 1, ..., pos + len - 2];
        Sub.length = len;
    }
    
    
    return OK;
}

块链存储表示

  • 存储
1
2
3
4
5
6
7
8
9
10
11
12
13
// 串的块链存储表示

# define CHUNKSIZE 80       // 块的大小

struct Chunk{
    char   ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct{
    Chunk *head, *tail;     // 串的头尾指针（设置尾指针是为了方便联接操作）
    int   curlen;           // 串的当前长度
}LString;
  • 操作（与线性表相关操作类似）

字符串的模式匹配（★）

（下面均以顺序存储结构为例）

原始算法

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
// 算法 4.5
// 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后位置
// 若不存在，则函数值返回 0
// 其中 T 非空， 1 ≤ pos ≤ StrLength(S)
// 时间复杂度 O(mn)，n 为主串长度，m 为模式串长度

/*
算法流程：
1. 初始化 i(= pos) 、 j(= 1)
2. 当 i 、 j 均小于各自字符串的长度时循环：
若 S 的 i 位置与 T 的 j 位置元素相等，则 i 、 j 自增；
若不等，则 i 回退(= i - j + 2)， j 重置(= 1)
3. 循环结束后，若 j > T[0]，则返回 i - T[0]；否则返回 0
*/

int Index(String S, String T, int pos)
{
    i = pos;	j = 1;
    
    while(i <= S[0] && j <= T[0])
    {
        if(S[i] == T[j])	{++i;	++j;}
        else	{i = i - j + 2;	j = 1;}
    }
    
    if(j > T[0])	return i - T[0];
    else    return 0;
}

KMP 算法

匹配算法

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
// 算法 4.6
// KMP 算法
// 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后位置
// 其中 T 非空， 1 ≤ pos ≤ StrLength(S)
// 时间复杂度 O(n + m)，n 为主串长度，m 为模式串长度

/*
算法流程：
1. 初始化 i(= pos) 、 j(= 1)
2. 当 i 、 j 均小于各自字符串的长度时循环：
若 S 的 i 位置与 T 的 j 位置元素相等或者 j 为 0 （别漏），则 i 、 j 自增；
若不等， j 取 next[j]
3. 循环结束后，若 j > T[0]，则返回 i - T[0]；否则返回 0
*/

int Index_KMP(SString S, SString T, int pos)
{
    i = pos;	j = 1;
    
    while(i <= S[0] && j <= T[0])
    {
        if(j == 0 || S[i] == T[j])            // 继续比较后续字符
        {
            ++i;
            ++j;
        }
        else                                  // 模式串向右移动
        {
            j = next[j];
        }
    }
    
    if(j > T[0])                              // 匹配成功
        return i - T[0];
    else
        return 0;
}

计算 next 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 算法 4.7
// 求模式串 T 的 next 函数值并存入数组 next
// 时间复杂度 O(m)


void get_next(SString T int next[])
{
    i = 1;	next[1] = 0;	j = 0;// i 从 1 开始，j 从 0开始 
                                  // next[1]= 0
    
    while(i < T[0])
    {
        if(j == 0 || T[i] == T[j])// j == 0 别漏
        {
            ++i;
            ++j;
            next[i] = j;  // j 为最长相等前后缀长度
        }
        else
            j = next[j];  // 字符串移动公式（推导见王道 6.5.5节）
    }
}
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
// 算法 4.8
// 算法 4.7 的改进版，效率更高
// 求模式串 T 的 next 函数修正值并存入数组 nextval

void get_next(SString T int next[])
{
    i = 1;	nextval[1] = 0;	j = 0;
    
    while(i < T[0])
    {
        if(j == 0 || T[i] == T[j])
        {
            ++i;
            ++j;
            
            // 改进部分
            if(T[i] != T[j])// 连续不等情况
                nextval[i] = j;
            else            //连续相等情况
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

补充：一种手算 next 数组的方法

教材写的太难懂了，这里分享一下王道中的方法。

先理清几个概念：

  • 前缀：除最后一个字符，字符串的所有头部子串
  • 后缀：除第一个字符，字符串的所有尾部子串
  • 部分匹配值：字符串的前缀和后缀的最长相等前后缀长度

举个例子：计算 ‘ababa’ 的 next 数组

  1. 先算部分匹配值
子串 前缀 后缀 前后缀交集 最长相等前后缀长度
'a' \(\varnothing\) \(\varnothing\) \(\varnothing\) 0
'ab' {'a'} {'b'} \(\varnothing\) 0
'aba' {'a', 'ab'} {'ba', 'a'} {'a'} 1(= len('a'))
'abab' {'a', 'ab', 'aba'} {'bab', 'ab', 'b'} {'ab'} 2(= len('ab'))
'ababa' {'a', 'ab', 'aba', 'abab'} {'baba', 'aba', 'ba',' a'} {'a', 'aba'} 3(= len('aba'))

故部分匹配值为 00123

  1. 再算 next 数组

next 数组为上述匹配值先右移（左边补 -1），再每位加 1

此例便为

  • 右移：-10012 （注：若位序从 0 开始，取这个答案）
  • 每位加一：01123 （注：若位序从 1 开始，取这个答案）

故此例 next 数组为 01123

参考资料

  1. 数据结构（C语言版）.严蔚敏
  2. 2020年数据结构考研复习指导.王道论坛