数据结构-串

串的定义:

    串(String)是零个或多分字符组成的有限序列

一般记作: S=”a1a2a3…an”

其中,S是串名,“a1a2a3…an是串值,ai(1 <= i <= n)可以是字母、数字或其他字符

串的长度:串中所包含的字符个数

    长度为零的串称为空串(Empty String),它不包含任何字符。

* 空白串:仅包含一个或多个空格组成的串 (Blank String)

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

* 通常将子串在主串中首次出现时地该子串地首字符对应地主串中地序号,定义为子串在主串中的位置(或序号)

特别地,空串是任意串地子串,任意串是其自身地子串

串的基本运算:

    串赋值: StrAssign(&S, char s)

    串比较: StrCompare(S,T)

    求串长: StrLength(S)

    串联接: Concat(&T, S1, S2)

    求子串: SubString(&sub, S, pos, len)

    子串定位: Index(S, T, pos)

同样,串也分为顺序存储和链式存储

 串的顺序存储

定长度顺序存储:

typedef struct{
    char ch[MaxStrlen];
    int length;
}SqString;

堆分配存储:

typedef struct{
    char *ch;
    int length;
}Hstring;

顺序串求子串

int find_string(SqString s,SqString t)
{
    int i,j,flage;
    for(i=0;i<s.length;i++)
    {
        for(j=0;i<t.length;j++)
        {
            if(s.data[i+j]!=t.data[j])
            {
                break;
            }
            if(j==t.length-1)
                return i+1;
        }
    }
    return -1;
}

堆串求子串

Status SubString(HString *sub,HString S,int pos,int len)
{//思路大概是再申请一个串来存储主串上某序列的子串,在位置pos之后的所有字符为该子串
    int i;
    if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
    {
        return ERROR;
    }
    if(sub->ch)
    {
        free(sub->ch);
    }
    if(!len)
    {
        sub->ch=NULL;
        sub->length=0;
    }
    else
    {
        sub->ch=(char *)malloc(len *sizeof(char));
        for(i=0;i<len;i++)
        {
            sub->ch[i]=S.ch[pos-1+i];
        }
        sub->length=len;
    }
    return OK;
}

串的模式匹配算法

1.基本的模式匹配算法——BF(brute force)匹配(朴素的模式匹配算法)

2.KMP模式匹配算法(改进的模式匹配算法)

BF算法:

int find_string(SqString s, SqString t){    //s为主串。t为模式串
    int i, j;
    for ( i = 0;i < s.length; i++)
    {
        for (j = 0;i < t.length; j++)
        {
            if (s.data[i + j] != t.data[j])    //当模式串的第j位和主串匹配位后j位不同时break
                 {
                      break;
                 }
            if (j == t.length - 1)     //当主串匹配位等于子串长度时,返回匹配位(i+1)
               return i + 1;
        }
    }
    return -1;
}

KMP算法:

    在基本的匹配算法中,当主串的字符Si与模式串Ti失配时。令i退回到本次匹配的起始位置,加1后再开始下一次的匹配

    在KMP算法中,使I不回溯,而是将j退回到模式串的第K个字符位置上(模式串右移),再继续进行匹配(将之前已部分匹配的结果用上)

int Index_KMP(SString S, SString P, int pos)

{

    //返回模式串P再主串S中从第pos个字符开始的位置

    //要求P非空, 1<= Strlength(S)

    I = pos; j = 1; Get_next(P,next);

    while (I <= Strlength(S) && j <= Strlength(P))

    {

        if ( j == 0 || S[i] == P[j])

            {

                ++i;++j;

            }

        else 

            j = next[j];

    }

    if ( j > Strlength(S))

        return (I – Strlength(P));

    return 0;

}

而用于计数的next[]数组的求法:

注意j从1开始!

一直next[1] = 0,设next[j] = k,求next[j + 1]:

    (1)若P[j] == P[next[j]],则next[j + 1] = k + 1(即next[j + 1] = next[j] + 1)

    (2)若P[j] != P[next[j]],则令P[j]和P[next[next[j]]]比较

        若相等,则next[j + 1] = next[next[j]] + 1

        若不等,则令P[j]和P[next[next[next[j]]]]比较,不等的话继续,直到某个P[next[…next[j]…]==O[j],或next[…next[j]…] == 0,此时置next[j + 1] = next[…next[j]…] + 1

int Get_next(SString P, int next[]){
    //求模式串P的next函数值并存入数组next
    j = 1; next[1] = 0; k = 0;
    while (j <= Strlength(P)){
        if (k == 0 || P[j] == P[k]){
            ++j;
            ++k;
            next[j] = k;
        }
        else
            k = next[k];
     }
}
//求next[]的改进算法
void Get_next(SString P, int next[])
{
    j = 1; next[1] = 0; k = 0;
    while (j <= Strlength(P)){
        if (k == 0 || P[j] == P[k]){
            ++j; ++k;
            if (P[j] != P[k])        //注意这里是改进的地方
                next[j] = k; //注意这里是改进的地方 else //注意这里是改进的地方 next[j] = next[k]; //注意这里是改进的地方 }
        else
            k = next[k];
    }
}

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注