程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 一步一步寫算法(之字符串查找 中篇)

一步一步寫算法(之字符串查找 中篇)

編輯:關於C

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱: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位元素比較即可。如果這個計算步驟能省下,查找的速度不就能提高了嗎?

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved