数据结构教案第八章.

array[mid].keyk) hig=mid-1; //在左子区间中查找 else low=mid+1; } //在右子区间中查找 return(-1); } //查找失败 例如，假设给定有序表中关键字为05,13,19,21,37,56,64,74,80,88,92将查找K=21和K=85的情况描述为图8-1及图8-2形式。 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 [ 05 13 19 21 37 56 64 74 80 88 92 ] low hig (a) 初始情形 教 学 过 程 设 计 (续表) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 (b) 经过一次比较后的情形 13 19 21 37 ] 56 64 74 80 88 92 [ 05 low hig mid [05 13 19 21 37 ] 56 64 74 80 88 92 low mid hig (c ) 经过二次比较后的情形 (array[mid].key=19) 图 8-1 查找K=21的示意图 0 1 2 3 4 5 6 7 8 9 10 19 [ 21 37 ] 56 64 74 80 88 92 05 13 mid low hig (d ) 经过三次比较后的情形 (array[mid].key=21) 图 8-1 查找K=21的示意图 (查找成功) 0 1 2 3 4 5 6 7 8 9 10 13 19 21 37 56 64 74 80 88 92 ] [ 05 low hig (a) 初始情形 0 1 2 3 4 5 6 7 8 9 10 教 学 过 程 设 计 (续表) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 [ 88 92 ] low mid hig (d) 经过三次比较后的情形 13 19 21 37 56 [ 64 74 80 88 92 ] 05 mid low hig (b) 经过一次比较后的情形 0 1 2 3 4 5 6 7 8 9 10 13 19 21 37 56 [ 64 74 80 88 92 ] 05 low mid hig (c) 经过二次比较后的情形 3.二分查找的性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，图8-1给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树见图8-3。 5 2 8 0 3 6 9 1 4 7 10 图8-3 具有11个关键字序列的二分查找判定树 从图8-3 可知，查找21的过程是从根到结点3的路径，查找85,应在结点9的左子树上,但其左子树为空,故失败。 二叉树第K层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。则二分查找的时间复杂度为O(log2n)。 5 2 8 0 3 6 9 1 4 7 10 图8-3 具有11个关键字序列的二分查找判定树 任务四：分块查找 分块查找 1.分块查找 的思想 分块查找是顺序查找的一种改进方法，又称索引顺序查找，具体实现如下：将一个主表分成n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。 typedef struct { int key; …; } NODE; typedef struct { int key, pos; } INDEX; 例如，给定关键字序列如下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3，即将该序列分成 3个子表，每个子表有6个元素，则得到的主表和索引表如图所示。 22 48 86 0 6 12 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 分块查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38, 则先在索引表中按顺序比较，因为22