程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 索引查找（索引查找、分塊查找） C語言實現

索引查找（索引查找、分塊查找） C語言實現

編輯：關於C

1、基本概念

索引查找又稱分級查找。

索引存儲的基本思想是：首先把一個集合或線性表（他們對應為主表）按照一定的函數關系或條件劃分成若干個邏輯上的子表，為每個子表分別建立一個索引項，由所有

這些索引項構成主表的一個索引表，然後，可采用順序或鏈接的方式來存儲索引表和每個子表。

索引表的類型可定義如下：

struct IndexItem
{
    IndexKeyType index;//IndexKeyType為事先定義的索引值類型
    int start;         //子表中第一個元素所在的下標位置
    int length;        //子表的長度域
};
typedef struct IndexItem indexlist[ILMSize];//ILMSize為事先定義的整型常量，大於等於索引項數m

主表的類型可定義如下：

typedef struct ElemType mainlist[MaxSize];//MaxSize為事先定義的整型常量，大於等於主表中元素的個數n

在索引表中的每個索引項對應多條記錄，則稱為稀疏索引，若每個索引項唯一對應一條記錄，則稱為稠密索引。

2、索引查找算法

過程：

首先根據給定的索引值K1，在索引表上查找出索引值等於K1的索引項，以確定對應子表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，在對應的子表中查找出

關鍵字等於K2的元素。

設數組A是具有mainlist類型的一個主表，數組B是具有indexlist類型的在主表A上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，K1和K2分別為給定

帶查找的索引值和關鍵字，並假定每個子表采用順序存儲，則索引查找算法為：

int Indsch(mainlist A, indexlist B, int m, IndexKeyType K1, KeyType K2)
{//利用主表A和大小為 m 的索引表B索引查找索引值為K1，關鍵字為K2的記錄
 //返回該記錄在主表中的下標位置，若查找失敗則返回-1
    int i, j;
    for (i = 0; i < m; i++)
        if (K1 == B[i].index)
            break;
    if (i == m)
        return -1; //查找失敗
    j = B[i].start;
    while (j < B[i].start + B[i].length)
    {
        if (K2 == A[j].key)
            break;
        else
            j++;
    }
    if (j < B[i].start + B[i].length)
        return j; //查找成功
    else
        return -1; //查找失敗
}
若 IndexKeyType 被定義為字符串類型，則算法中相應的條件改為

 strcmp (K1, B[i].index) == 0;

同理，若KeyType 被定義為字符串類型
則算法中相應的條件也應該改為

strcmp (K2, A[j].key) == 0

若每個子表在主表A中采用的是鏈接存儲，則只要把上面算法中的while循環
和其後的if語句進行如下修改即可：

while (j != -1)//用-1作為空指針標記
{
    if (K2 == A[j].key)
        break;
    else
        j = A[j].next;
}
return j;

若索引表B為稠密索引，則更為簡單，只需查找索引表B，成功時直接返回B[i].start即可。

索引查找分析：

索引查找的比較次數等於算法中查找索引表的比較次數和查找相應子表的比較次數之和，假定索引表的長度為m，子表長度為s，

則索引查找的平均查找長度為：

ASL= (1+m)/2 + (1+s)/2 = 1 + (m+s)/2

假定每個子表具有相同的長度，即s=n/m, 則 ASL = 1 + (m + n/m)/2 ,當m = n/m ,(即m = √▔n，此時s也等於√▔n), ASL = 1 + √▔n 最小，時間復雜度為 O(√▔n)

可見，索引查找的速度快於順序查找，但低於二分查找。

在索引存儲中，不僅便於查找單個元素，而且更方便查找一個子表中的全部元素，若在主表中的每個子表後都預留有空閒位置，則索引存儲也便於進行插入和刪除運算。

3、分塊查找

分塊查找屬於索引查找，其對應的索引表為稀疏索引，具體地說，分塊查找要求主表中每個子表（又稱為塊）之間是遞增（或遞減）有序的。即前塊中最大關鍵字必須

小於後塊中的最小關鍵字，但塊內元素的排列可無序。它還要求索引值域為每塊中的最大關鍵字。

下圖是用於分塊查找的主表和索引表的示例：

分塊查找的算法同上面的索引查找算法類似，具體如下：<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">int Blocksch(mainlist A, indexlist B, int m, KeyType K) {//利用主表A和大小為m的索引表B分塊查找關鍵字為K的記錄 int i, j; for (i = 0; i < m; i++) if (K <= B[i].index) break; if (i == m) return -1; //查找失敗 j = B[i].start; while (j < B[i].start + B[i].length) { if (K == A[j].key) break; else j++; } if (j < B[i].start + B[i].length) return j; else return -1; } 若在索引表上不是順序查找，而是二分查找相應的索引項，則需要把算法中的for循環語句更換為如下的程序段： int low = 0, high = m - 1; while (low <= high) { int mid = (low + high) / 2; if (K == B[mid].index) { i = mid; break; } else if (K < B[mid].index) high = mid - 1; else low = mid + 1; } if (low > high) i = low; 這裡當二分查找失敗時，應把low的值賦給i，此時b[i].index是剛大於K的索引值當然若low的值為m，則表示真正的查找失敗。