由于块内无序,只能用顺序查找。 分块检索方法通过将查找缩小在某个块中从而 提高了检索的效率,其查找的效率由两部分组成, 是为确定某一块对索引表的平均查找长度E,二是 块内查找所需的平均查找长度Eb。 火奇以顺序检索来确定块,则分块查找成功时的 均查找长度为 ASL:。=E+E 6+1+l n/sts n+ s +1 +1 2S 当=V时,ASLd取最小值Vn+1
由于块内无序，只能用顺序查找。 分块检索方法通过将查找缩小在某个块中从而 提高了检索的效率，其查找的效率由两部分组成， 一是为确定某一块对索引表的平均查找长度El，二是 块内查找所需的平均查找长度Eb 。 ➢ 若以顺序检索来确定块，则分块查找成功时的 平均查找长度为： ASLids=El+Eb= 1 2 1 2 / 2 1 2 1 2 + + + = + = + + + s b s n s s n s 当 s = n 时，ASLids取最小值 n +1
若以二分检索来确定块,则分块检索查找成功 时的平均查找长度为: ASLs=E+Eb:og2(b+1)-1+(S+1)/2 ≈og2(n/s+1)+s/2 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大★大大大大★★大大大大 分块查找算法 /*文件名: i search . c函数名: indexseqsearch 大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大★大大大大★大★大大大大 include seqlist. h typedef struct/索引表结点类型* i datatype key
➢ 若以二分检索来确定块，则分块检索查找成功 时的平均查找长度为： ASL’ ids=El+Eblog2（b+1）-1+（s+1）/2 log2（n/s+1）+s/2 /**************************************************************/ /* 分块查找算法 */ /* 文件名：i_search.c 函数名：indexseqsearch() */ /**************************************************************/ #include "seqlist.h" typedef struct /*索引表结点类型*/ { datatype key;
t address 3 indexnode 分块查找 int indexseqsearch(seqlist I,indexnode indexI, int m, datatype key /分块查找关键字为Key的记录,索引表为 Windex0.m-1]* int i=0, last While(<m&&key>inde刈们]key)i++; if(i>=m) return -1 else /“在顺序表中顺序检索
int address; } indexnode; /*--------分块查找--------*/ int indexseqsearch(seqlist l,indexnode index[],int m,datatype key) { /*分块查找关键字为Key的记录，索引表为index[0..m-1]*/ int i=0,j,last; while (i<m && key>index[i].key) i++; if (i>=m) return -1; else { /*在顺序表中顺序检索*/
f(==m-1)j=len-1; else j=indeⅫi+1 address1;鬥初始时指向本块的 最后一个结点* while (>=index[]. address & key!=L data]) j-;/从后向前逐个查找 if (j<index( address)return -1 else return j 算法9.3分块检索
if (i==m-1) j=l.len-1; else j=index[i+1].address-1; /*j初始时指向本块的 最后一个结点*/ while (j>=index[i].address && key!=l.data[j] ) j--; /*从后向前逐个查找*/ if (j<index[i].address) return -1; else return j; } } 算法9.3 分块检索
习题 9.1在分块检索中,对256个元素的线性表分成多少块 最好?每块的最佳长度是多少?若每块的长度为8,其 平均检索的长度是多少?
9.1 在分块检索中，对256个元素的线性表分成多少块 最好？每块的最佳长度是多少？若每块的长度为8，其 平均检索的长度是多少？ 习题