清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.2有序表的对分查找 int serch(v,n,x)/*函数返回被查找元素x在线性表中的序号 如果在线性表中不存在元素值x,则返回-1*/ int n: ET v: i int i,j,k i=1;j=n; while (i<=j) k=(i+j)/2 if (vlk-1==x return(k-1) if(v[k-1]>x)j=k-1; else i=k+1 return(-1)
7.2 有序表的对分查找 int bserch(v，n，x) /*函数返回被查找元素x在线性表中的序号 如果在线性表中不存在元素值x，则返回－1 */ int n； ET x，v[]； { int i，j，k； i＝1； j＝n； while (i＜＝j) { k＝(i＋j)/2； if (v[k－1]＝＝x) return(k－1)； if (v[k－1]＞x) j＝k－1； else i＝k＋1； } return(－1)； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 分块有序表 将长度为n线性表分成m个子表,各子表的长度可以相 等,也可以互相不等,但要求后一个子表中的每一个 元素均大于前一个子表中的所有元素 分块有序表的结构可以分为两部分: (1)线性表本身采用顺序存储结构。 (2)再建立一个索引表。在索引表中,对线性表的每个子 表建立一个索引结点,每个结点包括两个域:一是数 据域,用于存放对应子表中的最大元素值;二是指针 域,用于指示对应子表的第一个元素在整个线性表中 的序号
7.3 分块查找 分块有序表 将长度为n线性表分成m个子表，各子表的长度可以相 等，也可以互相不等，但要求后一个子表中的每一个 元素均大于前一个子表中的所有元素。 分块有序表的结构可以分为两部分： (1)线性表本身采用顺序存储结构。 (2)再建立一个索引表。在索引表中，对线性表的每个子 表建立一个索引结点，每个结点包括两个域：一是数 据域，用于存放对应子表中的最大元素值；二是指针 域，用于指示对应子表的第一个元素在整个线性表中 的序号
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 struct indnode et key;/*数据域,存放子表中的最大值, 其类型与线性表中元素的数据类 型相同*/ intk;/指针域,指示子表中第一个元素 在线性表中的序号米/
7.3 分块查找 struct indnode { ET key；/*数据域，存放子表中的最大值， 其类型与线性表中元素的数据类 型相同*/ int k； /*指针域，指示子表中第一个元素 在线性表中的序号*/ }；
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 索引表 数据域 22 46 86 指针域 13 线性表:221213080920334244382446605874478653
7.3 分块查找
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.3分块查找 (1)首先查找索引表,以便确定被查元素所在的子表。由 于索引表数据域中的数据是有序的,因此可以采用对 分查找。 (2)然后在相应的子表中用顺序查找法进行具体的查找 分块查找 输入:长度为n的线性表L的存储空间V(1:n);索引表中 的数据域存储空间KEY(1:m)与指针域存储空间 K(1:m);被查元素x。 输出:被查元素x在线性表L中的序号j(即使L(j) x的j)。如果x不在线性表L中,则置j=-1
7.3 分块查找 (1)首先查找索引表，以便确定被查元素所在的子表。由 于索引表数据域中的数据是有序的，因此可以采用对 分查找。 (2)然后在相应的子表中用顺序查找法进行具体的查找。 分块查找 输入：长度为n的线性表L的存储空间V(1：n)；索引表中 的数据域存储空间KEY(1：m)与指针域存储空间 K(1：m)；被查元素x。 输出：被查元素x在线性表L中的序号j（即使L(j) ＝x的j）。如果x不在线性表L中，则置j＝－1