分塊查找
分塊查找(Blocking Search)又稱索引順序查找它是一種性能介於順序查找和二分查找之間的查找方法
二分查找表存儲結構
二分查找表由分塊有序的線性表和索引表組成
()分塊有序的線性表
表R[n]均分為b塊前b塊中結點個數為
第b塊的結點數小於等於s;每一塊中的關鍵字不一定有序
但前一塊中
的最大關鍵字必須小於後一塊中的最小關鍵字即表是分塊有序的
()索引表
抽取各塊中的最大關鍵字及其起始位置構成一個索引表ID[lb]即
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)
注意
【例】若表中有個結點則應把它分成個塊每塊中含個結點用順序查找確定塊分塊查找平均需要做次比
較而順序查找平均需做次比較二分查找最多需次比較
注意
分塊查找算法的效率介於順序查找和二分查找之間
()塊的大小
在實際應用中分塊查找不一定要將線性表分成大小相等的若干塊可根據表的特征進行分塊
【例】一個學校的學生登記表可按系號或班號分塊
() 結點的存儲結構
各塊可放在不同的向量中也可將每一塊存放在一個單鏈表中
()分塊查找的優點
分塊查找的優點是
①在表中插入或刪除一個記錄時只要找到該記錄所屬的塊就在該塊內進行插入和刪除運算
②因塊內記錄的存放是任意的所以插入或刪除比較容易無須移動大量記錄
分塊查找的主要代價是增加一個輔助數組的存儲空間和將初始表分塊排序的運算
From:http://tw.wingwit.com/Article/program/sjjg/201311/23846.html
