分塊查找演算法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賦值為該塊內第一個元素的起始位置
然後進一步查到元素