查找-分块查找

素颜马尾好姑娘i 2022-05-12 03:00 177阅读 0赞

**索引存储结构**

存储节点信息时，建立索引表，索引表含有若干个索引项，索引项的一般形式：**(关键字，地址)**，关键字表示表示一个节点，地址是指向节点的信息。可以通过索引的方法来操作相应位置的数据。

**优点：**

1.提高数据查找的速度

2.插入、删除时，只需要移动索引表中对应节点的存储地址，而不必移动节点中节点的数据。

**缺点：**

增加了索引表，所以降低了存储空间的利用率。

![70][]

**分块查找（又称索引顺序查找）**

代码：

#include<stdio.h>
    //索引表
    typedef struct
    {
    int key;
    int address;
    }IdxTable;
    typedef IdxTable indxtable[3];
    //所有节点信息表
    typedef struct
    {
    int key;
    }NodeTable;
    typedef NodeTable nodetable[18];
    //二分查找
    int IndxSearch_erfen(indxtable idx,int m,int key1)
    {
    int left=0,right=m-1,mid;
    
    while(left<=right)
    {
    mid=(left+right)/2;
    if(idx[mid].key>=key1&&idx[mid-1].key<key1)
    {
    return idx[mid].address;
    }
    else if(idx[mid].key<key1)
    left=mid+1;
    else if(idx[mid].key>key1)
    right=mid-1;
    }
    }
    //顺序查找
    int IndxSearch_shunxu(int n,int m,int key1,indxtable idx,nodetable r)
    {
    //int b=n/m//每块的个数
    int b=n/m,i=IndxSearch_erfen(idx,m,key1);
    printf("在索引表的起始地址：%d\n",i);
    int data_n=i+b;//数据表起始位置到某块终点的长度
    while(i<data_n&&r[i].key!=key1)
    i++;
    if(i>=data_n)
    return -1;
    else
    return i;
    }
    void main()
    {
    nodetable r;
    int k=38;
    indxtable idx;
    int a[]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53},i;
    //数据表
    for(i=0;i<18;i++)
    r[i].key=a[i];
    //索引表
    idx[0].key=22;idx[0].address=0;
    idx[1].key=48;idx[1].address=6;
    idx[2].key=86;idx[2].address=12;
    //查找结果
    if((i=IndxSearch_shunxu(18,3,k,idx,r))!=-1)
    printf("元素%d的位置是%d\n",k,i);
    else
    printf("元素%d不在表中",k);
    }

[70]: /images/20220512/9248d61d62fc44c88ab15452c255cf98.png