数据结构与算法——串

//比较操作，若S>T，则返回值>0；若S=T，则返回值=0；若S
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;
}
1
2
3
4
5
6
7
8
9
10

🌈定位操作

若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0。

int Index(SString S, SString T){
    int i = 1, n = StrLength(s), m = StrLength(T);
    SString sub;        //用于暂存子串
    while(i<=n-m+1){
        SubStriing(sub, S, i, m);
        if(StrCompare(sub, T) != 0){
            i++;
        }else{
            return i;       //返回子串在主串中的位置
        }
    }
    return 0;       //S中不存在与T相等的子串
}
1
2
3
4
5
6
7
8
9
10
11
12
13

​

🚢堆分配存储表示

这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配而得。利用函数malloc()为每个新产生的串分配一块实际串长所需要的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长作为存储结构的一部分

#define MAXLEN 255      //预定义最大串长为255
typedef struct{
    char *ch;           //按串长分配存储区，ch指向串的基地址
    int length;         //串的长度
}HString;

HString S;
S.ch = (char *)malloc(MAXLEN * sizeof(char));
S.length = 0;
1
2
3
4
5
6
7
8
9

这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的。

由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用

🚢链式存储表示

和线性表的链式存储结构相类似，可采用链表方式存储串值，由于串结构的特殊性——结构中的每个数据是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。当结点大小大于1时，由于串长不一定是结点大小的整数倍，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或者其他非串值字符（通常“#”不属于串的字符集，是一个特殊的符号

第一种表示：

typedef struct StringNode{
    char ch;        //每个节点存一个字符
    struct StringNode * next;
}StringNode, * String;
1
2
3
4

为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针表示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构

第二种表示：

typedef struct StringNode{
    char ch[4];        //每个节点存多个字符
    struct StringNode * next;
}StringNode, * String;
1
2
3
4

由于在一般情况下，对串进行操作时，只需要从头向尾扫描即可，则对串值不必建立双向链表。设尾指针的目的是为了便于进行联结操作，但应注意联结时需要处理第一个串尾的无效字符

在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率

存储密度可定义为：串值所占的存储位/实际分配的存储位

存储密度小（如结点大小为1时），运算处理方便，然而，存储占用最大，如果在串处理过程中需要进行内、外存交换的话，则会因为内外存交换操作过多而影响处理的总效率。一般地，字符集小，则字符的机内编码就短，这也影响串值的存储方式的选取。

串值的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的来说不如另两种存储结构灵活，它占用存储量大且操作复杂。

🚀拓展

🚢朴素模式匹配算法

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

朴素模式匹配算法：
将主串中与模式串长度相同的子串提出来，一个一个与模式串进行比较，当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。

int Index(SString S, SString T){
    int k=1;
    int i=k, j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i] == T.ch[i]){
            ++i;
            ++j;        //继续比较后继字符
        }else{
            k++;        //检查下一个子串
            i=k;
            j=1;
        }
    }
    if(j>T.length){
        return k;
    }else{
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

若模式串长度为m，主串长度为n，则匹配成功的最好时间复杂度为：O(m)，匹配失败的最好时间复杂度为：O(n)

若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要$（n-m+1）\ast m$次比较。最坏时间复杂度就可表示为：O(nm)

🚢KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针i会经常回溯，导致时间开销增加。KMP算法的出现就是为了解决主串指针回溯问题。

int Index_KMP(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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里只是对KMP算法的 一个简单介绍，并没有过多深入，但是KMP算法是串这一章节中比较重要的一个算法，后面还会涉及到next数组的推算等等，所以将会在以后单独出一篇文章讲解KMP算法。

💻总结

在经过将近一个多月的停更后，本专栏的文章再次开始更新，之前因为个人原因停更，感谢各位小伙伴们的支持与等待，同样，在新文章更新的同时，我也会不断提高自己的创作水平，争取自己的文章能给小伙伴们带来更多的帮助。

本篇文章比较全面的讲解了数据结构中串这一节的详细内容，因其与线性表类似的结构，所以有些点并没有重复提起，但是关于串的知识点，小伙伴们要多花时间去细读文章，串是编程中处理字符串比较重要的数据结构。一如既往希望我的文章能给各位小伙伴们带来帮助，数据结构与算法专栏也在持续更细中！！！

🎨觉得不错的话记得点赞收藏呀！！🎨

😀别忘了给我关注~~😀