数据结构——串，数组和广义表学习篇(一)

前言

昨天一直在做关于KMP算法的事情，今天把数据结构中串，数组和广义表的知识点梳理一下

串

定义：是由零个或多个字符组成的有限序列，又称字符串。

串的长度：串中字符的数目称为串的长度。

空串：由零个字符组成的串叫做空串，空串不包括任何字符，其长度为零。

子串：串中任意个连续的字符组成的子序列称为该串的子串，空串是任何串的子串。

主串：包含子串的串相应的称为主串。

串有两种表示形式：顺序存储表示和链式存储表示。

顺序存储表示：串的顺序存储结构简称为顺序串，顺序串中的字符序列被顺序地存放在一组连续的存储单元中，主要有三种实现顺序串的方式。

串的顺序存储

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];//存储串的一维数组
    int length; ///串当前的长度 
}SString;

注意：对于上面的数组加1是为了让数组的下标从1开始，为了避免麻烦而为之

串的堆式顺序存储结构

typedef struct{
    char *ch; 
    int length; ///串当前的长度 
}HString;

串的链式存储

#define CHUNKSIZE 80
typedef struct Chunk {
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;
typedef struct {
    Chunk *head,*tail;//串的头指针和尾指针
    int length;
} LString;

BF算法

主串和字串都是从第一个位置进行比较即i=1;j=1

int Index_BF(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;
    }
}

去除特殊的位置进行匹配，也就是说让主串从任意位置与字串进行匹配，只需要把i=1,变成i=pos就可以了，pos代表主串匹配的位置

int Index_BF(SString S,SString T int pos) {
    int i=pos,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;
    }
}

注意：其实BF算法就是一个简单的回溯，只需要一直回溯，然后进行字符串的匹配就可以了，其中的i-j+2可以看成是(i-j)+2

就是为了从i所在位置的下一个位置进行匹配就可以了

nextval[]数组计算：