分块查找（索引顺序表查找）

分块查找：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

方法描述：将n个数据元素“按块有序”划分为m块（m<=n）。每一块中的数据元素不必有序，但块与块之间必须“按块有序”，即第1快中的任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都小于第3块中的任一元素，……

图示分块如下：

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHN0cm9uZz6y2df3sr3W6KO6PC9zdHJvbmc+PC9wPgo8cD4xoaLPyNGhyKG497/s1tC1xNfutPO52Lz819a5ubPJ0ru49sv30v2x7TwvcD4KPHA+MqGisunV0rfWwb2yv7fWo7rPyLbUy/fS/bHtvfjQ0Lb+t9ay6dXSu/LLs9DysunV0qOs0tTIt7aotP2y6bzHwrzU2sTE0ru/6dbQo7vIu7rz1NrS0ci3tqi1xL/s1tDTw8uz0PK3qL340NCy6dXSoaM8L3A+CjxwPjxzdHJvbmc+t9a/6bLp1dLGvb75sunV0rOktsijujwvc3Ryb25nPjwvcD4KPHA+yeizpLbIzqputcSx7b751Mi12LfWs8liv+mjrMO/v+m6rNPQc7j2vMfCvKOs1PJiPW4vczs8L3A+CjxwPsuz0PKy6dXSy/nU2r/po6y31r/psunV0rXExr2++bLp1dKzpLbIPShiJiM0MzsxKS8yICYjNDM7IChzJiM0MzsxKS8yID0gKG4vcyYjNDM7cykvMiYjNDM7MaO7PC9wPgo8cD7V27DrsunV0sv51Nq/6aOst9a/6bLp1dK1xMa9vvmy6dXSs6S2yD1sb2cyKG4vcyYjNDM7MSkmIzQzO3MvMqO7PC9wPgo8cD7TxbXjo7rU2rHt1tCy5cjru/LJvrP90ru49rzHwrzKsaOs1rvSqtXStb24w7zHwrzL+dTav+mjrL7N1Nq4w7/p1tC9+NDQsuXI67vyyb6z/dTLy+OjqNLyv+zE2s7e0PKjrMv50tSyu9Do0qq088G/0sa2r7zHwryjqaGjPC9wPgo8cD7IsbXjo7rU9rzTwcvSu7j2uKjW+sr91+m1xLTmtKK/1bzkus29q7P1yryx7bfWv+nFxdDytcTUy8vjoaM8L3A+CjxwPtDUxNyjur3p09rLs9DysunV0rrNtv631rLp1dLWrrzkoaM8L3A+CjxwPsq+wP0oYmxvY2suYymjujwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include #include #define MAX 3 #define MAXSIZE 18 typedef int ElemType; typedef struct IndexItem{ ElemType index; int start; int length; }IndexItem; IndexItem indexlist[MAX]; ElemType MainList[MAXSIZE] = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53}; int sequential(IndexItem indexlist[], ElemType key) { int index; if(indexlist[0].index >= key) return 1; for(index = 1; index <= MAX; index++){ if((indexlist[index-1].index < key)&&(indexlist[index].index >= key)) return index+1; } return 0; } int mainsequential(ElemType MainList[], int index, ElemType key) { int i, num=0; for(i = 0; i < index-1; i++){ num += indexlist[i].length; } for(i = num; i < num+indexlist[index-1].length; i++){ if(MainList[i] == key) return i+1; } return -1; } int main(void) { indexlist[0].index = 22; indexlist[0].start = 1; indexlist[0].length = 6; indexlist[1].index = 48; indexlist[1].start = 7; indexlist[1].length = 6; indexlist[2].index = 86; indexlist[2].start = 13; indexlist[2].length = 6; int index = sequential(indexlist, 38); printf("index = %d.\n", index); int mainindex = mainsequential(MainList, index, 38); printf("mainindex = %d.\n", mainindex); return 0; }
编译：gcc block.c

运行：./a.out

测试结果：

index = 2.
mainindex = 10.