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

一步一步寫算法(之查找)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    無論是數據庫,還是普通的ERP系統,查找功能數據處理的一個基本功能。數據查找並不復雜,但是如何實現數據又快又好地查找呢?前人在實踐中積累的一些方法,值得我們好好學些一下。我們假定查找的數據唯一存在,數組中沒有重復的數據存在。

 

    (1) 普通的數據查找

 

    設想有一個1M的數據,我們如何在裡面找到我們想要的那個數據。此時數據本身沒有特征,所以我們需要的那個數據可能出現在數組的各個位置,可能在數據的開頭位置,也可能在數據的結束位置。這種性質要求我們必須對數據進行遍歷之後才能獲取到對應的數據。

 

 

view plaincopy to clipboardprint?int find(int array[], int  length, int value) 

    if(NULL == array || 0 == length) 

        return -1; 

 

    for(int index = 0; index < length; index++){ 

        if(value == array[index]) 

            return index; 

        } 

    return -1; 

int find(int array[], int  length, int value)

{

       if(NULL == array || 0 == length)

              return -1;

 

       for(int index = 0; index < length; index++){

              if(value == array[index])

                     return index;

        }

       return -1;

}分析:

 

    由於我們不清楚這個數據判斷究竟需要多少次。但是,我們知道,這樣一個數據查找最少需要1次,那麼最多需要n次,平均下來可以看成是(1+n)/2,差不多是n的一半。我們把這種比較次數和n成正比的算法復雜度記為o(n)。

 

    

 

    (2)上面的數據沒有任何特征,這導致我們的數據排列地雜亂無章。試想一下,如果數據排列地非常整齊,那結果會是什麼樣的呢?就像在生活中,如果平時不注意收拾整齊,那麼找東西的時候非常麻煩,效率很低;但是一旦東西放的位置固定下來,所有東西都歸類放好,那麼結果就不一樣了,我們就會形成思維定勢,這樣查找東西的效率就會非常高。那麼,對一個有序的數組,我們應該怎麼查找呢?二分法就是最好的方法。

 

 

view plaincopy to clipboardprint?int binary_sort(int array[], int length, int value) 

    if(NULL == array || 0 == length) 

        return -1; 

 

    int start = 0; 

    int end = length -1; 

 

    while(start <= end){ 

         

        int middle = start + ((end - start) >> 1); 

        if(value == array[middle]) 

            return middle; 

        else if(value > array[middle]){ 

            start = middle + 1; 

        }else{ 

            end = middle -1; 

        } 

    } 

 

    return -1; 

int binary_sort(int array[], int length, int value)

{

       if(NULL == array || 0 == length)

              return -1;

 

       int start = 0;

       int end = length -1;

 

       while(start <= end){

             

              int middle = start + ((end - start) >> 1);

              if(value == array[middle])

                     return middle;

              else if(value > array[middle]){

                     start = middle + 1;

              }else{

                     end = middle -1;

              }

       }

 

       return -1;

}分析:

 

    上面我們說到普通的數據查找算法復雜度是o(n)。那麼我們可以用上面一樣的方法判斷一下算法復雜度。這種方法最少是1次,那麼最多需要多少次呢?我們發現最多需要log(n+1)/log(2)即可。大家可以找個例子自己算一下,比如說7個數據,我們發現最多3次;如果是15個數據呢,那麼最多4次;以此類推,詳細的論證方法可以在《算法導論》、《計算機編程藝術》中找到。明顯,這種數據查找的效率要比前面的查找方法高很多。

 

 

 

 

    (3) 上面的查找是建立在連續內存基礎之上的,那麼如果是指針類型的數據呢?怎麼辦呢?那麼就需要引入排序二叉樹了。排序二叉樹的定義很簡單:(1)非葉子節點至少一遍分支非NULL;(2)葉子節點左右分支都為NULL;(3)每一個節點記錄一個數據,同時左分支的數據都小於右分支的數據。可以看看下面的定義:

 

 

view plaincopy to clipboardprint?typedef struct _NODE 

    int data; 

    struct _NODE* left; 

    struct _NODE* right; 

}NODE; 

typedef struct _NODE

{

       int data;

       struct _NODE* left;

       struct _NODE* right;

}NODE;    那麼查找呢,那就更簡單了。

 

 

view plaincopy to clipboardprint?const NODE* find_data(const NODE* pNode, int data){ 

    if(NULL == pNode) 

        return NULL; 

 

    if(data == pNode->data) 

        return pNode; 

    else if(data < pNode->data) 

        return find_data(pNode->left, data); 

    else 

        return find_data(pNode->right, data);         

const NODE* find_data(const NODE* pNode, int data){

       if(NULL == pNode)

              return NULL;

 

       if(data == pNode->data)

              return pNode;

       else if(data < pNode->data)

              return find_data(pNode->left, data);

       else

              return find_data(pNode->right, data);         

}

    (4)同樣,我們看到(2)、(3)都是建立在完全排序的基礎之上,那麼有沒有建立在折中基礎之上的查找呢?有,那就是哈希表。哈希表的定義如下:1)每個數據按照某種聚類運算歸到某一大類,然後所有數據鏈成一個鏈表;2)所有鏈表的頭指針形成一個指針數組。這種方法因為不需要完整排序,所以在處理中等規模數據的時候很有效。其中節點的定義如下:

 

 

view plaincopy to clipboardprint?typedef struct _LINK_NODE 

    int data; 

    struct _LINK_NODE* next; 

}LINK_NODE; 

typedef struct _LINK_NODE

{

       int data;

       struct _LINK_NODE* next;

}LINK_NODE;

 

    那麼hash表下面的數據怎麼查找呢?

 

 

view plaincopy to clipboardprint?LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data) 

    int index = data % mod; 

    if(NULL == array[index]) 

        return NULL; 

 

    LINK_NODE* pLinkNode = array[index]; 

    while(pLinkNode){ 

        if(data == pLinkNode->data) 

            return pLinkNode; 

        pLinkNode = pLinkNode->next; 

    } 

 

    return pLinkNode; 

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)

{

       int index = data % mod;

       if(NULL == array[index])

              return NULL;

 

       LINK_NODE* pLinkNode = array[index];

       while(pLinkNode){

              if(data == pLinkNode->data)

                     return pLinkNode;

              pLinkNode = pLinkNode->next;

       }

 

       return pLinkNode;

}分析:

 

 

    hash表因為不需要排序,只進行簡單的歸類,在數據查找的時候特別方便。查找時間的大小取決於mod的大小。mod越小,那麼hash查找就越接近於普通查找;那麼hash越大呢,那麼hash一次查找成功的概率就大大增加。

 

 

 

【預告: 下一篇博客介紹排序的內容】

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