您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

索引查找與分塊查找算法詳解 - C語言實現

編輯：關於C

1. 基本概念

索引查找（Indexed Search），又稱分級查找。基本思想：將主表劃分為若干子表，為每個子表建立一個索引項，所有索引項構成索引表。查找時先在索引表確定子表，再在子表中查找具體記錄。

索引表項結構

typedef struct {
    KeyType index;   // 索引鍵值（如子表最大關鍵字）
    int start;       // 子表在主表中的起始下標
    int length;      // 子表長度
} IndexItem;

主表結構

typedef struct {
    KeyType key;     // 關鍵字
    // 其他數據域...
} ElemType;

2. 索引查找算法

順序查找索引表版

int IdxSearch(ElemType A[], IndexItem B[], int m, KeyType K1, KeyType K2) {
    int i, j;
    // 1. 在索引表中查找索引值 K1
    for (i = 0; i < m; i++)
        if (K1 == B[i].index) break;
    if (i == m) return -1; // 索引表查找失敗

    // 2. 在對應子表中順序查找關鍵字 K2
    j = B[i].start;
    while (j < B[i].start + B[i].length) {
        if (K2 == A[j].key) break;
        j++;
    }
    return (j < B[i].start + B[i].length) ? j : -1;
}

子表鏈式存儲版

// 主表節點包含 next 域
while (j != -1) {
    if (K2 == A[j].key) break;
    j = A[j].next;
}
return j;

稠密索引優化

若每個索引項唯一對應一條記錄，查找成功直接返回 B[i].start。

3. 性能分析

平均查找長度 ASL = (1+m)/2 + (1+s)/2 = 1 + (m+s)/2
設子表長度均勻 s = n/m，則 ASL = 1 + (m + n/m)/2
當 m = √n 時 ASL 最小 = 1 + √n，時間複雜度 O(√n)
快於順序查找 O(n)，慢於二分查找 O(log n)

4. 分塊查找

屬於索引查找的一種，索引表為稀疏索引。要求：

主表分塊，塊間有序（前塊最大關鍵字 < 後塊最小關鍵字）
塊內可無序
索引值取各塊最大關鍵字

分塊查找算法

int BlockSearch(ElemType A[], IndexItem B[], int m, KeyType K) {
    int i, j;
    // 1. 索引表查找：找到第一個 index >= K 的塊
    for (i = 0; i < m; i++)
        if (K <= B[i].index) break;
    if (i == m) return -1;

    // 2. 塊內順序查找
    j = B[i].start;
    while (j < B[i].start + B[i].length) {
        if (K == A[j].key) break;
        j++;
    }
    return (j < B[i].start + B[i].length) ? j : -1;
}

索引表二分查找優化

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 指向第一個 > K 的索引項
if (i == m) return -1;   // 真正失敗

5. 總結

方法	前提條件	時間複雜度	適用場景
順序查找	無序	O(n)	小規模、無序數據
索引查找	分塊、建立索引	O(√n)	中等規模、頻繁查找、需範圍查詢
分塊查找	塊間有序	O(log m + s)	動態插刪、塊內無序
二分查找	整體有序	O(log n)	靜態有序數據

6. C語言完整示例

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000
#define MAXB 100

typedef int KeyType;
typedef struct { KeyType key; } ElemType;
typedef struct { KeyType index; int start, len; } IndexItem;

int blockSearch(ElemType A[], IndexItem B[], int m, KeyType K) {
    int i = 0, j;
    while (i < m && K > B[i].index) i++;
    if (i == m) return -1;
    for (j = B[i].start; j < B[i].start + B[i].len; j++)
        if (A[j].key == K) return j;
    return -1;
}

int main() {
    // 示例：主表 3 塊，每塊 3 個元素
    ElemType A[MAXN] = {{1},{3},{5}, {7},{9},{11}, {13},{15},{17}};
    IndexItem B[MAXB] = {{5,0,3}, {11,3,3}, {17,6,3}};
    int m = 3;
    KeyType K;
    while (scanf("%d", &K) == 1) {
        int pos = blockSearch(A, B, m, K);
        printf("Key %d -> %s\n", K, pos==-1?"Not found": "Found");
    }
    return 0;
}