清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 PROCEDURE INSERCH(V, n, KEY, K, m, X, j) WHILE(j一i>1)D0[对分查找索引表] t=(i+j)/2 IF(x≤KEY(t) then j=t else i=t IF (itj and(x>key(i))then i j=K(i); t=n IF(i≠m) then t=K(i+1)-1[确定顺序查找的终点] WHILE(j≤t)and(V()≠x)D0j=j+1[顺序查找子表] IF (j>t)then j=-1 RETURN
7.3 分块查找 PROCEDURE INSERCH(V，n，KEY，K，m，x，j) i＝1； j＝m WHILE (j－i＞1) DO [对分查找索引表] { t＝(i＋j)/2 IF (x≤KEY(t)) THEN j＝t ELSE i＝t } IF (i≠j)and(x＞KEY(i)) THEN i＝j j＝K(i)； t＝n IF (i≠m) THEN t＝K(i＋1)－1 [确定顺序查找的终点] WHILE (j≤t)and(V(j)≠x) DO j＝j＋1 [顺序查找子表] IF (j＞t) THEN j＝－1 RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 在分块查找中,为了找到被查元素x所在的子表,需要对分查找索引 表,在最坏情况下需要查找log2(m+1)次。 在相应子表中用顺序查找法查找元素x,在最坏情况下需要査找n/m (假设各子表长度相等)次;而在平均情况下需要查找n/(2m)次。 因此,分块查找的工作量为: 在最坏情况下需要查找log2(m+1)+n/m次, 平均情况下大约需要查找log2(m+1)+n/(2m次 m=n时,线性表L即为有序表,分块查找即为对分查找 当m=1时,线性表L为一般的无序表,分块查找即为顺序查找。 分块査找的效率介于对分查找和顺序查找之间
7.3 分块查找 在分块查找中，为了找到被查元素x所在的子表，需要对分查找索引 表，在最坏情况下需要查找log2(m＋1)次。 在相应子表中用顺序查找法查找元素x，在最坏情况下需要查找n/m （假设各子表长度相等）次；而在平均情况下需要查找n/(2m)次。 因此，分块查找的工作量为： 在最坏情况下需要查找log2(m＋1)＋n/m次， 平均情况下大约需要查找log2(m＋1)＋n/(2m)次。 当m＝n时，线性表L即为有序表，分块查找即为对分查找 当m＝1时，线性表L为一般的无序表，分块查找即为顺序查找。 分块查找的效率介于对分查找和顺序查找之间
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 struct indnode ET key;/*数据域,存放子表中的最大值, 其类型与线性表中元素的数据类型相同* intk;/*指针域,指示子表中第一个元素在线性表中的序号* /*函数返回被查找元素x在线性表中的序号, 如果在线性表中不存在元素值x,则返回一1* int inserch(v, n, s, m, x) int n, m ET X, VI struct indnode
7.3 分块查找 struct indnode { ET key；/*数据域，存放子表中的最大值， 其类型与线性表中元素的数据类型相同*/ int k； /*指针域，指示子表中第一个元素在线性表中的序号*/ }； /*函数返回被查找元素x在线性表中的序号， 如果在线性表中不存在元素值x，则返回－1 */ int inserch(v，n，s，m，x) int n，m； ET x，v[]； struct indnode s[] ；
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 I int i,j,t 1;j=m: while(j-i>1)/对分查找索引表* t=(i+j/2; if (x<=slt] key) j= else i=t if ((i!=j)&&(x>sli]. key)) i=j j=sLi].k; t=n; if(i!≡m)t=s[i+1].k-1;/*确定顺序查找的终点* while(j<=t)&&(V[j!=x)j=j+1;/*顺序查找子表* if (j>t) return(j)
7.3 分块查找 { int i，j，t； i＝1； j＝m； while (j－i＞1) /*对分查找索引表*/ { t＝(i＋j)/2； if (x＜＝s[t].key) j＝t； else i＝t； } if ((i!＝j)&&(x＞s[i].key)) i＝j； j＝s[i].k； t＝n； if (i!＝m) t＝s[i＋1].k－1；/*确定顺序查找的终点*/ while((j＜＝t)&&(V[j]!＝x)) j＝j＋1；/*顺序查找子表*/ if (j＞t) j＝－1； return(j)； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.4二叉排序树查找 7.4.1二又排序树及其构造 7.4.2二叉排序树查找
7.4 二叉排序树查找 7.4.1 二叉排序树及其构造 7.4.2 二叉排序树查找