【C语言程序设计】C语言分块查找算法，索引顺序查找算法！

「爱情、让人受尽委屈。」 2022-10-23 04:52 216阅读 0赞

例如，采用分块查找法在有序表 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("查找成功，其位置是：%d\n",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 存在，则输出其相应位置，否则输出提示信息。

![fc2477a01039694a7c8e0d1028f7a6a7.gif][]

不管你是转行也好，初学也罢，进阶也可，如果你想学编程，进阶程序员~

【值得关注】我的 **[编程学习交流俱乐部][Link 1]**！【点击进入】

全栈程序员正在等你加入~

![1857cbc19cab869312521de965e92e12.png][]

[fc2477a01039694a7c8e0d1028f7a6a7.gif]: /images/20221022/f3e11d25edef454981c810db06dbef5c.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=teZNipK1
[1857cbc19cab869312521de965e92e12.png]: /images/20221022/a3a600d5e8544078a37ed99d47ba93b4.png