数据结构-串数组广义表笔记

4.1 串的定义

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

零个字符的串称为空串(null string),长度为零。

由一个空格或多个空格的串“ ”称为空格串(blank string)。

串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串

只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。

4.3 串的存储结构

1.顺序存储(多采用)

静态分配:

1 #define MAXLEN 255    //串的最大长度
2 typedef struct{
3     char ch[MAXLEN+1];    //存储串中的一堆数组
4     int length;    //当前串长
5 }SString;

动态(堆式):

typedef struct{
    char *ch;   //若是非空串,则按串长分配存储区,否则ch为NULL
    int length; //串长
}HString;

2.链式存储

结点大小问题:每个结点可以可以存放一个字符,也可以存放多个字符。

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

4.3.3 串的模式匹配算法

BF算法:

int Index(SString S,SString T,int pos)
{
    int i=pos;int j=1;  //初始化
    while (i<=S.length && j<=T.length)  //未比较到串尾
    {
        if (S.ch[i]==T.ch[i]){i++;j++;} //比较后继字符
        else{i=i-j+2;j=1;}  //后退重新匹配
    }
    if(j>T.length) return i-T.length;
    else return 0;
}

平均时间复杂度O(n*m)

KMP算法:

int Index_KMP(SString S,SString T,int pos)
{
    i=pos;j=1;
    while(i<=s.length && j<=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;
}

平均时间复杂度O(n+m)

原文地址:https://www.cnblogs.com/loglian/p/12878636.html