串-数据结构

串-数据结构

串的定义

串,即字符串(String)是由零个或者多个字符组成的有限序列。一般计为S='a~1~a~2~......a~n~'(n>=0)。其中S是串名,单引号括起来的字符序列是串的值;a~i~可以是字母、数字或者其他字符;串中字符的个数n称为串的长度。n=0时的串称为空串(可以用数学符号∅表示)。

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

主串:包含子串的串。

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

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

例如:

S="HelloWord"
T='iPhone 15 Pro Max'

注意:有的语言使用双引号,如Java、C。有些地方用单引号,如Python。

'iPhone','Pro M'是串T的子串。

T是子串'iPhone'的主串。

'1'在T中的位置是8。(第一次出现)

'15 Pro'在T中的位置为8。

注意:位序从1开始,而不是从0开始。

例如:

M=''
N='   '

M是空串,而N是由三个空格字符组成的空格串,每个空格字符占1B。

串与线性表的关系

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

串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等)

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

串的基本操作

假设有串T="",S="iPhone 15 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清为空串。

DestoryString(&S):销毁串。将串S销毁。(回收存储空间)

Concat(&T, S1, S2):串联接。同T返回由S1和S2连接而成的新串。

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

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

StrCompare(S, T):比较操作。若S>T,则返回值大于0,若S=T,则返回值为0,若S<T,则返回值小于0。

例如:

执行基本操作Concat(&T, S, W)后,T="iPhone 15 Pro Max?Pro"

执行基本操作SubString(&T, S, 4, 6)后,T="one 15"

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

串的比较操作

从第一个字符开始往后依次对比,先出现更大字符的串就更大(ASCII表)。长串的前缀与短串相同时,长串更大。只有两个串完全相同时,才相等。

串的存储结构

串的存储结构包含顺序存储、链式存储、基于顺序存储实现基本操作。

串的顺序存储

静态数组实现(定长顺序存储)

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

动态数组实现(堆分配存储)

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

int main(){
    HString S;
    S.ch=(char *) malloc(sizeof(char)); //使用完毕后,需要手动free释放空间
    S.length=0;
    return 0;
}
串的链式存储

有两种定义方法,读者可以进行对比,第一种方法的存储密度低,每个字符1B,而每个指针4B,第二种让每个结点存多个字符,提高存储密度。

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

//方法二
typedef struct StringNode{
    char ch[4]; //每个结点存多个字符
    struct StringNode *next;
}StringNode, *String;
基本操作的实现
求字串

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

S.ch=“wangdao”,S.length=7

w a n g d a o
0 1 2 3 4 5 6 7 8 9
#define MaxSize 255 //预定义最大串长为255
typedef struct {
    char ch[MaxSize];
    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。

例如:下面有T1和T2两个串。

w b n g d a o
0 1 2 3 4 5 6 7 8 9
w a n g
0 1 2 3 4 5 6 7 8 9
//比较操作
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):定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的 位置;否则函数值为0。

例如:主串为T1,子串为T2。

w a n g d a o
0 1 2 3 4 5 6 7 8 9
g d a
0 1 2 3 4 5 6 7 8 9
int Index(SString S, SString T){
    int i=1;
    n=StrLength(S);
    m=StrLength(T);
    SString sub; //暂存子串
    while(i<=n-m+1){ //循环条件,当i不超过主串中剩余长度与模式串长度之差加一时执行
        SubString(sub,S,i,m);
        if(StrCompare(sub, T)!=0)
        {
            i++;
        } else
        {
            return i; //返回子串在主串中的位置
        }
    }
    return 0; //S中不存在于T相等的子串
}
字符串朴素模式匹配算法

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

假如主串长度为n,模式串长度为m。

朴素模式匹配算法是一种简单直观的字符串匹配算法,它的基本思想是从主串的第一个字符开始,依次比较主串中每个可能与模式串匹配的子串与模式串本身是否相等。如果相等,则匹配成功;否则,继续尝试下一个位置。该算法的时间复杂度为O((nm+1)m),其中 n 是主串的长度,m 是模式串的长度。

int Index(SString S, SString T){
    int i=1, j=1; // 初始化指针 i 和 j
    while (i<=S.length && j<=T.length) // 当指针 i 和 j 均未超出字符串长度时
    {
        if(S.ch[i]==T.ch[j]) // 如果主串 S 和模式串 T 在当前位置上的字符相等
        {
            ++i; // 将指针 i 向后移动一位
            ++j; // 将指针 j 向后移动一位
        } else
        {
            i=i-j+2; // 如果不相等,则将指针 i 移动到上次比较的位置的下一个位置
            j=1; // 将指针 j 重新指向模式串 T 的开头
        }
        if(j>T.length) // 如果 j 超出了模式串的长度
        {
            return i-T.length; // 返回当前匹配的起始位置
        } else
        {
            return 0; // 如果 j 没有超出模式串长度,说明匹配失败,返回 0
        }
    }

}

最坏的情况,每个⼦串都要对⽐ m 个字符,共 n-m+1 个⼦串,复杂度 = O((n-m+1)m) = O(nm)。该算法最坏的时间复杂度为O(nm)。因为很多时候n的规模总是大于m。

字符串KMP算法

KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,用于在一个主串中查找一个模式串的出现位置。相比于朴素的模式匹配算法,KMP算法通过预处理模式串,利用模式串中的信息来尽量减少不必要的字符比较,从而提高了匹配的效率。

KMP算法的核心思想是利用模式串中的前缀信息,来尽可能地避免主串中的字符重复比较。

KMP算法主要分为两个步骤:预处理和匹配。

在预处理阶段,KMP算法会构建一个部分匹配表(Partial Match Table),也称为next数组,它记录了模式串中每个位置的最长可匹配前缀的长度。这个表能够告诉我们,在模式串匹配失败时,应该将模式串向右移动多少位才能继续匹配。

在匹配阶段,利用预处理得到的部分匹配表,将模式串与主串进行匹配。 从主串的第一个字符开始,同时从模式串的第一个字符开始,逐个比较字符。 如果匹配成功,则继续比较下一个字符。 如果匹配失败,根据部分匹配表将模式串向右移动一定的位数,继续与主串比较。 KMP算法的优点在于,它避免了不必要的字符比较,将时间复杂度降低到 (O(n+m)),其中 n 是主串的长度,m 是模式串的长度。 总的来说,KMP算法通过预处理构建部分匹配表,利用模式串中的信息来指导匹配过程,从而提高了字符串匹配的效率。

对于模式串 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++

提示:KMP算法未懂的读者,建议观看咸鱼学长对应该章节的内容,文字描述比较难以理解,结合PPT会减少学习难度。

总结KMP算法:对模式串进行预处理,减少不必要的对比开销。

下图为KMP代码实现方式。

KMP算法

KMP算法在某个元素比较失败时,主串指针i不会回溯,而朴素模式匹配指针会一直回溯。KMP算法最坏时间复杂度为O(m+n),其中求next数组时间复杂度为O(m),模式匹配过程最坏时间复杂度O(n)。

对于KMP算法,读者需要掌握如何对模式串求next数组,下面给出三个例子,并附带答案,读者可自行计算。

技巧:next[1]都⽆脑写 0,next[2]都⽆脑写 1,其他 next:在不匹配的位置前,划⼀根美丽的分界线模式串⼀步⼀步往后退,直到分界线之前“能对上”,或模式串完全跨过分界线为⽌。此时 j 指向哪⼉,next数组值就是多少。

①google

next[0] next[1] next[2] next[3] next[4] next[5] next[6]
0 1 1 1 2 1

②ababaa

next[0] next[1] next[2] next[3] next[4] next[5] next[6]
0 1 1 2 3 4

③aaaab

next[0] next[1] next[2] next[3] next[4] next[5]
0 1 2 3 4
KMP算法优化

nextval数组相比于next数组的改进主要在于其在某些特定情况下能够更好地优化模式串的移动,减少了不必要的比较次数。

  1. 跳过重复字符

    • 在next数组中,如果模式串中的某个字符与其前面的字符相等,则直接将指针后移一位。
    • 但是在nextval数组中,如果某个字符与其前面的字符相等,它会尝试继续向前跳跃到更远的位置,以避免不必要的比较。
    • 这样,nextval数组能够更快地跳过一系列重复的字符,减少比较次数。
  2. 减少不必要的回退

    • 在next数组中,当模式串中的某个字符与当前位置不匹配时,只能通过next数组中的值进行回退。
    • 而在nextval数组中,如果当前位置与主串中的某个字符不匹配,它可以根据前面已经比较过的信息,尽量跳到更远的位置,从而减少回退次数。
    • 这种优化能够减少在匹配过程中的不必要的回退,加快了算法的执行速度。

总的来说,nextval数组在某些情况下能够更好地优化模式串的移动,减少了不必要的比较次数和回退次数,提高了KMP算法的效率。这使得KMP算法在实际应用中更加高效。

附带两个例子供读者参考

nextval-1

nextval-2