第十六天、分块查找

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

相关文章

来自专栏Code_iOS

Objective-C 内存管理(上)学习笔记

这里的“计数”表明必然会有一个东西(变量)来记录引用的变化,而在OC里这个变量就是retainCount;那么还有一个问题就是通过什么方式来操作这个变量,OC里...

502
来自专栏difcareer的技术笔记

彻底弄懂dalvik字节码【三】0x01:0x02:0x03:0x04:0x05:

【一】、【二】中从代码的角度分析了dalvik字节码解释执行的过程,这篇文章以一个例子来实际分析一下。

822
来自专栏Vamei实验室

安卓第八夜 玛丽莲梦露

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 

731
来自专栏python3

python3--面向对象的三大特性:封装,property,classmethod,staticmethod

AttributeError: type object 'A' has no attribute '__N'

511
来自专栏C/C++基础

RTTI简介

RTTI是Runtime Type Identification的缩写,是“运行时类型识别”的意思。面向对象的编程语言,象C++,Java,Delphi都提供了...

743
来自专栏Coding迪斯尼

reactjs自制Monkey语言编译器:解析组合表达式,ifelse语句块和间套函数调用

443
来自专栏老九学堂

【干货】Java字符串之10大热点问题!

其实作为Java初学者,字符串是一个必须迈过的坎,所以老九君为了大家能够更好的掌握字符串这个知识点,以及深入的了解一些原理,搜罗总结了以下10条Java字符串的...

2624
来自专栏Jerry的SAP技术分享

使用javap深入理解Java整型常量和整型变量的区别

下面我们就用javap将.class文件反编译出来然后深入研究Java里整型变量和整型常量的区别。

1023
来自专栏追不上乌龟的兔子

介绍一些Python str类的方法

上面的代码正确的返回了'0.333333',但是当x = 1 / 2时,由于小数只有一位,这个方案的结果就是'0.5'了,而不是预期中的'0.500000'。

794
来自专栏Golang语言社区

golang错题集

为什么呢?是不是有点诧异? 输出的都是“annei”,而“annei”又是“names”的最后一个元素,那么也就是说程序打印出了最后一个元素的值,而name对于...

1290

扫码关注云+社区