第十六天、分块查找

题目 采用分块查找的方法查找有序表,有序表个数为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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Vijos P1785 同学排序【模拟】

同学排序 描述 现有m位同学,第1位同学为1号,第2位同学为2号,依次第m位同学为m号。要求双号的学生站出来,然后余下的重新组合,组合完后,再次让双号的学生站出...

2494
来自专栏各种机器学习基础算法

php链式操作的实现

一、什么是链式操作? 直接说链式操作,也许大家不清楚是什么,但是在平时使用框架的过程中,大家肯定见到过这样子的使用: $db->where()->limit()...

3277
来自专栏desperate633

第九课 汇总数据聚集函数聚集不同的值

682
来自专栏喵了个咪的博客空间

zephir-(7)数组

#zephir-数组# ? ##前言## 先在这里感谢各位zephir开源技术提供者 在java和c++中几乎所有的操作都是正对于类开展的,但是在php中你们常...

3677
来自专栏deepcc

jquery插件开发模板

32910
来自专栏企鹅号快讯

Python模块知识4:序列化Json/pickle

序列化与反序列化 序列化:把Python的基本数据类型转为字符串 反序列化:把字符串转为Python的基本数据类型 Python中用于序列化的两个模块: jso...

1929
来自专栏java一日一条

教你在Java接口中定义方法

基本上所有的Java教程都会告诉我们Java接口的方法都是public、abstract类型的,没有方法体的。

581
来自专栏破晓之歌

python中的内置函数(双下划线) 原

如果我们是直接执行某个.py文件的时候,该文件中那么”__name__ == '__main__'“是True,但是我们如果从另外一个.py文件通过import...

902
来自专栏前端菜鸟变老鸟

Object.keys和Object.values

使用Object.keys()或者Object.values()获取循环变量,渲染的时候根据循环变量获取值。Object.keys()函数返回索引(不仅仅是数字...

662
来自专栏blackheart的专栏

[C#6] 2-nameof 运算符

0. 目录 C#6 新增特性目录 1. 老版本的代码 1 using System; 2 namespace csharp6 3 { 4 in...

1905

扫码关注云+社区