数据结构之串

串的定义

串：内容受限的线性表

由零个或多个任意字符组成的有限序列

子串：一个串中任意个连续字符组成的子序列
主串：包含子串的串相应地称为主串
字符位置：字符在序列中的序号
子串位置：子串第一个字符
空格串：由一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等并且各个对应的位置上字符都相等（所有空串都相等）

串的类型定义

ADT String{
   数据对象：D={ai|ai属于Characterset，(i=1,2,3...n，n>=0)}  

   数据关系：R={<ai-1，ai>|ai-1，ai属于D，(i=1,2,3...n)}

   基本操作：
   串赋值
   穿比较
   求串长
   串连结
   ...
}ADT String

串中元素逻辑关系与线性表相同

串的顺序存储结构

#define MAXLEN 255   
typedef struct {
    char ch[MAXLEN+1];//存储串的一维数组（0号位一般不用）
    int length; //串的当前长度
}SString;

串的链式存储结构-块链结构

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

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

串的模式匹配算法

算法目的：确定主串中所包含子串（模式串）第一次出现的位置

算法种类：BF算法、KMP算法

串的BF算法

i-j+1是原始位置，再+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；//匹配不成功
    }
}

//从主串的中间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；//匹配不成功
    }
}

串的KMP算法

计算next[j]=k；k-1=5（如上图，则k=6）

void get_next(SString T,int &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];
     }
}

//从主串的中间pos处开始找
int Index_KMP(SString S,SString T，int pos){
    int 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]; //i不变，j后退 
        }
        if(j>T.length)return i-T.length;//返回匹配的第一个字符的下标  
        else return 0；//匹配不成功
    }
}