有序列表中分块查找-c语言

拼搏现实的明天。 2022-06-04 00:05 132阅读 0赞

#include <stdio.h>
    struct block_index{
        int start;
        int end;
        int key;
    } index_key[3];
    int blockSearch(int key, int a[]);
    
    int main()
    {
        int numList[16];
        int i = 0;
        int j = 0;
        int key = 0;
        int ret = 0;
        printf("请输入需要查找的序列:\n");
        for(i=0;i<15;i++)
        {
            scanf("%d", &numList[i]);
        }
        printf("请输入需要查找的元素：\n");
        scanf("%d", &key);
        i = 0;
        while(i<3)//进行分块，因为我们要求在15个数中进行查找，所以分为3块
        {
            index_key[i].start = j; //存储每块的起点
            index_key[i].end = j+4; //存储没快的终点
            index_key[i].key = numList[j+4]; //记录每块的最大值，也就是终点的值，因为我们是按从小到大输入的有序列表
            j += 5;//将j拨到下一块的起始点
            i++; //进入下一块
        }
        ret = blockSearch(key, numList); //调用函数进行查找
        if(0 == ret)
        {
            printf("查询失败!\n");
            return -1;
        }
        else
        {
            printf("查找成功！\n其位置是%d\n", ret++);
        }
    
        return 0;
    }
    
    int blockSearch(int key, int a[])
    {
        int i = 0 ;
        int j = 0;
        while (i<3 && key>index_key[i].key)//先确定key值在哪块
        {
            i++;
        }
        if(i>=3)// 不在我们分的三块中，则函数结束
        {
            return 0;
        }
        j = index_key[i].start;//确定在i块后，将此块的起始值赋给j
        while(j<index_key[i].end && key !=a[j])//轮训此块，确定j值,因为序列下标值是从0开始的，所以我们的返回值是j+1
            j++;
    
        return j+1;
    }

结果：

└─\[0\] a.out  
请输入需要查找的序列:  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15   
请输入需要查找的元素：  
1  
查找成功！  
其位置是1