第十六天、分块查找

题目 采用分块查找的方法查找有序表,有序表个数为15,要求用户输入有序表各元素,程序输出查找结果,若成功,显示出元素在有序表中的位置。 1、程序分析     step1先选取各块中的最大关键字构成一个索引表;     step2查找分为两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。 2、程序实现

 <stdlib.h>
/*声明分块查找函数*/
int block_search(int iKey,int iArr[]);

/*定义块的结构体*/
struct index
{
    int iKey;       //关键字
    int iStart;     //起始位置
    int iEnd;       //结束位置
}index_table[4];    //结构体数组

/**********************************
*函数名称:block_search
*参数说明:iKey      查询的关键字
*         iArr      有序数列保存的数组
*说明:    分块查找
***********************************/
int block_search(int iKey,int iArr[])
{
    int i = 1,j;
    while((i < 4) && (iKey > index_table[i].iKey))  //确定要查找的元素在哪个块里
    {
        i++;
    }
    if(i > 3)                                       //当大于最大块数的时候表明没有查找到,返回0
    {
        return 0;
    }
    else
    {
        j = index_table[i].iStart;                      //j为块范围的起始位置
        while((j <= index_table[i].iEnd) && (iArr[j] != iKey))
        {
            j++;
        }
        if(j > index_table[i].iEnd)                     //超出块的范围
        {
            return 0;
        }
        return j;
    }
}

void main(void)
{
    int i,j = 0,iRet,iKey,iArr[16];
    printf("请输入15个有序数:");
    for(i = 1;i < 16;i++)
        scanf("%d",&iArr[i]);
    for(i = 0;i < 3;i++)
    {
        index_table[i].iStart = j + 1;      //确定每个块范围的起始位置
        j = j + 1;
        index_table[i].iEnd = j + 4;        //确定每个块范围的结束位置
        j = j + 4;
        index_table[i].iKey = iArr[j];      //确定每个块范围的元素最大值
    }
    printf("请输入您要查询的数字:");
    scanf("%d",&iKey);
    iRet = block_search(iKey,iArr);
    if(iRet != 0)
        printf("查找成功,其位置是:%d\n",iRet);
    else
        printf("查找失败!\n");
}

3、显示结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏听Allen瞎扯淡

Integer的highestOneBit方法源码解析

在读HashMap源码的时候,遇到了Integer的highestOneBit静态方法不是太理解,所以就读了一下源码,这里记录一下。

1991
来自专栏于晓飞的专栏

Java 容器 接口

在开发中使用容器正常的流程是,首先根据需求确定使用何种容器模型,然后选择一个符合性能要求的容器实现类或者自己实现一个容器类。例如:

742
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict专栏)

Python3 与 C# 基础语法对比(基础知识场):https://www.cnblogs.com/dotnetcrazy/p/9102030.html

783
来自专栏Java开发者杂谈

java如何获取一个对象的大小

When---什么时候需要知道对象的内存大小 在内存足够用的情况下我们是不需要考虑java中一个对象所占内存大小的。但当一个系统的内存有限,或者某块程序代码允许...

9296
来自专栏飞雪无情的博客

Go语言参数传递是传值还是传引用

其实对于传值和传引用,是一个比较古老的话题,做研发的都有这个概念,但是可能不是非常清楚。对于我们做Go语言开发的来说,也想知道到底是什么传递。

1163
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict专栏)

Python3 与 C# 基础语法对比(基础知识场):https://www.cnblogs.com/dotnetcrazy/p/9102030.html

23110
来自专栏null的专栏

设计模式——类图以及类与类之间的关系

    设计模式在程序设计上有着很重要的作用,使用设计模式可以使得代码更容易被理解,使得代码更规范,真正实现工程化。 一、用UML表示一个类 ? 类图一般是三行...

3534
来自专栏绿巨人专栏

[Java] 设计模式: Code Shape - 管理你的代码结构

3906
来自专栏小灰灰

JDK容器学习之Queue: ArrayDeque

数组双端队列 ArrayDeque 双端队列,表示可以添加元素到(或删除,获取)队列头也可以添加元素到(或删除,获取)队列尾 ? 1. 底层数据结构 类中定义成...

1816
来自专栏老九学堂

十七个C语言新手编程时常犯的错误及解决方式

编译程序把a和A认为是两个不同的变量名,而显示出错信息。C认为大写字母和小写字母是两个不同的字符。习惯上,符号常量名用大写,变量名用小写表示,以增加可读性。

1424

扫码关注云+社区