从零开始的数据结构与算法(C)(2)

• 二.字符串
• • 1.串类型简介
  • 2.串的定长存储及其算法
  • • (1).抽象类型的三种定义方式
    • (2).两串拼接
    • (3).求字串
    • (4).串比较
  • 3.串的模式匹配算法
  • • (1).朴素匹配(BF算法)
    • (2).KMP算法
  • 4.一些关于串的例题

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

串相等：两个串长度与对应字符都相同时称为两串相等。

#define MAXSIZE 256
typedef struct
{
    char data[MAXSIZE];//存储串中元素的数组
    int curlen;
}SeqString;
SeqString s;

串长度：s.curlen+1;

定义方式①：用一个指针来指向最后一个字符。

定义方式②：在串尾存储一个不会在串中出现的特殊字符以作为串的终结符。（C语言中的）

定义方式③：用s[0]存放数串的长度信息。

int StrConcat(s1,s2,s){
    int i = 0,j = 0;
    int len1,len2;//两拼接串的长度
    //超过长度的情况
    if(len1+len2>MAXSIZE-1){
        return 0;
    }
    while(s1[j]!=''){
        s[i] = s1[j];
        i++;
        j++;
    }
    j = 0;
    while(s2[j]!=''){
        s[i] = s2[j];
        i++;
        j++
    }
    s[i] = '';//给新字符串加结尾符
    return 1;
}

int StrSub(char *t,char *s,int i,int len){
    int slen = StrLength(s);//获取原串的长度
    //位置不正确或长度不为正整数
    if(i < 1||i > slen||len <= 0){
        return 0;
    }
    for(int j = 0;j < len;j++){
        t[j] = s[i+j-1];
    }
    t[j] = '';
    return 1;
}

int StrComp(char *s1,char *s2){
    int i = 0;
    while(s1[i]==s2[i]&&s1[i]!=''){
        i++;
    }
    return s1[i]-s2[i];
}

简介：在主串s中寻找字串t的过程称为【模式匹配】。

算法思想：

首先将s1 (s串的第一个字符)与t1 (t串的第0个字符)进行比较，若不同，则将s2与t1比较，以此类推。当到si与t1相同时，再将他们之后的字符进行比较，若也相同，即如此继续往下比较。当si与t中某个字符tj不同时，则s返回本趟开始字符的下一个字符，即s(i-j+2)，t返回到t1，重复上述过程。

int StrIndex_BF(char *s,char *t){
    int i = 1,j = 1;
    int slen,tlen;//分别存放s串长度和t串长度
    slen = s[0];
    tlen = t[0];//串首位存放串长信息
    while(i <= slen&&j <= tlen){
        if(s[i]==t[j]){
            i++;
            j++;
        }else{
            i = i-j+2;
            t = 1;
        }
    }
    //当t指针已经超过t串长度，说明匹配成功
    if(j > tlen){
        return i-tlen;//或者i-j+1
    }
    return -1;
}

补充：该算法实现是从s串的第一个字符开始的，但有时算法要求从指定位置开始，这时可添加一个位置参数pos。该算法相当于pos=1的情况。

算法思想：改进BF算法的回溯。

举个例子：

主串s：a b a b c a b c a c b a b

字串t：a b c a c

希望在s(i) 和 t(j)匹配失败后，指针i不回溯，而将t向右滑动到某个位置k，从而使k继续对准s(i)。即s(i)和t(j)匹配失败后，指针i不动，模式t向右滑动，使t(k)继续对准s(i)。

next函数：

next函数是KMP算法中最为重要的一个部分。

※next函数规律总结：

当j = 1时，next[j] = 0;

当j = 2时，next[j] = 1;

当j > 2时，满足next[j] = （比较前k-1位，得出前后缀最大匹配长度k，令k+1，即是next[j]的值）;

举个栗子：对模式串a,b,c,a,c来说：

j = 0或j = 1填写固定值0和1。

j = 3时，看模式串的前j-1位，a和b，最长前缀a和后缀b不相等，所以其函数值为0+1 = 1。

j = 4时，看模式串的前3位，即a,b,c。前后缀a,c不相等，前后缀a,b 和 b,c不相等，所以函数值位0+1 = 1。

j = 5时，看模式串的前4位，即a,b,c,a,前后缀a,a相等，且为最长的前后缀匹配长度。所以函数值为1+1 = 2。

最终可以得到：next[j] = {0,1,1,1,2}

KMP算法实现：

int StrIndex_KMP(char *s,char *t,int pos){
    int i = pos,j = 1;
    int slen = s[0],tlen = t[0];//获取模式串和主串长度
    while(i <= slen && j <= tlen){
        if(j == 0||s[i] == t[j]){
            i++;
            j++;
        }
        //匹配失败时，让j重新处于next函数的位置
        else{
            j = next[j];
        }
    }
    //当j超过字串长度，即匹配成功
    if(t > tlen){
        return i-tlen;
    }
    return -1;
}

求解next函数的程序：

void GetNext(char *t,int next[]){
    int i = 1,j = 0;
    next[1] = 0;
    while(i < t[0]){
        while(t > 0&&t[i]!=t[j]){
            j = next[j];
        }
        i++;
        j++;
        if(t[i] == t[j]){
            next[i] = next[j];
        }else{
            next[i] = j;
        }
    }
}

a.两个字符串相等的条件是【两串长度相等，并且对应位置上的字符相同】。

b.字符串采用结点大小为1的链表作为其存储结构，是指【链表的每个链结点的数据域中只存放了一个字符】。

c.若串s = ‘’software’‘,则其字串的数目为【37】。

解析：一个字符串的字串数目为 (字符串长度*字符串长度+1)/2。

d.串’ababaaababaa’的next数组是【0，1，1，2，3，4，2，2，3，4，5，6】。

解析：第一位第二位为0，1固定值。

第三位开始，看前2位，a,b,最长前缀a，最长后缀b，不相等，故next[3] = 0+1 = 1。

…

第十一位：看前10位，ababaaabab,最长匹配前缀abab,最长匹配后缀abab，相等，所以next[11] = 4+1 = 5。

第十二位：看前11位，ababaaababa,最长匹配前缀ababa,最长匹配后缀ababa，相等，所以next[12] = 5+1 = 6。

e.以行序为主序存储二维数组A=array[6] [8],设每个数据元素占4个存储单元，基地址为1000，则LOC[2] [3] = 【1078】。

解析：A[0] [0]的内存地址是基地址(1000)。

由于是以行为主序存储，所以A[0] [1] 地址是1000+4 = 1004。

A[1] [0] 地址为 1000+8*4 = 1032。

推出以行为主序存储的地址计算公式为：1000+i* 8 *4+j * 4

所以A[2] [3]的地址为：1000+2* 8 * 4+3*4 = 1078。

f.设有数组A[i] [j]，数组的每个元素长度为3，i的值为1-8，j的值为1-10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为【】。

解析：注意A[5,8]指二维数组第五行第八列，换算成下标应该为A[4] [7]。

画图更容易理解：