头歌 数据结构 实训四——串

前言：

花了20分钟作业写的三道题，没什么难度可言，这里就不详细解答了，只给出要求填写的函数代码(其中的乱码是中文，可以是编译格式问题导致的，不影响代码)。

第一关：求子串

void SubStr(SString t, SString s,int i,int len)
//从s的第i个字符开始截取长度为len的子串存入t中。
//其中1≦i≦串s的长度, 0≦len≦ 串s的长度-i+1。
//若i和len超出取值范围，则输出"error"；否则输出子串t。
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int j=0;
    if(i<1||i>s[0]||len<0||len>s[0]-i+1){
        printf("error\n"); 
    }else if(len==0){
        printf("");
    }else{
        for(j=i;j<i+len;j++){
            t[j-i]=s[j];
        }
        t[j+1]='\0';
        printf("%s",t);
    }
    /********** End **********/
}

第二关：串的模式匹配之简单算法

int StrIndex_BF(SString s, SString t, int pos)
//´ÓÖ÷´®sµÄµÚpos¸ö×Ö·û¿ªÊ¼²éÕÒ×Ó´®t¡£
//ÈôÕÒµ½£¬Ôò·µ»Ø×Ó´®tÔÚÖ÷´®sÖеÚÒ»´Î³öÏÖµÄλÖ㬷ñÔò·µ»Ø0¡£
{
    // ÇëÔÚÕâÀï²¹³ä´úÂ룬Íê³É±¾¹ØÈÎÎñ
    /********** Begin *********/
    int m=s[0];int n=t[0];
    char tmp=s[1];
    for(int i=1;i<=m-n;i++){
        for(int j=0;j<n;j++){
            if(s[i+j]!=t[j+1]){
                break;
            }else{
                if(j==n-1){
                    return i;
                }
            }
        }
    }
    return 0;
    /********** End **********/
}

第三关：串的模式匹配之KMP算法

void GetNext(SString t, int next[])
//Çóģʽ´®TµÄnextÖµ²¢´æÈënextÊý×éÖÐ
{
    // ÇëÔÚÕâÀï²¹³ä´úÂ룬Íê³É±¾¹ØÈÎÎñ
    /********** Begin *********/
    int j=1;int i=0;next[1]=0;
    while(j<=t[0]){
        if(i==0||t[j]==t[i]){
            i++;j++;
            next[j]=i;
        }else{
            i=next[i];
        }
    }
    /********** End   *********/
}