模拟实现strstr函数

模拟实现strstr函数推荐一篇讲解KMP算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html推荐一篇讲解Boyer-Moore算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html…

大家好,又见面了,我是你们的朋友全栈君。

推荐一篇讲解KMP算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

推荐一篇讲解Boyer-Moore算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html


strstr函数用于在字符串中查找字串,本篇博客我们主要讲解一下它的实现过程。以我自己为例,刚开始写strstr函数的实现还是漏洞百出的。下面就记录一下我当时的思考过程。

strstr在进行字串查找时,如果找到,则返回字串在源字符串中第一次出现的位置;如果没有找到,则返回NULL。下面我们逐步来看可能出现的各种情况。

(1)源串:abcd

          字串:bc

思路:让str和sub两个指针分别指向源串和字串的起始位置,然后进行比较,如果相等,则str和sub指针同时向后移,在比较下一个字符;如果不相等,则另str指针向后移,然后再进行比较。比较结束的时间点:str和sub指针当中有任意一个已经到达了字符串末尾‘\0’处。如果sub到达‘\0’,则说明两个字符串已经相等。

则不难写出以下代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
	assert(str);
	assert(sub);
	while (*str != '
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
}
}
if (*sub == '\0')
{
return ?;
}
return NULL;
}
int main()
{
char str[] = "abcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);
system("pause");
return 0;
}
'&&*sub != '
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
}
}
if (*sub == '\0')
{
return ?;
}
return NULL;
}
int main()
{
char str[] = "abcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);
system("pause");
return 0;
}
') { if (*str == *sub) { str++; sub++; } else { str++; } } if (*sub == '
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
}
}
if (*sub == '\0')
{
return ?;
}
return NULL;
}
int main()
{
char str[] = "abcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);
system("pause");
return 0;
}
') { return ?; } return NULL; } int main() { char str[] = "abcd"; char *p ; p = Strstr(str, "bc"); printf("%s", p); system("pause"); return 0; }

 注意看“return ?”这里,按照上面所举的例子,对应的逻辑,我们已经遍历到了字串的\0处,判断出来字串bc在对应源串的1(这里见图解)处,那么问题来了?虽然已经找到了字串对应的位置,但是如何返回呢?str指针已经移动到了3(即d)的位置处。很明显无法在找到字串第一次出现的位置了。

这个问题给我们的启示是:在两个指针不断移动进行比较期间,一定要保存下匹配的位置。那么如何保存呢?显然还需要定义另一个指针。回顾我们一开始的思路:一直都是拿原生的两个指针进行移动比较。所以对于这个问题,显然仅仅原生指针比较是不可行的。

想明白问题所在的点后,我们对代码进行修改(这里我们又定义了一个start指针,用于保存第一次匹配成功时记录位置)

模拟实现strstr函数

char*Strstr(const char*str, const char*sub)
{
	assert(str);
	assert(sub);
	const char*start = str;//start指针保存匹配成功的位置
	while (*str != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
start = str;
}
}
if (*sub == '\0')
{
return start;
}
return NULL;
}
'&&*sub != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
start = str;
}
}
if (*sub == '\0')
{
return start;
}
return NULL;
}
') { if (*str == *sub) { str++; sub++; } else { str++; start = str; } } if (*sub == '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
start = str;
}
}
if (*sub == '\0')
{
return start;
}
return NULL;
}
') { return start; } return NULL; }

运行结果:

模拟实现strstr函数

但是如果例题改为在abbcd中查找bc,则结果就不正确了

char str[] = "abbcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);

运行结果:

模拟实现strstr函数

我们来分析一下原因,当两个指针都走到2时,b与c不匹配,这时,str指针继续往后走,即走到3的位置,然后赋给了start指针,这时str和sub指针都指向了c;最后一步,sub指针已经到达‘\0’,循环退出,所以最后输出的就是cd。本次的出错点就在:当str走到第二个b时(2的位置),发现与c不匹配,那么那一次比较时,就要重新字串的起始位置处进行比较,而不是直接往后走。

模拟实现strstr函数

于是我们尝试着再把代码做修改:

char*Strstr(const char*str, const char*sub)
{
	assert(str);
	assert(sub);
	const char*start = str;//start指针保存匹配成功的位置
	const char*sub_p = sub;//另sub_p遍历字串
	while (*str != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//另sub_p遍历字串
while (*str != '\0'&&*sub_p != '\0')
{
if (*str == *sub_p)
{
str++;
sub_p++;
}
else
{
str++;
start = str;
sub_p = sub;//回到字串的起始位置进行重新匹配
}
}
if (*sub_p == '\0')
{
return start;
}
return NULL;
}
'&&*sub_p != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//另sub_p遍历字串
while (*str != '\0'&&*sub_p != '\0')
{
if (*str == *sub_p)
{
str++;
sub_p++;
}
else
{
str++;
start = str;
sub_p = sub;//回到字串的起始位置进行重新匹配
}
}
if (*sub_p == '\0')
{
return start;
}
return NULL;
}
') { if (*str == *sub_p) { str++; sub_p++; } else { str++; start = str; sub_p = sub;//回到字串的起始位置进行重新匹配 } } if (*sub_p == '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//另sub_p遍历字串
while (*str != '\0'&&*sub_p != '\0')
{
if (*str == *sub_p)
{
str++;
sub_p++;
}
else
{
str++;
start = str;
sub_p = sub;//回到字串的起始位置进行重新匹配
}
}
if (*sub_p == '\0')
{
return start;
}
return NULL;
}
') { return start; } return NULL; }

结果:

模拟实现strstr函数

结果还是错误,原因在于:当str走到2(b)时,sub_p也走到2(c)时,发现不匹配,这时本应该sub_p回到子串起始位置处,str继续从2(b)的位置处开始比较。但是由于else语句中str先++了,所以str直接指向了3(c),随后sub_p指向初始位置b,所以后边再怎么比较也不可能有匹配的字符串。

模拟实现strstr函数

综上:我们用了很长的篇幅去分析代码每次出现的错误,每分析出来错误的点进行修改总是“当前问题解决了,但是又带来了新问题”,说明之前的代码框架有问题,这时不如重新构建一下代码框架,换个思路。


通过上面众多例子的分析:搞清楚了两个最重要的问题:

(1)匹配成功时,最后返回的是字串第一次出现的位置。而两个指针进行比较时都是依次向后移动的,只有字串的指针到达\0才说明匹配成功,那这时指针已经指向了后面的字符,怎么返回匹配成功的第一个字符的位置?所以就需要再定义一个指针来保存这个位置

(2)基本的逻辑我们已经知道,当连个指针指向的字符相同时,指针都向后移,再比较下一个字符;当不同时,源字符串的指针向后移一位,进行比较。注意,这时比较就要从字串的起始处重新开始比较了。

综上,整理一下逻辑,如图所示–>

模拟实现strstr函数

最终代码:

char*Strstr(const char*str, const char*sub)
{
	assert(str);
	assert(sub);
	const char*str_p = str;//sub_p指针遍历源字符串进行比较
	const char*start = str;//start指针保存匹配成功的位置
	const char*sub_p = sub;//sub_p遍历子串进行比较
	while (*start != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//sub_p指针遍历源字符串进行比较
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//sub_p遍历子串进行比较
while (*start != '\0')
{
str_p = start;
sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较
while (*str_p != '\0'&&*sub_p != '\0')
{
if (*str_p == *sub_p)
{
str_p++;
sub_p++;
}
else
{
break;
}
}
if (*sub_p == '\0')
{
return start;
}
start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配
}
return NULL;
}
') { str_p = start; sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较 while (*str_p != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//sub_p指针遍历源字符串进行比较
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//sub_p遍历子串进行比较
while (*start != '\0')
{
str_p = start;
sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较
while (*str_p != '\0'&&*sub_p != '\0')
{
if (*str_p == *sub_p)
{
str_p++;
sub_p++;
}
else
{
break;
}
}
if (*sub_p == '\0')
{
return start;
}
start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配
}
return NULL;
}
'&&*sub_p != '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//sub_p指针遍历源字符串进行比较
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//sub_p遍历子串进行比较
while (*start != '\0')
{
str_p = start;
sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较
while (*str_p != '\0'&&*sub_p != '\0')
{
if (*str_p == *sub_p)
{
str_p++;
sub_p++;
}
else
{
break;
}
}
if (*sub_p == '\0')
{
return start;
}
start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配
}
return NULL;
}
') { if (*str_p == *sub_p) { str_p++; sub_p++; } else { break; } } if (*sub_p == '
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//sub_p指针遍历源字符串进行比较
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//sub_p遍历子串进行比较
while (*start != '\0')
{
str_p = start;
sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较
while (*str_p != '\0'&&*sub_p != '\0')
{
if (*str_p == *sub_p)
{
str_p++;
sub_p++;
}
else
{
break;
}
}
if (*sub_p == '\0')
{
return start;
}
start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配
}
return NULL;
}
') { return start; } start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配 } return NULL; }

模拟实现strstr函数

下面的也可以

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
		assert(str);
		assert(sub);
		const char*str_p = str;//str_p真正向后走
		const char*start = str_p;//start用来指向起始位置
		const char*sub_p = sub;
		while (*start)//外层循环只是决定了从什么时候开始
		{
			str_p = start;
			sub_p = sub;
			//内层循环才是真正比较
			while (*str_p&&*sub_p&&*str_p == *sub_p)
			{
				str_p++;
				sub_p++;
			}
			//只要两个字符不相等就停下来,或者有一个已经到达
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//str_p真正向后走
const char*start = str_p;//start用来指向起始位置
const char*sub_p = sub;
while (*start)//外层循环只是决定了从什么时候开始
{
str_p = start;
sub_p = sub;
//内层循环才是真正比较
while (*str_p&&*sub_p&&*str_p == *sub_p)
{
str_p++;
sub_p++;
}
//只要两个字符不相等就停下来,或者有一个已经到达\0就停下来
//*sub_p=='\0'说明比较成功了,这时候返回起始比较位置,而起始比较位置在start当中保存着
if (*sub_p == '\0')
{
return start;
}
start++;
}
return NULL;
}
int main()
{
char str[] = "abbbbcdef";
char *p ;
p = strstr(str, "bbc");
printf("%s", p);
system("pause");
return 0;
}
就停下来 //*sub_p=='
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//str_p真正向后走
const char*start = str_p;//start用来指向起始位置
const char*sub_p = sub;
while (*start)//外层循环只是决定了从什么时候开始
{
str_p = start;
sub_p = sub;
//内层循环才是真正比较
while (*str_p&&*sub_p&&*str_p == *sub_p)
{
str_p++;
sub_p++;
}
//只要两个字符不相等就停下来,或者有一个已经到达\0就停下来
//*sub_p=='\0'说明比较成功了,这时候返回起始比较位置,而起始比较位置在start当中保存着
if (*sub_p == '\0')
{
return start;
}
start++;
}
return NULL;
}
int main()
{
char str[] = "abbbbcdef";
char *p ;
p = strstr(str, "bbc");
printf("%s", p);
system("pause");
return 0;
}
'说明比较成功了,这时候返回起始比较位置,而起始比较位置在start当中保存着 if (*sub_p == '
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//str_p真正向后走
const char*start = str_p;//start用来指向起始位置
const char*sub_p = sub;
while (*start)//外层循环只是决定了从什么时候开始
{
str_p = start;
sub_p = sub;
//内层循环才是真正比较
while (*str_p&&*sub_p&&*str_p == *sub_p)
{
str_p++;
sub_p++;
}
//只要两个字符不相等就停下来,或者有一个已经到达\0就停下来
//*sub_p=='\0'说明比较成功了,这时候返回起始比较位置,而起始比较位置在start当中保存着
if (*sub_p == '\0')
{
return start;
}
start++;
}
return NULL;
}
int main()
{
char str[] = "abbbbcdef";
char *p ;
p = strstr(str, "bbc");
printf("%s", p);
system("pause");
return 0;
}
') { return start; } start++; } return NULL; } int main() { char str[] = "abbbbcdef"; char *p ; p = strstr(str, "bbc"); printf("%s", p); system("pause"); return 0; }

运行结果:

模拟实现strstr函数

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152983.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号