C語言分塊查詢演算法,索引順序查詢演算法

2020-07-16 10:04:29
例如,採用分塊查詢法在有序表 11、12、18、28、39、56、69、89、96、122、135、146、156、256、298 中查詢關鍵字為 96 的元素。

査找特定關鍵字元素個數為 15,要求使用者輸入有序表各元素,程式輸出査找成功與否,若成功,還顯示元素在有序表中的位罝。

實現過程:

(1)定義結構體 index,用於儲存塊的結構,並定義該結構體陣列 index_table。

(2)自定義函數 block_search(),實現分塊查詢。

(3) main() 函數作為程式的入口函數。程式程式碼如下:
#include <stdio.h>
struct index    //定義塊的結構
{
    int key;    //塊的關鍵字
    int start;    //塊的起始值
    int end;    //塊的結束值
}index_table[4];    //定義結構體陣列

int block_search(int key,int a[])    //自定義實現分塊查詢
{
    int i,j;
    i=1;
    while(i<=3&&key>index_table[i].key)    //確定在哪個塊中
        i++;
    if(i>3)    //大於分得的塊數,則返回0
        return 0;
    j=index_table[i].start;    //j等於塊範圍的起始值
    while(j<=index_table[i].end&&a[j]!=key)    //在確定的塊內進行順序查詢
        j++;
    if(j>index_table[i].end)    //如果大於塊範圍的結束值,則說明沒有要査找的數,j置0
        j = 0;
    return j;
}

int main()
{
    int i,j=0,k,key,a[16];
    printf("請輸入15個數:n");
    for(i=1;i<16;i++)
        scanf("%d",&a[i]);    //輸入由小到大的15個數
    for(i=1;i<=3;i++)
    {
        index_table[i].start=j+1;    //確定每個塊範圍的起始值
        j=j+1;
        index_table[i].end=j+4;    //確定每個塊範圍的結束值
        j=j + 4;
        index_table[i].key=a[j];    //確定每個塊範圍中元素的最大值
    }
    printf("請輸入你想査找的元素:n");
    scanf("%d",&key);    //輸入要查詢的數值
    k=block_search(key,a);    //呼叫函數進行杳找
    if(k!=0)
        printf("查詢成功,其位置是:%dn",k);    //如果找到該數,則輸出其位置
    else
        printf("查詢失敗!");    //若未找到,則輸出提示資訊
    return 0;
}

執行結果:

請輸入15個數:
11 12 18 28 39 56 69 89 96 122 135 146 156 256 298
請輸入你想査找的元素:
96
查詢成功,其位置是:9

技術要點:

分塊査找也稱為索引順序査找,要求將待查的元素均勻地分成塊,塊間按大小排序,塊內不排序,所以要建立一個塊的最大(或最小)關鍵字表,稱為索引表

本範例中將給出的 15 個數按關鍵字大小分成了 3 塊,這 15 個數的排列是一個有序序列,也可以給出無序序列,但必須滿足分在第一塊中的任意數都小於第二塊中的所有數,第二塊中的所有數都小於第三塊中的所有數。當要査找關鍵字為 key 的元素時,先用順序杳找在已建好的索引表中查出 key 所在的塊中,再在對應的塊中順序查詢 key,若 key 存在,則輸出其相應位置,否則輸出提示資訊。