分块查找算法c

1. 分块查找算法中如何对数据分块

可以实现确定待查找数据的上限和下限，
然后对该区间等分N块，
那么这N块就可以作为分块查找的块，
然后将原数组中的元素按区间插入进去，
当然，这样划分不能保证每个块中的元素个数相等，
但是，分块查找算法并不严格要求每块中的元素的个数相等。

2. 查找 - 线性表的查找 - 分块查找

分块查找

分块查找(Blocking Search)又称索引顺序查找 它是一种性能介于顺序查找和二分查找之间的查找方法

二分查找表存储结构

二分查找表由 分块有序 的线性表和索引表组成

( ) 分块有序 的线性表

表R[ n]均分为b块 前b 块中结点个数为

的最大关键字必须小于后一块中的最小关键字 即表是 分块有序 的

( )索引表

抽取各块中的最大关键字及其起始位置构成一个索引表ID[l b] 即

ID[i]( ≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置 由于表R是分块有序的 所以索引表是一个递增有序表

【例】下图就是满足上述要求的存储结构 其中R只有 个结点 被分成 块 每块中有 个结点 第一块中最大关键字 小于

第二块中最小关键字 第二块中最大关键字 小于第三块中最小关键字

分块查找的基本思想

分块查找的基本思想是

( )首先查找索引表

索引表是有序表 可采用二分查找或顺序查找 以确定待查的结点在哪一块

( )然后在已确定的块中进行顺序查找

由于块内无序 只能用顺序查找

分块查找示例

【例】对于上例的存储结构

( )查找关键字等于给定值K= 的结点

因为索引表小 不妨用顺序查找方法查找索引表 即首先将K依次和索引表中各关键字比较 直到找到第 个关键宇大小等于K的

结点 由于K< 所以关键字为 的结点若存在的话 则必定在第二块中;然后 由ID[ ] addr找到第二块的起始地址 从该地址

开始在R[ ]中进行顺序查找 直到R[ ] key=K为止

( )查找关键字等于给定值K= 的结点

先确定第二块 然后在该块中查找 因该块中查找不成功 故说明表中不存在关键字为 的结点

算法分析

( )平均查找长度ASL

分块查找是两次查找过程 整个查找过程的平均查找长度是两次查找的平均查找长度之和

①以二分查找来确定块 分块查找成功时的平均查找长度

ASL blk =ASL bn +ASL sq ≈lg(b+ ) +(s+ )/ ≈lg(n/s+ )+s/

②以顺序查找确定块 分块查找成功时的平均查找长度

ASL blk =(b+ )/ +(s+ )/ =(s + s+n)/( s)

注意

【例】若表中有 个结点 则应把它分成 个块 每块中含 个结点 用顺序查找确定块 分块查找平均需要做 次比

较 而顺序查找平均需做 次比较 二分查找最多需 次比较

注意

分块查找算法的效率介于顺序查找和二分查找之间

( )块的大小

在实际应用中 分块查找不一定要将线性表分成大小相等的若干块 可根据表的特征进行分块

【例】一个学校的学生登记表 可按系号或班号分块

( ) 结点的存储结构

各块可放在不同的向量中 也可将每一块存放在一个单链表中

( )分块查找的优点

分块查找的优点是

①在表中插入或删除一个记录时 只要找到该记录所属的块 就在该块内进行插入和删除运算

②因块内记录的存放是任意的 所以插入或删除比较容易 无须移动大量记录

分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算

3. 计算机考研：数据结构常用算法解析(8)

第九章 查找
查找分成静态查找和动态查找，静态查找只是找，返回查找位置。而动态查找则不同，若查找成功，返回位置，若查找不成功，则要返回新记录的插入位置。也就是说，静态查找不改变查找表，而动态查找则会有插入操作，会改变查找表的。
不同的查找所采用的存储结构也不同，静态查找采用顺序表，而动码迟态查找由于经常变动，所以用二叉排序树，二叉平衡树、B-和B+。
静态查找有，顺序查找，折半查找，分块查找(索引顺序查找)
顺序查找(Sequential Search)是最简单的一种查找方法。
算法思路
设给定值为k，在表(R1 R2……Rn)中，从Rn即最后一个元素开始，查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k，则查找成功，返回记录序号i;否则，查找失败，返回0。
算法描述
int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
{ int i;
r.data[0].key=k; //k存入监视哨//
i=r.len; //取表长//
while(r.data[i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(≠0)有r.data[i].key=k，则查找成功，返回i;若i从n递减到1都无记录的key为k，i再减1为0时，必有r.data[0].key=k，说明查找失败，返回i=0。
平均查找成功长度ASL= ，而查找失败时，查找次数等于n+l。
折半查找算法及分析
当记录的key按关系≤或≥有序时，不管是递增的还是递减的，只要有序且采用顺序存储。
算法描述
int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空间存在时//
{ mid=(low+high)/2; //求当前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //调整上界，向左部查找//
else
low=mid+1; //调整下界，向右部查找//
}
return(0); //low>high，查找失败//
}
判定树：用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树，但他的叶子结点所在层次之差不超过1。所以，折半查找在查找成功时和给定值进行比笑困较的关键字个数至多为
ASL=
分块查找算法及分析
分块查找(Blocking Search)，又称索引顺序查找(Indexed Sequential Search)，是顺序查找方法的一种改进，目的也是为了提高查找效率。
1.分块
设记录表长为n，将表的n个记录分成b= 个块，每块s个记录(最后一块记录数可以少于s个)，即：
且表分块有序，即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。
2.建立索引
每块对应一索引项：
KeymaxLink
其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
3.算法思路 分块索碰模念引查找分两步进行：
(1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
(2)在块内顺序查找。(只能用顺序查找，块内是无序的)

考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/

4. 求分块查找算法 最好有代码和详细注释

注意：采用“二分查找”时，初始的数组或其他线性表中的每个元素都必须是按一定的顺序排列的（从大到小，或从小到大），
该算法的基本思想：对一个有序数据序列，总是先把查找目标与该序列的中间的元素进行比较，我们假设该序列是由从小到大排列的，if(key > data[mid]),则key一定在data[mid]的又边，于是，把mid到序列data[end]分成一块，此时mid = (mid + end) / 2,依次类推

参考程序：

#include<stdio.h>
#define MAXSIZE 26 //定义索引表的最长长度
typedef char TYPE;

int blksearch(TYPE R[],TYPE K);
void main()
{
int num, i;
TYPE R[N + 1];
TYPE K;

for(i = 0;i<N;i++)
R[i]='a'+i;
printf("\nplease input the key number:\n");
K=getchar();
num=blksearch(R,K);

if(num!=-1)
printf("第%d个是关键字\n",num+1);
else
printf("查找失败！\n");
}

int blksearch(TYPE R[],TYPE K) //分块查找
{
int low1,mid,high1;
low1=0;
high1=N - 1; //二分查找区间上下界初值
while(low1<=high1)
{
mid=(low1+high1)/2;

if(K < R[mid])
high1=mid-1;
else
if(K > R[mid])
low1=mid+1;
else
return mid; //如果找到key，立即返回key的位置

}
return -1;// 只要上面的return语句没执行，则原数组中无key，返回-1

}

5. 分块查找(C语言)

i=idx[low1].low是块中第一个元素的起始位置的值

int blksearch(sqlist r,index idx,find=0,hb;) // bn为块个数 //
{ int i,;low=1,high1=bn,midl,find=0,hb;
while(low1<=high1&&!find)
{mid=(low1+high1)/2;
if(k<idx[mid1].key)high1=mid-1;
else if(k>idx[mid1],key)low1=mid1+1;
else{
low=mid1;
find=1;
}
到这里是初步锁定要查的元素在那个块，找到大的方向后 在块里进行进一步的搜索
if(low1<bn)//如果low1的值没有超过块的总个数
i=idx[low1].low; //i赋值为该块内第一个元素的起始位置
然后进一步查到元素