c语言分块查找算法(分块查找的效率与线性表被分成多少块有关)

导语：C语言：数据结构-线性表的查找-分块查找

分块查找

分块查找（又称为索引顺序查找），是顺序查找的一种改进方法。在分块查找时，把表内的记录按某种属性分成n（n>1）个块（子表），且块间有序，即后一个块中所有记录关键字的值比前一个块中所有记录的关键字值都大，而块内关键字值的大小可以是无序的。然后建立一个相应的“索引表”，索引表由若干个索引记录组成，每个索引记录对应一个块。索引记录包含两个数据项，即对应块内最大关键字值和块中第一个记录位置的地址指针。

分块查找分为两个步骤：第一步是要对索引表进行查找以确定给定值所在的块，由于索引表有序，则可用顺序查找，也可用折半查找；第二步是在该块中查找给定的值，由于块内不一定有序，所以要用顺序查找。

例8-2：线性表中共有9个数据元素，其对应关键字分别为{16，22，5，11，66，38，62，88，100}，用分块查找方法查找关键字为66的数据元素。分块方法和索引表如图8-4所示。

分块查找示意图

线性表被分为3块，每块3个数据元素。已知给定值为66，第一步先将66与索引表中各个块的最大关键字进行比较，66大于16与 62，且小于100，因此可以判断给定值如果存在则应在第三块中。第二步在第三块中进行顺序查找，直至查找成功或失败。

顺序查找、折半查找和分块查找对被查的表中元素的要求是怎样的？

3种方法对查找的要求分别如下：

（1）顺序查找：表中元素可以任意次序存如。

（2）折半查找：表中元素必须以关键字的大小递增或递减的次序存入且为顺序存储。

（3）分块查找：表中块内元素可以任意顺序存放，但块与块之间必须以关键字的大小递增或递减存放，即前一块内所有元素的关键字都不能大于（或小于）后一块内任何元素的关键字。

本文内容由小森整理编辑！