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

---

一、简介

一共介绍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;
}

测试截图：