频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
一步一步写算法(之字符串查找 上篇)
2011-11-02 08:19:00           
收藏   我要投稿

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

 

 

 

    字符串运算是我们开发软件的基本功,其中比较常用的功能有字符串长度的求解、字符串的比较、字符串的拷贝、字符串的upper等等。另外一个经常使用但是却被我们忽视的功能就是字符串的查找。word里面有字符串查找、notepad里面有字符串查找、winxp里面也有系统自带的字符串的查找,所以编写属于自己的字符串查找一方面可以提高自己的自信心,另外一方面在某些情况下可以提高软件的运行效率。下面我们就三个方面讨论一下字符串的查找方法:

 

    1)基本字符串查找

 

    2)KMP查找

 

    3)多核cpu下的字符串查找

 

   

 

    (一)、首先介绍一下普通的字符串查找方法:

 

    a)指针是否为空,否则返回

 

    b)判断str是否为‘\0’,判断剩下来的字符串长度是否>=模板字符串的长度,只有一个不符合,函数结束运行

 

    c)依次比较字符串和模板字符串的内容,如果全部符合,返回;只要一个不符合,break跳出,str加1,转b)

 

    那么算法应该怎么写呢?朋友们可以自己先书写一下,即使在纸上写也可以。

 

 

char* strstr(const char* str, char* data) 

    int index; 

    int len; 

 

    if(NULL == str || NULL == str) 

        return NULL; 

 

    len = strlen(data); 

    while(*str && (int)strlen(str) >= len){ 

        for(index = 0; index < len; index ++){ 

            if(str[index] != data[index]) 

                break; 

        } 

 

        if(index == len) 

            return (char*) str; 

 

        str++; 

    } 

 

    return NULL; 

char* strstr(const char* str, char* data)

{

       int index;

       int len;

 

       if(NULL == str || NULL == str)

              return NULL;

 

       len = strlen(data);

       while(*str && (int)strlen(str) >= len){

              for(index = 0; index < len; index ++){

                     if(str[index] != data[index])

                            break;

              }

 

              if(index == len)

                     return (char*) str;

 

              str++;

       }

 

       return NULL;

}

    为了说明代码的正确性,我们可以编写几个测试用例测试一下。

 

 

void test() 

    assert(NULL == strstr(NULL, "china")); 

    assert(NULL == strstr("hello, world", "china")); 

    assert(NULL != strstr("hello, china", "china")); 

void test()

{

       assert(NULL == strstr(NULL, "china"));

       assert(NULL == strstr("hello, world", "china"));

       assert(NULL != strstr("hello, china", "china"));

}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 上篇 字符串 算法
上一篇:一步一步写算法(之链表排序)
下一篇:一步一步写算法(之字符串查找 中篇)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站