模拟实现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 != '\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 ?”这里,按照上面所举的例子,对应的逻辑,我们已经遍历到了字串的\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 != '\0'&&*sub != '\0')
	{
		
		if (*str == *sub)
		{
			str++;
			sub++;
		}
		else
		{
			str++;
			start = str;
		}
	}
	if (*sub == '\0')
	{
		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 != '\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;
}

结果:

模拟实现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 != '\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;
}

模拟实现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++;
			}
			//只要两个字符不相等就停下来,或者有一个已经到达\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;
}

运行结果:

模拟实现strstr函数

 

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

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

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

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

(0)


相关推荐

  • python导入excel数据画散点图_excel折线图怎么做一条线

    python导入excel数据画散点图_excel折线图怎么做一条线目的:读取excel文件中的数据,绘制折线图、散点图安装环境:由于我使用的是Anaconda集成的环境所以不用安装模块,直接导入就行importpandasaspdimportmatplotlib.pyplotasplt绘制简单折线pandas操作Excel表单数据准备,有一个Excel文件:lemon.xlsx有两个表单,表单名分别为:Python以及student,Python的表单数据如下所示:student的表单数据如下所示:…

  • BlueZ_bluebonnet

    BlueZ_bluebonnet一、BlueZ在ubuntuPC上的基础应用1、bluez的安装及基本功能dong@ubuntu:~/bluez$lsbluez-5.47.tar.xzSPP-loopback.pydong@ubuntu:~/bluez$tarxvfbluez-5.47.tar.xzdong@ubuntu:~/bluez/bluez-5.47$./configure–pr…

    2022年10月22日
  • JS 暂时性死区

    JS 暂时性死区JS暂时性死区ES6暂时性死区引用ES6暂时性死区只要块级作用域内存在let命令,它所声明的变量就“绑定”(binding)这个区域,不再受外部的影响。vartmp=123;if(true){tmp=’abc’;//ReferenceErrorlettmp;}上面代码中,存在全局变量tmp,但是块级作用域内let又声明了一个局部变量tmp,导致后…

  • 函数去抖(debounce)& 函数节流(throttle)总结

    函数去抖(debounce)& 函数节流(throttle)总结//todo

  • <Win32_15>用纯C语言来实现WP8中磁贴动态翻转的功能「建议收藏」

    今年年初入手了一部诺基亚新款WP8手机——Lumia620经典蓝,用起来感觉很不错,很流畅、界面很清新到现在,用了大概有大半年时间了,一直很好奇WP8中磁贴动态翻转的实现算法——使用过WP8手机的朋友都知道,这个功能很有3D的效果,看起来感觉很不错但是,它到底是如何实现的呢? 今儿,我就来和大家一起剖析一下它的实现细节WP8中磁贴动态翻转功能细节:(1)将当

  • 通过PropertyDescriptor反映射调用set和get方法

    通过PropertyDescriptor反映射调用set和get方法1packagecom.zhoushun;importjava.lang.reflect.Method;importjava.lang.reflect.Field;importjava.beans.PropertyDescriptor;publicclassPropertyUtil{ @SuppressWarnings(“unchecked”) publicsta

发表回复

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

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