Chinaunix

标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr() [打印本页]
作者: jxg945    时间: 2005-08-05 09:47
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
不使用已有的系统调用或函数库,实现c库的函数:strstr()
实现的原型为
char *my_strstr(char *haystack, char *needle);
返回needle字符串在haystack字符串第一次出现位置的指针，如果不存在
返回NULL。

哪个高手帮忙做一下呀。我做了1天了  都没有实现
作者: mq110    时间: 2005-08-05 09:50
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
啥也不让用.那就一点一点比吧.
作者: jxg945    时间: 2005-08-05 09:56
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
你写一下好吗？？我想看一下你怎么实现返回那2种指针
作者: jxg945    时间: 2005-08-05 12:06
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
有没有高手呀，这个真的很难吗？
我是这样写的 谁能告诉我错误在哪
作者: jxg945    时间: 2005-08-05 12:08
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
1 #include<stdio.h>;
      2 #include<unistd.h>;
      3
      4 char *my_strstr(char *dst, char *src)
      5 {
      6     char *a = dst;
      7     char *b = src;
      8 //  char *t;
      9     int i = 0;
     10
     11     while (*dst++ !='\0')
     12     {
     13         if(*dst == *src){
     14             a = dst;
     15         }
     16
     17         while ((*dst++) == (*src++))
     18         {
     19             if (*src == '\0')
     20             {
     21                 i = 1;
     22                 break;
     23             }
     24         }
     25
     26         if(i==1){
     27             break;
     28         }
     29
     30         src = b;
     31     }
     32
     33     if(i==1){
     34         return a;
     35     }else{
     36         return NULL;
     37     }
     38 }
     39
     40 main()
     41 {
     42     char *p;
     43     p = my_strstr("bcabchydacaa","abc";
     44     printf("%s\n",p);
     45 }
作者: luojiannx    时间: 2005-08-05 13:22
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
  1. #include<stdio.h>;
  2. #include<unistd.h>;

  4. char *my_strstr(char *dst, char *src)
  5. {
  6.         char *a = dst;
  7.         char *b = src;
  8.         //  char *t;
  9.         int i = 0;

  11.         do
  12.         {
  13.                 if(*dst == *src){
  14.                         a = dst;

  16.                         while ((*ds++t) == (*src++))
  17.                         {
  18.                                 if (*src == '\0')
  19.                                 {
  20.                                         return a;
  21.                                 }
  22.                         }

  24.                 }
  25.                 src = b;
  26.         }while (*++ds !='\0');

  28.         return NULL;
  29. }

  31. main()
  32. {
  33.         char *p;
  34.         char q[100]="abcddachytdacaab";
  35.         char *c="Hello, what's your name";
  36.         p = my_strstr(q,"abc");        
  37.         printf("[%s]\n%s\n",q,p);
  38.         p = my_strstr(c,"your");
  39.         printf("[%s]\n%s\n",c,p);
  40. }

复制代码


你的第一个if的结束的花括号地方放错了，应把第2个while循环包括进来，循环结构要改下，刚开始加加会有点小问题，第一个字母就比较不了了
作者: luojiannx    时间: 2005-08-05 13:40
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
另外，有了结果你可以直接返回啊，不用两个break了，累赘！！！
作者: hades666    时间: 2005-08-05 13:54
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
各位 我也写了一个 不过有些问题.
在return 之前printf出来可以
为什么
return 的时候是NULL的.
请高手们指点.
  1. #include <stdio.h>;
  2. #include <string.h>;

  4. int _strlen(char *str)
  5. {
  6.     int len=0;
  7.     while(*str++!='\0')
  8.         len++;
  9.     return len;
  10. }

  12. char *my_strstr(char *haystack, char *needle)
  13. {
  14.     char *ptr_h=haystack,*ptr_n=needle;
  15.     int len=_strlen(needle);
  16.     static char *save;

  18.     if(_strlen(haystack)<_strlen(needle))
  19.         return NULL;
  20.     while((*ptr_h++ == *ptr_n++) && --len>;0)
  21.     ;
  22.     if(len!=0)
  23.         my_strstr(ptr_h,needle);
  24.     else
  25.     {
  26.         printf("%s\n",haystack);
  27.         save=haystack;
  28.         return save;
  29.     }
  30.     return NULL;
  31. }

  33. int main()
  34. {
  35.     char *s1="abcde",*s2="cd";
  36.     printf("%s\n",my_strstr(s1,s2));
  37.     return 0;
  38. }
复制代码
作者: luojiannx    时间: 2005-08-05 14:03
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
这个还用递归？i 服了u了
作者: hades666    时间: 2005-08-05 14:06
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
递归看起来舒服,我不知道我错在哪了.
作者: luojiannx    时间: 2005-08-05 14:39
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
问题应该就出在递归调用的地方。等返回的时候，堆栈已经复原了，ebp已经变化，访问到了错误的位置
作者: hades666    时间: 2005-08-05 14:42
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
那我还想用递归,我应该怎么改呢?
作者: zhaozj0222    时间: 2005-08-05 15:16
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()

  2. char *my_strstr(char *str,char *sub_str)
  3. {
  4.         int i=0,j=0;
  5.         while(str[i]!='\0'&&sub_str[j]!='\0') {
  6.                 if(str[i]==sub_str[j]) {
  7.                         i++;
  8.                         j++;
  9.                 }
  10.                 else {
  11.                         i=i-j+1;
  12.                         j=0;
  13.                 }
  14.         }
  15.         if(sub_str[j]=='\0')
  16.                 return (char *)(str+i-j);
  17.         return NULL;
  18. }
复制代码

不知道行不行。。
作者: luojiannx    时间: 2005-08-05 15:34
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
上面我说错了，反汇编了一下，gcc用的eax传递的返回值，递归返回错误具体原因待查：）
作者: heijude    时间: 2005-08-05 16:10
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
我感觉判断长度的函数有些不合适，具体那不合适我也说不上来，等我去调试调试．
作者: 高峰    时间: 2005-08-05 17:10
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
真是固执！
作者: hades666    时间: 2005-08-05 17:36
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
我的千古密题.谁来帮我找到解决的办法啊.
作者: luojiannx    时间: 2005-08-05 18:49
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
我看了下汇编代码，疑似没什么问题（不知道eax在返回的中途有没有被改掉，偶功力低，可能看不透）    
C改成下面这个样子好像也没问题（不过没多大意义）
把各个参数的修饰符号换了很多种也没用，可能是我没找到合适的吧
另外我把递归去掉，立马可以返回正确的指针了
估计还是递归的机制的原因   
  1. #include <stdio.h>;
  2. #include <string.h>;
  3. static char *save;
  4. int _strlen(char *str)
  5. {
  6.    int len=0;
  7.    while(*str++!='\0')
  8.        len++;
  9.    return len;
  10. }


  13. char *my_strstr(char *haystack, char *needle)
  14. {
  15.    char *ptr_h=haystack,*ptr_n=needle;
  16.    int len=_strlen(needle);

  18.    if(_strlen(haystack)<_strlen(needle))
  19.        return NULL;
  20.    while((*ptr_h++ == *ptr_n++) && len-->;0)
  21.    ;
  22.    if(len!=0)
  23.    {
  24.        my_strstr(ptr_h,needle);
  25.    }
  26.    else
  27.    {
  28.                   printf("%p\n",haystack);
  29.            save=haystack;
  30.            return NULL;
  31.    }
  32.    return NULL;
  33. }

  35. int main()
  36. {       
  37.    char *s1="abcde",*s2="cd";
  38.    char *s3;
  39.    printf("%p\n",s1);
  40.    my_strstr(s1,s2);
  41.    printf("%s\n",save);
  42.    return 0;
  43. }
复制代码
作者: luojiannx    时间: 2005-08-05 19:10
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
最后一个return
作者: mq110    时间: 2005-08-05 19:29
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
  1. #include <stdio.h>;
  2. #include <string.h>;

  4. int _strlen(char *str)
  5. {
  6.     int len=0;
  7.     while(*str++!='\0')
  8.         len++;
  9.     return len;
  10. }

  12. char *my_strstr(char *haystack, char *needle)
  13. {
  14.     char *ptr_h=haystack,*ptr_n=needle;
  15.     int len=_strlen(needle);

  17.     if(_strlen(haystack)<len)
  18.         return NULL;
  19.     while((*ptr_h++ == *ptr_n++) && --len>;0 );
  20.     if(len==0)
  21.         return haystack;
  22.     return my_strstr(ptr_h,needle);
  23. }

  25. int main()
  26. {
  27.     char *s1="abcdeffffff",*s2="ef";
  28.     printf("%s\n",my_strstr(s1,s2));
  29.     return 0;
  30. }
复制代码

千古密题.
作者: mq110    时间: 2005-08-05 19:31
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
递归的最后一个调用 才应该是递归函数本身.
不应该是NULL.
作者: luojiannx    时间: 2005-08-05 19:36
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
呵呵，刚才才想到，被你贴了
这个真的有点隐秘
作者: mq110    时间: 2005-08-05 19:38
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "luojiannx" 发表：
呵呵，刚才才想到，被你贴了
这个真的有点隐秘


我也琢磨了好长时间  
作者: mq110    时间: 2005-08-05 19:42
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
>;>;  if(_strlen(haystack)<_strlen(needle))
改成  if(_strlen(haystack)<len)
少让计算机干点活吧.
作者: luojiannx    时间: 2005-08-05 19:51
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
害我今天一天上班心神不宁啊，靠，手上又没一本书(._.!)
作者: mq110    时间: 2005-08-05 19:52
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
[quote]原帖由 "luojiannx"]害我今天一天上班心神不宁啊，靠，手上又没一本书(._.!)[/quote 发表：


啊.大哥你不好好工作.竟看论坛调程序啊.你真行.
作者: luojiannx    时间: 2005-08-05 19:56
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
嘿嘿，当然是手上的活干完了，又没人在的时候来瞅瞅啦，抓到了肯定会扣奖金的
作者: luojiannx    时间: 2005-08-05 19:56
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
安全第一
作者: homesp    时间: 2005-08-05 21:23
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
我写了一个但是编译有两个warning，运行好像不对，大家帮看看：

  1. char * mystrstr(char *dst,char *src){
  2.         char *test=src;
  3.         int count=0;
  4.         if(dst==NULL||test==NULL)
  5.                 return NULL;
  6.         while(*dst!=NULL&&*test!=NULL){
  7.                 if(*dst!=*test){
  8.                         dst++;
  9.                         test=src;
  10.                         count=0; /*应该重置一下*/
  11.                 }
  12.                 if(*dst==*src){ /* 应该是if(*dst==*test) */
  13.                         dst++;
  14.                         test++;
  15.                         count++;
  16.                 }
  17.         }
  18.         if(*test=='\0')
  19.                 return (dst-count);
  20.         else
  21.                 return NULL;
  22. }
复制代码
作者: mq110    时间: 2005-08-05 21:29
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
>;>;while(*dst!=NULL&&*test!=NULL)
指针可以用NULL来判断.
你指针里的值不应该用 NULL来判断. 应该用'\0'或者直接ASC码0来判断.
作者: luojiannx    时间: 2005-08-05 21:34
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
  1. #include <stdio.h>;
  2. char * mystrstr(char *ds,char *src){
  3.        char *test=src;
  4.        char *dst=ds;
  5.        int count=0;
  6.        if(dst==NULL||test==NULL)
  7.                return NULL;
  8.        while(*dst!='\0'&&*test!='\0'){
  9.                if(*dst!=*test){
  10.                        dst++;
  11.                        test=src;
  12.                        count=0;
  13.                }
  14.                else{
  15.                        dst++;
  16.                        test++;
  17.                        count++;
  18.                }
  19.        }
  20.        if(*test=='\0')
  21.                return (dst-count);
  22.        else
  23.                return NULL;
  24. }
  25. main()
  26. {
  27.         char *p="what's your name";
  28.         //char *c="go home";
  29.         printf("%s\n",mystrstr(p,"your"));
  30. }
复制代码

没仔细优化，能工作我就没管了
作者: homesp    时间: 2005-08-05 21:35
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
改了好像还是不行
作者: luojiannx    时间: 2005-08-05 21:39
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
我的测试通过了啊
作者: homesp    时间: 2005-08-05 21:41
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
找到 错误了，粗心将src与test混了
作者: homesp    时间: 2005-08-05 21:42
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
[quote]原帖由 "luojiannx"]我的测试通过了啊[/quote 发表：

你把我while循环里的第二个if用else代替了，就是那判断语句里的问题
作者: luojiannx    时间: 2005-08-05 21:45
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
count你也没重新清0呢
作者: homesp    时间: 2005-08-05 21:47
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
[quote]原帖由 "luojiannx"]count你也没重新清0呢[/quote 发表：


恩，是的，哎，我太粗心了
作者: zlrll    时间: 2005-08-06 07:24
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
模式匹配的问题，有个经典的KMP算法
作者: m12_leon    时间: 2005-08-06 08:08
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
[quote]原帖由 "zlrll"]模式匹配的问题，有个经典的KMP算法[/quote 发表：

对
作者: hades666    时间: 2005-08-06 08:27
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
多谢mq110
作者: kukucm    时间: 2005-08-07 20:33
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
这个函数只有一个一个的比，没有什么好的办法。
作者: zhaozj0222    时间: 2005-08-08 09:39
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "hades666" 发表：

#include <stdio.h>;
#include <string.h>;

int _strlen(char *str)
{
   int len=0;
   while(*str++!='\0')
       len++;
   return len;
}

char *my_strstr(char *haystack, char *needle)
{
   char *ptr_h=haystack,*ptr_n=needle;
   int len=_strlen(needle);

   if(_strlen(haystack)<len)
       return NULL;
   while((*ptr_h++ == *ptr_n++) && --len>;0 );
   if(len==0)
       return haystack;
   return my_strstr(ptr_h,needle);
}

int main()
{
   char *s1="abcdeffffff",*s2="ef";
   printf("%s\n",my_strstr(s1,s2));
   return 0;
}

代码是有问题的，达不到 strstr的功能。
如果将
char *s1="abcdeffffff",*s2="ef";
换成
char *s1="aaaf",*s2="aaf";
看看是什么结果？
作者: mq110    时间: 2005-08-08 09:52
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
这个代码不是我写的.

他只是问了递归的问题.我帮他看了看.
作者: havey    时间: 2005-08-08 12:24
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
//这段代码有没有问题，这样编码规范吗？
//多多指教,谢谢！

#include <stdio.h>;
#include <string.h>;

char* GetSubStr(const char* instr, char* outstr);
int   CompSubStr(char* instr, char* str);

char* GetSubStr(const char* instr, char* outstr)
{
    char *ptr, *optr;

    if ((NULL == instr) || (strlen(outstr)>;strlen(instr)))
         return NULL;

    if (NULL == outstr)
         return (char*)instr;

    ptr = (char*)instr;
    optr = outstr;

    while (*ptr++ != '\0') {
         if (*ptr == *optr) { //find first char.
            if (1 == CompSubStr(ptr, optr))
                return ptr;
         }
    }

    return NULL;
}


int CompSubStr(char* instr, char* str)
{
    char *ptr, *optr;

    if (strlen(str) >; strlen(instr))
        return 0;

    ptr = instr;
    optr = str;

    while (*optr != '\0') { //compare substring.
        if (*ptr == *optr++)
              ptr++;
        else
              return 0;
    }

    return 1;
}

int main()
{
    const char *p1="myteststr";
    char *p2="testj";

    printf("The substring is ==========>; :%s\n", GetSubStr(p1, p2));

    return 0;
}
作者: luojiannx    时间: 2005-08-08 12:44
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
这么多人喜欢重复发明轮子啊
作者: kukucm    时间: 2005-08-08 19:35
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
其实这个函数只能比，大家写的都差不多。
作者: fsilence    时间: 2005-08-08 20:37
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()

  2. #include <stdio.h>;
  3. #include <string.h>;

  5. int _strlen(char *str)
  6. {
  7.   int len=0;
  8.   while(*str++!='\0')
  9.       len++;
  10.   return len;
  11. }

  13. char *my_strstr(char *haystack, char *needle)
  14. {
  15.   char *ptr_h=haystack,*ptr_n=needle;
  16.   int len=_strlen(needle);

  18.   if(_strlen(haystack)<len)
  19.       return NULL;
  20.   while((*ptr_h++ == *ptr_n++) && --len>;0 );
  21.   if(len==0)
  22.       return haystack;
  23.   return my_strstr(ptr_h,needle);
  24. }

  26. int main()
  27. {
  28.   char *s1="abcdeffffff",*s2="ef";
  29.   printf("%s\n",my_strstr(s1,s2));
  30.   return 0;
  31. }
复制代码

这段代码的确还有问题，
while((*ptr_h++ == *ptr_n++) && --len>;0 );
在第一次(*ptr_h++ == *ptr_n++)时 ，如果ptr_n开头的子串和ptr_h开头的子串到后面并不匹配，但这时ptr_h已经往前走了几个位置，下一次比较时不是从第一次ptr_h==ptr_n时ptr_h的后一个字节开始重新比较的。[/code]
作者: mq110    时间: 2005-08-08 20:47
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
楼上说的 是这个问题的关键..
作者: mik    时间: 2005-08-09 07:41
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
实现strstr()有很多方法; 看看我的实现:

(1)代码中虽然使用了goto, 但考虑到整体的整洁,并且保持高效。这是值得的。
（2）返回0表示找不到，返回具体值，代表位置。

int __strstr(const char *s, const char *d) {
             int ret = 0;
             int i = 0, j = 0;

c1:   
            if (*(d+i) == *(s+j))
            {
                         i++; j++;
                         if (*(d+i) == '\0') {
                                    ret++;
                                    goto exit1;
                         }
                         goto c1;

            } else {

                        i = 0;
                        ret++;
                        j = ret;
                        if (*(s+j) == '\0') {
                                       ret = 0;
                                       goto exit1;
                        }
                        
                        goto c1;
            }

exit1:
            return ret;

}


测试：
main() {
      printf("\"cd\" in \"acbcdef\" at %d\n", __strstr("acbcdef", "cd");
      printf("\"cc\" in  \"acbcdef\" at %d\n", __strstr("acbcdef", "cc");
}

结果：
"cd" in "acbcdef" at 4
"cc" in "acbcdef" at 0
作者: mq110    时间: 2005-08-09 07:44
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
楼上的这个程序 用while循环 continue break 同样能实现。为啥要用goto..
作者: 虚无此人    时间: 2005-08-09 11:20
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
你的递归有两处错误:
1.my_strstr(++haystack,needle); 前面要加一个return.否则不管如何都会return 一个NULL值.
2.递归应写成my_strstr(++haystack,needle); 具体原因自己去想想
作者: shucx    时间: 2005-08-09 12:42
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
/*
        cc -Wall -o strstr strstr.c
        Env:FreeBSD 5.4,gcc3.2.1
*/
#include <stdio.h>;
#include <string.h>;
#include <stdlib.h>;

char * MyStrstr(char *src,char *dest)
{
        char *cp=src;
        char *s1,*s2;

        if(!*dest)
        {
                return(src);
        }

        while(*cp)
        {
                s1=cp;
                s2=dest;

                while(*s1&&*s2&&!(*s1-*s2))
                {
                        s1++;
                        s2++;
                }
                if(!*s2)
                {
                        return (cp);
                }
                cp++;
        }
       
        return (NULL);
}

int main(int argc,char **argv)
{
        char *s;
       
        if(argc!=3)
        {
                printf("Usage:%s [src] [dest]\n",argv[0]);
                exit(1);
        }
       
        s=MyStrstr(argv[1],argv[2]);
        printf("%s\n",s);       
       
        return (0);
}
作者: jxg945    时间: 2005-08-09 16:41
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "luojiannx" 发表：

你的第一个if的结束的花括号地方放错了，应把第2个while循环包括进来，循环结构要改下，刚开始加加会有点小问题，第一个字母就比较不了了



谢谢您  您的do while 思想真不错  但是 如果main待参数调用会有bug
int main(int argc,char *argv[])
{   
     char *p;
     p = my_strstr(argv[1],argv[2]);
     printf("%s\n",p);

}

$ ./a.out backackabc abc执行
或者./a.out backackabc abcd执行
您看看
作者: jxg945    时间: 2005-08-09 17:05
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
看到大家的评论真是受益非浅，感谢风云等对我的指点  我自己把我的代码完成拉

      1 #include<stdio.h>;
      2 #include<unistd.h>;
      3 #include<stdlib.h>;
      4
      5 char *my_strstr(char *dst, char *src)
      6 {
      7     char *a = NULL;
      8     char *b = src;
      9     int i = 0;
     10     while (1)
     11     {
     12         if(*dst == *src){
     13             a = dst;
     14         }
     15
     16         while ((*dst) == (*src))
     17         {
     18             dst++;
     19             src++;
     20             if (*src == '\0')
     21             {
     22                 return a;
     23             }
     24
     25             if (*dst == '\0')
     26             {
     27                 return NULL;
     28             }
     29
     30         }
     31
     32         src = b;
     33         dst++;
     34         if(*dst == '\0'){
     35             return NULL;
     36         }
     37     }
     38
     39
     40 }
     41
     42 int main(int argc, char *argv[])
     43 {
     44     char *p;
     45     if (argc != 3)
     46     {
     47         printf("input argument error\n";
     48         exit(1);
     49     }
     50     p = my_strstr(argv[1],argv[2]);
     51     printf("%s\n",p);
     52 }
作者: mik    时间: 2005-08-09 19:21
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
[quote]原帖由 "mq110"]楼上的这个程序 用while循环 continue break 同样能实现。为啥要用goto..[/quote 发表：



没看我的第一点说明吗? 我当然知道可以用while, 我考虑过，但为了简洁与高效。
你用while来写一个，切磋切磋
作者: mq110    时间: 2005-08-09 19:42
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "mik" 发表：



没看我的第一点说明吗? 我当然知道可以用while, 我考虑过，但为了简洁与高效。
你用while来写一个，切磋切磋

  1. #include <stdio.h>;
  2. int __strstr(const char *s, const char *d) {
  3.     int ret = 0;
  4.     int i = 0, j = 0;

  6.     while(1)
  7.     {
  8.         if (*(d+i) == *(s+j))
  9.         {
  10.             i++; j++;
  11.             if (*(d+i) == '\0') {
  12.                 ret++;
  13.                 break;
  14.             }

  16.         } else {

  18.             i = 0;
  19.             ret++;
  20.             j = ret;
  21.             if (*(s+j) == '\0') {
  22.                 ret = 0;
  23.                 break;
  24.             }
  25.         }
  26.     }
  27.     return ret;

  29. }

  31. int main() {
  32.     printf("\"cd\" in \"acbcdef\" at %d\n", __strstr("acbcdef", "cd"));
  33.     printf("\"cc\" in  \"acbcdef\" at %d\n", __strstr("acbcdef", "cc"));
  34.     return 0;
  35. }
复制代码



我改了你那个goto的. 没看到效果有什么不一样啊.
作者: mq110    时间: 2005-08-09 19:47
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
还有 你的程序不符合 strstr的函数原形
char *strstr(const char *haystack, const char *needle);

既然能用while 改. 我想你也不必再用goto.
作者: mq110    时间: 2005-08-09 19:56
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
>;>;没看我的第一点说明吗? 我当然知道可以用while, 我考虑过，但为了简洁与高效。

我看了你第一点说明了.  而且还是仔细的看了.

没发现比while 高效到哪? 所以我才告诉你可以用while改的.

请指教.
作者: luojiannx    时间: 2005-08-09 21:51
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "jxg945" 发表：
   

$ ./a.out backackabc abc执行
或者./a.out backackabc abcd执行
您看看

可以的,我仔细测试过了
代码就是改改你的,所以我没做什么大改动
估计是我代码没贴好,上面有个字母t不知道怎么就乱了或者不看见了
  1. #include<stdio.h>;
  2. #include<unistd.h>;
  3. char *my_strstr(char *dst, char *src)
  4. {
  5.     char *a = dst;
  6.     char *b = src;
  7.     do {
  8.         if (*dst == *src) {
  9.             a = dst;
  10.             while ((*dst++) == (*src++)) {
  11.                 if (*src == '\0') {
  12.                     return a;
  13.                 }
  14.             }
  15.         }
  16.         src = b;
  17.     } while (*++dst != '\0');
  18.     return NULL;
  19. }
  20. int main(int argc, char **argv)
  21. {
  22.     char *p;
  23.     char q[100] = "abcddachytdacaab";
  24.     char *c = "Hello, what's your name";
  25.     p = my_strstr(q, "abc");
  26.     printf("[%s]\n%s\n", q, p);
  27.     p = my_strstr(c, "your");
  28.     printf("[%s]\n%s\n", c, p);
  29.     if (argc == 3) {
  30.         p = my_strstr(argv[1], argv[2]);
  31.         printf("[%s]\n", p);
  32.     }
  33. }
复制代码
作者: tena    时间: 2005-08-12 16:22
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
俺写的：

char *my_strstr(char *initStr,char *seekStr)
{
        int i=0;
       
        while(*initStr)
        {
                if((*initStr)!=(*seekStr))
                {
                        initStr++;
                        continue;
                }
                i=0;
                while((*(initStr+i))&&(*(seekStr+i)))
                {
                        if(!(*(seekStr+i+1)))
                                return initStr;
                        if(*(initStr+i)!=*(seekStr+i))
                                break;
                        i++;
                }
                initStr++;
        }
        if(!(*initStr))
                return  NULL;
}

void main(int argc,char **argv)
{
        char *str;
        if(argc<3)  return;       
        str=my_strstr(argv[1],argv[2]);
        printf("sub string:%s\n",str);
        return;
}
作者: mik    时间: 2005-08-12 21:21
标题: 不使用已有的系统调用或函数库,实现c库的函数:strstr()
原帖由 "mq110" 发表：
还有 你的程序不符合 strstr的函数原形
char *strstr(const char *haystack, const char *needle);

既然能用while 改. 我想你也不必再用goto.



当时感觉用while(1)循环, 可能会每次循环做一次判断.
     而且,用goto感觉好点,简洁些.是根据算法而想的.
如果原型改为 char *(const char* s, const char *d); 就更容易实现了.

char * __strstr(const char *s, const char *d)
{
         int ret = 0;
         int i = 0, j = 0;

loop:

         if (*(d+i) == *(s+j)) {
                   i++;  j++;
                   if (*(d+i) == '\0')
                            return s + ret;
                   goto loop;

         } else {
                  i = 0;
                  ret++;   j = ret;
                  if (*(s+j) == '\0')
                         return 0;
                  goto loop;
         }
}
作者: slwrq    时间: 2006-03-24 16:21
标题: 贴一段linux 内部实现
char * strstr(const char * s1,const char * s2)
{
       int l1, l2;

       l2 = strlen(s2);
       if (!l2)
               return (char *) s1;
       l1 = strlen(s1);
       while (l1 >= l2) {
               l1--;
               if (!memcmp(s1,s2,l2))
                       return (char *) s1;
               s1++;
       }
       return NULL;
}
作者: xiaofeng_jia    时间: 2006-03-24 17:16
抽空写了一个

/* filename my_strstr.c */

#include <unistd.h>
#include <stdio.h>
#include <assert.h>


char *my_strstr(const char *string, const char *string_set)
{
        assert(NULL != string);
        assert(NULL != string_set);
       
        char *str_src= (char *)string;
        char *str_set = (char *)string_set;
        char *str_rut = NULL;
       
        while ( '\0' != *str_src ) {
                str_rut = str_src;
                for ( ; *str_src++ == *str_set; ) {
                        str_set++;
                        if ( '\0' == *str_set ) {
                                return str_rut;
                        }
                }
        }
       
        return NULL;
}

int main(void)
{
        char *str_tmp = NULL;
        char string_1[]="453gh3u";
        char *string_2="What's your name";

        str_tmp = my_strstr(string_1, "abc");
        printf("[%s]\n%s\n",string_1, str_tmp);

        str_tmp = my_strstr(string_2, "your");
        printf("[%s]\n%s\n", string_2, str_tmp);
       
        return 0;
}
作者: oyjcq    时间: 2006-03-24 17:24
http://www.cublog.cn/u/1807/?u=h ... howart.php?id=89570
这个合适吧， 返回的地方改下就好了
作者: emacsnw    时间: 2006-03-29 00:24
简单看了一把，全是naive的O(m*n)算法。KMP不是可以O(m+n)吗？
作者: luojiannx    时间: 2007-09-01 00:38
想想,确实可以做到更有效率点
比较第一个字符相同后,直接比较搜索字符串的最后一个字符（指针都+strlen（dest))
如果最后一个字符相同还是逐个比较
如果不同再从刚才加的长度+1处开始比较
O(m+n)是这样的么？这个如果理想情况下，效率比m+n还好呢，（m/n)+n

如果像62楼所说的
那么linux内核“也不是处处考虑周到（起码在效率方面,这个应该不要考虑可读性吧）



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2