《数据结构》第四章 串

4.1 串的定义和实现

4.1.1 串的定义

串是由零个或多个字符组成的有限序列。

• 子串：串中任意个连续的字符组成的子序列。
• 主串：包含子串的串。
• 字符在主串中的位置：字符在串中的序号。
• 子串在主串中的位置：子串的第一个字符在主串中的位置。

空串：""
空格串：" "（空格串不是空串）

4.1.2 串的基本操作

• StrAssign(&T, chars):赋值操作。将chars赋值给T。
• StrCopy(&T, S):复制操作。
• StrEmpty(S):判空操作。
• Strcompare(S, T):比较操作。S>T，返回值>0；S=T，返回值=0，S<T，返回值<0。
• StrLength(S):求串长操作。
• SubString(&Sub, S, pos, len):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
• Concat(&T, S1, S2):串连接操作。
• Index(S, T):定位操作。
• ClearString(&S):清空操作。
• DestroyString(&S):销毁操作。

4.1.3 串的存储结构

1. 定长顺序存储表示

静态存储

#define MaxLen 255
typedef struct {
    char ch[MaxLen];
    int length;
}SString;

2. 堆分配存储表示

动态存储

typedef struct {
    char *ch;
    int length;
}HString;

HString S;
S.ch = (char *) malloc (MaxLen * sizeof(char)); //malloc分配
free(S);//free释放

3. 块链存储表示

串的链式存储
结点大小为 1的链表

typedef struct StringNode{
    char ch;
    struct StringNode *next;
}StringNode, *NString;

也可 结点大小为 4的链表，块链

typedef struct StringNode {
    char ch[4];
    struct StringNode *next;
}StringNode, *NString;

4. 基本操作的实现

• 求子串

  ♾️ C 代码:

  //求子串
  bootL Substring(SString &Sub，SString S，ijint pos,int Len){
    //子串范围越界
    if (pos+Len-1 > S$.Length)
        return faLse;
    for (int i=pos; i<pos+Len; i++)
        Sub.ch[i-pos+1l] = S$.ch[i];
    Sub.Length = Len;
    return true;
  }

• 比较操作

  ♾️ C 代码:

  //比较操作。若>T，则返回值>8; 若S=T，则返回值=9; 若S<T，则返回值<8
  int StrCompare(SString S，SString T) {
    for (int i=1;) i<=S,Length && i<=T,Length; i++){
        if (S.ch[il!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
  
    //扫描过的所有字符都相同，则长度长的串更大
    return S.Length - T.Length;
  

• 定位操作

  ♾️ C 代码:

  //若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
  int Index(SString S，SString T){
    int i=1，n=StrLength(S) ,m=StrLength(T);
    SString sub;   //用于暂存子串
    whitLe(i<=n-m+1){
        Substring(sub,S,im);
        if(StrCompare(sub，T) !=0) ++i;
            else return ij; //返回子串在主串中的位置
    }
    return 0;  //S中不存在与T相等的子串
  }

4.2 串的模式匹配

4.2.1 简单的模式匹配算法

也称 暴力匹配算法。

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

该算法最坏时间复杂度为 $O(nm)$

4.2.2 串的模式匹配算法——KMP算法

求 next[]数组算法

void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while(i < T.length){
        if(j == 0||T.ch[i] == T.ch[j]) {
            ++i; ++j;
            next[i] = j;
        }
        else 
            j = next[j];
    }
}

KMP算法

int Index_KMP(SSstring S,SSstring 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;
}

4.2.3 KMP算法的进一步优化

进一步优化 next[]成 nextval[]

void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while(i < T.length){
        if(j == 0||T.ch[i] == T.ch[j]){
            ++i; ++j;
            //和求 next 的主要变动
            if(T.ch[i] != T.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
    }
}

优化后的KMP算法

int Index_KMP(SSstring S,SSstring T,int nextvel[]){
    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;
}