书上串的基本操作以及BF算法

data_structure

一、简介

一共介绍4个函数，如下：

void StrCat(char * s1,char *s2);
int StrCmp(char* s1,char* s2);
void StrCpy(char* s1,char* s2);
int BFmatching(char* s,char* t);

二、实现

2.1 StrCat

用于连接两个字符串，放到第一位上去

void StrCat(char * s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    if(len1 + len2 >  MaxSize-1)
    {
        cerr<<"超长";
        exi t(1);
    }
    int i=0;
    while (s2[i]!='\0')
    {
        s1[i+len1] = s2[i];
        i++;
    }
    s1[i+len1] = '\0';
}   

要注意，这里由于用到了MAXSIZE判定是否溢出，所以在测试的时候，要把字符串大小置为这么大。

2.2 StrCmp

字符串比较

• 若s1< s2,输出负数
• 若s1< s2,输出0
• 若s1> s2,输出正数

代码如下：

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

2.3 StrCpy

拷贝s2的内容到s1

void StrCpy(char* s1,char* s2)
{
    int len = strlen(s2);
    if(len > MaxSize-1)
    {
        cerr<<"超长";
        exit(1);
    }
    while(*s1++= *s2++);
}

2.4 BFmatching

简单的模式匹配算法

int BFmatching(char* s,char* t)
{
    int i,j,n,m;
    i = 0;
    j = 0;
    n = strlen(s);
    m = strlen(t);
    while(i<n && j<m)
    {
        if(s[i] == t[j])
        {
            i++;
            j++;
        }
        else 
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if(j >= m)
        return i-j;
    else
        return -1;
}

三、测试

int main()
{
    char s1[MaxSize] = "Data";
    char s2[MaxSize] = " Structures";
    cout<<"s1:"<<s1<<endl;
    cout<<"s2:"<<s2<<endl;
    cout<<"测试连接函数，并输出S1"<<endl;
    StrCat(s1,s2);
    cout<<s1<<endl;
    cout<<endl;
    char s3[MaxSize] = "in c++";
    char s4[MaxSize] = "c++";
    cout<<"测试比较函数(s3,s4)，并输出结果"<<endl;
    cout<<StrCmp(s3,s4)<<endl;
    cout<<endl;
    cout<<"测试拷贝函数(s1,s2)，并输出结果"<<endl;
    StrCpy(s1,s2);
    cout<<"拷贝后："<<endl;
    cout<<"s1:"<<s1<<endl;
    cout<<"s2:"<<s2<<endl;
    cout<<endl;
    cout<<"测试BF匹配(s3,s4)，并输出结果"<<endl;
    int v=BFmatching(s3,s4);
    if(v == -1)
    {
        cout<<"匹配失败"<<endl;
    }
    else
    {
        cout<<s4<<"在"<<s3<<"中首次出现的下标为 "<<v<<endl;
    }
    cout<<endl;
    cout<<"测试BF匹配(s4,s3)，并输出结果"<<endl;
    v=BFmatching(s4,s3);
    if(v == -1)
    {
        cout<<"匹配失败"<<endl;
    }
    else
    {
        cout<<s4<<"在"<<s3<<"中首次出现的下标为 "<<v<<endl;
    }
    return 0;
}

测试截图：