North China Electric power University 2)块中的记录是任意排列的,则在块中只能用顺序查找 分块查找的平均查找长度应该是前两者之和: 即: AsLb=Lb+Lw Lb:为查找所在块的平均查找长度。 Lw为块中查找元素的平均查找长度。 已知表的长度为n,分成b小块,每块有s个元素,那 么b=n/s.若表中各元素的查找概率相等,那么每块的 查找概率为1/b,块中每个元素的查找概率为1/s 用顺序查找方法,确定所在的块,则Lb=1/b 2 用顺序查找方法,查找的元素所在位置,则Lw=1
North China Electric Power University 2)块中的记录是任意排列的，则在块中只能用顺序查找。 分块查找的平均查找长度应该是前两者之和： 即： ASLbs=Lb+Lw Lb:为查找所在块的平均查找长度。 用顺序查找方法,确定所在的块,则Lb=1/b∑j j=1 b 用顺序查找方法,查找的元素所在位置,则Lw=1/s∑i i=1 s 已知表的长度为n,分成b小块,每块有s个元素,那 么b=n/s.若表中各元素的查找概率相等,那么每块的 查找概率为1/b,块中每个元素的查找概率为1/s. Lw:为块中查找元素的平均查找长度
North China Electric Power University I AsL bs 5(+1)2++12 L八/2行s+2)=1/20/5+9+1 1 由上式可以看出,分块查找的平均查找长度不仅和 表的长度n有关,而且和每一块中的元素个数s有关 可以证明:当s=n时,平均查找长度最小=/n+1 用折半查找确定所在的块,则分块查找的平均查找长 度为ASLb=10g2(b+1)-1+(s+1)/2 =1og2(n/s+1)+(s-1)/2
North China Electric Power University ASLbs=1/b∑j+1/s∑i =(b+1)/2+(s+1)/2 =1/2(n/s+s+2)=1/2(n/s+s)+1 j=1 b i=1 s 可以证明:当s= 时，平均查找长度最小= +1 由上式可以看出，分块查找的平均查找长度不仅和 表的长度n有关，而且和每一块中的元素个数s有关。 n n 用折半查找确定所在的块，则分块查找的平均查找长 度为ASLbs =log2(b+1)-1+(s+1)/2 =log2(n/s+1)+(s-1)/2
分块査找的算法描述如下: Function Search idx(st: sq Table, Id: IndexTable; k: Key Type): Integer; {st为查找表,Id为索引表,k为待查关键字} Begin low:=1; high: =Id Length; found: false; while (low<=high)and(foundfalse) Do I mid=(low+high)div 2; if(k<ld Elem mid]. Key) then high: =mid -1 else if(kId. Elem mid]. key)then low: =mid+1 else i found: true; low: =mid; S:=IdElem[low stadr {经索引表查找后,下一步的查找范围定位在第low块} if (high<ld Length) then t: =Id Elem low+1. stadr-l else t: =st lengt if(st Elem[t key=k then return(t) else i st Elem[0]: =st Elem t+llist Elem t+lkey: =k; i: = s while(st Elemi Key<>k) Do i:=i+1 st Elem t+1: st Elem O ifK< >t+l then return gi else return(o); end
分块查找的算法描述如下： Function Search_idx(st:sqTable,Id:IndexTable;k:KeyType):Integer; {st为查找表，Id为索引表，k为待查关键字} Begin low:=1;high:=Id.Length;found:=false; while (low<=high) and (found=false) Do [ mid=(low+high) div 2; if(k<Id.Elem[mid].Key) then high:=mid-1 else if (k>Id.Elem[mid].key) then low:=mid+1 else [ found:=true;low:=mid;] ] s:=Id.Elem[low].stadr; {经索引表查找后，下一步的查找范围定位在第low块} if (high<Id.Length) then t:=Id.Elem[low+1].stadr-1 else t:=st.length; if(st.Elem[t].key=k) then Return(t) else [ st.Elem[0]:=st.Elem[t+1];st.Elem[t+1].key:=k;i:=s; while (st.Elem[i].Key< >k) Do i:=i+1; st.Elem[t+1]:=st.Elem[0]; if i< >t+1 then Return(i) else Return(0); ] End;
North China Electric Power University I 三种查找方法的比较: 就平均查找长度而言,折半查找最小,分块查找次 之,顺序查找最大。 就表的结构而言,顺序查找对有序表和无序表均 可应用,折半查找仅适用有序表,而分块查找要求表 中数据是分块有序的,即需要把表分成若干块,块与 块之间的记录按关键字有序。 就表的存储结构而言,顺序查找和分块查找对两 种存储结构一向量和链表均适用,而折半查找只适用 于以向量做存储结构的的表,这就要求表中的元素基 本不变,否则,当进行插入和删除运算时为保持表的 有序性,便要移动元素,这在一定程度上降低折半查 找的效率
North China Electric Power University 三种查找方法的比较: 就平均查找长度而言，折半查找最小，分块查找次 之，顺序查找最大。 就表的结构而言，顺序查找对有序表和无序表均 可应用，折半查找仅适用有序表，而分块查找要求表 中数据是分块有序的，即需要把表分成若干块，块与 块之间的记录按关键字有序。 就表的存储结构而言，顺序查找和分块查找对两 种存储结构--向量和链表均适用，而折半查找只适用 于以向量做存储结构的的表，这就要求表中的元素基 本不变，否则，当进行插入和删除运算时为保持表的 有序性，便要移动元素，这在一定程度上降低折半查 找的效率
North China Electric Power University I ★动态查找森 二叉排序树:或者是一棵空树,或者是具有下列 性质的二叉树:1)若它的左子树不空,则它的左 子树上所有结点的值均小于根结点的值;2)若它 的右子树不为空,则它的右子树上所有结点的值 均大于或等于它的根结点的值;3)它的左、右子 树均为二叉排序树 二叉排序树的构造方法 设R={R1,R2,…,Rn}为一数列,按下面的原则建立二叉树: )令R1为二叉树的根; 2)若R2<R1,则令R为R1的左子树的根结点,否则令R2为 R1的右子树的根结点; 3)对R3,R4,…Rn重复上述步骤2);
★ 动态查找表 二叉排序树：或者是一棵空树，或者是具有下列 性质的二叉树：1)若它的左子树不空，则它的左 子树上所有结点的值均小于根结点的值；2)若它 的右子树不为空，则它的右子树上所有结点的值 均大于或等于它的根结点的值；3)它的左、右子 树均为二叉排序树。 North China Electric Power University 二叉排序树的构造方法： 设R={R1,R2,…,Rn}为一数列,按下面的原则建立二叉树： 1)令R1为二叉树的根； 2)若R2<R1，则令R2为R1的左子树的根结点，否则令R2为 R1的右子树的根结点； 3)对R3,R4,…Rn重复上述步骤2)；