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

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

 


    昨天我们编写了简单的字符查找函数。虽然比较简单,但是也算能用。然而,经过我们仔细分析研究一下,这么一个简单的函数还是有改进的空间的。在什么地方改进呢?大家可以慢慢往下看。

    下面的代码是优化前的代码,现在再贴一次,这样分析起来也方便些:


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;
}     不知道朋友们发现没有,原来的while条件中有一个很费时的操作。那就是每次str移动的时候,都需要判断str的长度大小。如果str的长度远大于data的长度,那么计算str长度的时间是相当可观的。


int check_length_of_str(const char* str, int len) 

    int index; 
 
    for(index = 0; index < len; index ++){ 
        if('\0' == str[index]) 
            return 0; 
    } 
 
    return 1; 

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

    int index; 
    int len; 
 
    if(NULL == str || NULL == str) 
        return NULL; 
 
    len = strlen(data); 
    while(*str && check_length_of_str(str, len)){ 
        for(index = 0; index < len; index ++){ 
            if(str[index] != data[index]) 
                break; 
        } 
 
        if(index == len) 
            return (char*) str; 
 
        str++; 
    } 
 
    return NULL; 

int check_length_of_str(const char* str, int len)
{
 int index;

 for(index = 0; index < len; index ++){
  if('\0' == str[index])
   return 0;
 }

 return 1;
}

char* strstr(const char* str, char* data)
{
 int index;
 int len;

 if(NULL == str || NULL == str)
  return NULL;

 len = strlen(data);
 while(*str && check_length_of_str(str, len)){
  for(index = 0; index < len; index ++){
   if(str[index] != data[index])
    break;
  }

  if(index == len)
   return (char*) str;

  str++;
 }

 return NULL;
}    上面的代码很好地解决了长度判断的问题,这样一来每次比较的长度很短,只要判断len的大小字符长度即可。但是,我们还不是很满足,如果两者不比较岂不更好。那么,有没有这个可能?我们发现,如果str在每次比较不成功的时候,就会自己递增一位。那么我们只要判断这一位是不是‘\0’不就可以了吗?所以说,我们的代码还可以写成下面的形式。


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

    int index; 
    int len; 
 
    if(NULL == str || NULL == str) 
        return NULL; 
 
    len = strlen(data); 
    if((int)strlen(str) < len) 
        return NULL; 
 
    while(*str){ 
        for(index = 0; index < len; index ++){ 
            if(str[index] != data[index]) 
                break; 
        } 
 
        if(index == len) 
            return (char*) str; 
 
        if('\0' == str[len]) 
            break; 
 
        str++; 
    } 
 
    return NULL; 

char* strstr(const char* str, char* data)
{
 int index;
 int len;

 if(NULL == str || NULL == str)
  return NULL;

 len = strlen(data);
 if((int)strlen(str) < len)
  return NULL;

 while(*str){
  for(index = 0; index < len; index ++){
   if(str[index] != data[index])
    break;
  }

  if(index == len)
   return (char*) str;

  if('\0' == str[len])
   break;

  str++;
 }

 return NULL;
}    和上面第一次的优化不同,我们在进入while之前会判断两者的长度区别,但是经过第一次判断之后,我们就再也不用判断了,因为接下来我们只要判第n个元素是否为‘\0’即可,原来的n-1个元素我们已经判断过了,肯定是合法的元素。为什么呢?大家可以好好想想。

 


(二)、KMP算法

    KMP算法本质上说是为了消除查找中的多余查找步骤。怎么就产生了多余的查找步骤了呢。我们可以用示例说话。假设有下面两个字符串:

    A:  baaaaabcd

    B:  aaaab

    那么这两个查找的时候会发生什么现象呢?我们可以看一下:


/*      1 2 3 4 5 6 7 8 9
*    A: b a a a a a b c d
*    B:   a a a a b
*       1 2 3 4 5 6 7 8 9
*/   
/*      1 2 3 4 5 6 7 8 9
*    A: b a a a a a b c d
*    B:   a a a a b
*       1 2 3 4 5 6 7 8 9
*/      我们发现B和A在从第2个元素开始比较的时候,发现最后一个元素是不同的,A的第6个元素是a,而B的第5个元素是b。按照普通字符串查找的算法,那么下面A会继续向右移动一位,但是事实上2-5的字符我们都已经比较过了,而且2-5这4个元素正好和B的前4个元素对应。这个时候B应该用最后一位元素和A的第7位元素比较即可。如果这个计算步骤能省下,查找的速度不就能提高了吗?

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

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

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