数据结构-查找(18)

数据结构复习资料

例 如 ， 给 定 关 键 字 序 列 如 下 ： 22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53, 假 设 n=3,即将该序列分成3个子表，每个子表有6个元素，则 得到的主表和索引表如图所 示。22 0 48 6 86 12

22 12 13 8

9

20 33 42 44 38 24 48 60 58 74 49 86 53

分块查找的过程是先确定待查记录所在的块，然后在块中 顺序查找。假设给定k=38, 则先在索引表中按顺序比较，因为 22<k<48,则可确定38应该在第二块中，从第二块的第一个记 录 array[6] 顺序查起. 分块查找的时间复杂度是O(m+n) m是块长度，n是索引表 长度。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构-查找(18)在线全文阅读。