数据结构 408-4-1&2 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 串的定义

串，即字符串是由零个或多个字符组成的有限序列。一般记为 $S='a_1a_2......a_b'(n\ge0)$

其中，S 是串名，单引号括起来的字符序列是串的值； $a_i$ 可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n=0 时串称为空串 (用 $\phi$ 表示)

子串：串种任意个连续的字符组成的子序列

主串：包含子串的串

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

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

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

串的数据对象限定为字符集

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

# 串的基本操作

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；

注意：采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符栈 1B 即可

# 串的顺序存储

#define MaxSize 255 
typedef struct{
    char ch[MaxSize];
    int length;
}SString; //静态数组实现

typedef struct{
    char *ch;
    int length;
}HString; //动态数组实现
HString S;
S.ch=(char *)malloc(MAXLEN*sizeof(char));
S.length=0;

# 串的链式存储

typedef struct StringNode{
    char ch;
    struct StringNode * next;
}StringNode,*String //存储密度低，每个字符1B，每个指针4B
    
typedef struct StringNode{
    char ch[4]; //每个节点存多个字符
    struct StringNode * next;
}StringNode,*String

# 基本操作的实现

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

# 朴素模式匹配算法

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

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

模式串：不一定能在朱传众找到

朴素模式匹配算法：将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串或者所有的子串都不匹配为止（最多 n-m+1 的子串）

若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置

若 j>T.length，则当前子串匹配成功，返回当前子串第一个字符的位置 ——i-T.length

最坏时间复杂度为 O (mn)

# KMP 算法

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

next 数组求解：

next [1] 填 0，next [2] 填 1

其他 next：在不匹配的位置前，划一根分界线，模式串一步一步后退，直到分界线之前能对上，或模式串完全跨过分界线为止，此时 j 指向哪，next 数组值就为多少。

KMP 算法，最坏时间复杂度为 O (m+n)，其中求 next 数组时间复杂度为 O (m)，模式匹配过程最坏时间复杂度为 O (n)

nextval 数组：先求 next 数组，再求 nextval 数组：

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

数据结构考研408