[数据结构与算法]数据结构--串

准备工作

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<windows.h>

//函数结果状态字符
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef char ElemType;

1.串的顺序存储结构

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

2.串的链式存储结构

#define CHUNKSIZE 80  //块的大小可以自定义
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct
{
    Chunk *head,*tail;  //串的头指针和尾指针
    int curlen;         //串的当前长度
}LString;               //字符串的块链结构

3.确定主串中所含子串第一次出现的位置（BF算法）

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;//主串、字串指针回溯重新开始下一次匹配
        }     //其中i-j+2 使得刚好回溯到本轮匹配初始位置的下一个字符
    } 
    if(j>=T.length) return i-T.length;  //返回匹配的第一个字符的下标
    else return 0;   //模式匹配不成功
}

其时间复杂度较差: O(n*m)。

4.确定主串中所含子串第一次出现的位置（KMP算法）

//计算next函数值
/void get_next(SString T, int next[])
{
    //求模式串T的next函数值并存入数组next
    i = 1; next[1] = 0; j=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(SString S, SString T, int pos)
{
    //利用模式串T的next函数求T在主串中第pos个字符之后的位置
    //其中，T非空，1<=pos<=S.length
    i = pos; 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;
}