目录

定义

串的存储结构

1.定长顺序存储

2.堆分配存储

3.块链存储

 串的基本操作

 串的模式分配

---

注：本章不在考研考纲范围，了解即可。

定义

串，也就是我们常说的字符串，我们在程序中经常这样定义

String S="*******";

里面字符的个数就是串的长度，没有字符就叫空串。（里面有空格，不算空串哦）

串的逻辑类型与线性表极为类似，区别在于串的数据对象限定于字符集。在基本操作上，串和线性表有很大区别。串经常以子串为操作对象。

串的存储结构

1.定长顺序存储

2.堆分配存储

3.块链存储

 

 类似于线性表的链式存储结构。因为每个元素只能放一个字符。所以在具体实现时，每个结点即可以放一个字符，也可以放多个字符。每个结点称为块，整个链表称为块链结构。

 串的基本操作

 串的模式分配

子串的定位操作通常称为串的模式分配

1.简单匹配算法

左图就是简单算法举例，下面是代码。

时间复杂度是o（nm），nm分别为子串和主串的长度。

 

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

2.KMP算法

过程比较多，这里推荐一个博主写的，很全面

https://blog.csdn.net/weixin_46007276/article/details/104372119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165692276516782391841891%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165692276516782391841891&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-104372119-null-null.142^v30^pc_rank_34,185^v2^tag_show&utm_term=kmp%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E8%AF%A6%E8%A7%A3&spm=1018.2226.3001.4187https://blog.csdn.net/weixin_46007276/article/details/104372119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165692276516782391841891%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165692276516782391841891&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-104372119-null-null.142^v30^pc_rank_34,185^v2^tag_show&utm_term=kmp%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E8%AF%A6%E8%A7%A3&spm=1018.2226.3001.4187