模拟实现strstr函数

ゝ一纸荒年。 2022-08-21 07:52 234阅读 0赞

# strstr函数。 #

char \*strstr(const char \*str1, const char \*str2)

这个函数的作用为查找字符串 str1中是否含有字符串str2，两种情况，有或没有，大家注意，在 ‘有’ 这个情况中还有一种特别的情况。这个下面再谈。

大致思路很简单：建立两个指针，分别指向str1和str2进行遍历，并一一比较。

例如这两个字符串：

str1          abcdefg

str2          cde

建立两个指针：   char \*str=str1;

char \*strtub=str2;

此时 str指向a，strtub指向c。

对\*str与\*strtub进行比较。若两个相等，两个都向后移动一位，若不相等，strtub不动，str向后移动一位，再次进行比较。

从上可知，我们需要建立一个循环来保证比较可以持续进行。

那么，循环的判断条件或者说结束条件是什么呢？

我们想一下，这是字符串的比较，字符串的特点是最后都有一个‘\\0’。

我们来列举一下：

1、  当\*str='\\0' 的时候说明已经比较到了最后，仍然没有找到子串strtub，即str1中没有str2；

2、  当\*strtub=‘\\0’的时候，说明已经找了子串，并且已经比较完毕。即str1中含有str2；

所以进入循环的条件为，\*str!=‘\\0’,\*strtub!='\\0',并且\*str==\*strtub；

<pre name="code" class="cpp">  while(*str)
          {
        while(*str&&*strtub&&*str==*strtub)
           {
             str++;
             strtub++;
          }
         if(*strtub=='\0')
           {
              return (*****);//这个返回值我先不写，请继续往下看。
           }

strtub=str2；

}

这个代码只是针对上面讲的比较，还不够完善， 大家不要被误导，缺少一种情况，就是我在文章开头提到的特殊情况。

所谓的特殊情况

下面我们来举个例子：

str1         abbbcd

str2         bbc

同上，我们仍然建立两个指针str，strtub分别指向str1，str2。

当str指向第一个b的时候，str=strtub，strtub开始向后移动，当str指向第三个b的时候，strtub指向的是c，str!=strtub，此时strtub应付返回开头（strtub=str2）。

注意：

此时两个指针的状态，\*str指向的是第三个b，\*strtub指向str开头。

当再次进行比较，str继续向后移动，我们会发现，在“abbbcd”中我们永远也无法找到“bbc”。这就是我所说的特殊情况。

处理办法：

当出现str!=strtub的时候，让strtub返回开头的同时，应该让str向前返回到str开始位置的下一个位置，再接着进行比较。

实现办法：

在进入第一个循环时建立一个指针保存一下str。char \*start=str；

让str向前返回到str开始位置的下一个位置。令str=start+1；

所以完善后的代码应为

while(*str)
          {
         char *start=str
         while(*str&&*strtub&&*str==*strtub)
           {
             str++;
             strtub++;
          }
         if(*strtub=='\0')
           {
              return start;//这里返回值补上，让它返回str的起始位置
           }
         str=start+1;
         strtub=str2;
      }

完整的代码：

//模拟实现strstr 
    #include<stdio.h>
    #include<assert.h>//assert函数的头文件
     char* my_strstr(const char *str1,const char *str2)
      {
         
      	  assert(sub!=NULL);//用assert进行断言
              assert(substr!=NULL);
      	  const char* str=str1;//学会用const保护，无论是参数或者变量。
              const char* strtub=str2;
              const char *start=NULL;//start最好定义在循环外，上面我只是为了让大家看的更明白。
      	  while(*str)
      	  {
      	  	 start=str;//用start保存str
      	  	 while(*str&&*strtub&&*str==*strtub)
      	  	   {
      	  	           str++;
      	  	           strtub++;
    			}
    		 if(*strtub=='\0')
    		  {
    	   return (char*)start;
    		 
    		  }
    	   str=start+1;
    	   strtub=str2;
    		
          }
       return NULL;//若没找到则返回空
      }
     int main()
      {
       	char arr1[]="abbbcdef";
      	char arr2[]="bbc";
      	
      	if(my_strstr(arr1,arr2)!=NULL)//当返回值不为空的时候，说明找到了子串
      	  {
      	  	printf("yes");
    	  }
        else 
        {
         printf("NO");
       }
      	return 0;
       }