数据结构讲义第九章第九章查找目录8、查找方案的评价查找方1）查找速度2）占用存储空间多少3）算法本身复杂程度4）平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度。9.2静态查找表抽象数据类型的定义：书P216页9.2.1顺序表的查找（我们主要介绍在顺序存储结构上的实现，在链式存储结构上的实现请同学们自己考虑）。1、存储结构的描述typedefstruct{ElemType*elem;intlength;}SSTable;2、查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定的值相等则查找成功；反之，若一直没有记录的关键字和给定值相等，则查找失败。算法1：intsearch_seq(SSTableST,KeyTypekey){i=1;n=ST.length;while((i<=n)&&(ST.elem[i].key!=key))i++;if(i>n)returnERROR;//没找到elsereturni;}i算法2：intsearch_seq(SSTableST,KeyTypekey){ST.elem[0].key=key;//设立哨兵i=ST.length;while(ST.elem[i].key!=key)i--;returni;//未找到则返回值为0}由于查找不成功时和给定值比较的次数为n+1，若查找成功与查找不成功的可能性相同，对每个记录的查找概率也相等，则：算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若k<r[mid].key，则high=mid-1若k>r[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败算法：intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key<key)low=mid+1;elsehigh=mid-1;}return0;}low例1234567891011算法评价判定树：描述查找过程的二叉树叫判定树。有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数（无论成功与否）最多不超过其判定树的深度。9.2.3分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域。建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。算法描述123456789101112131415161718分块查找方法评价各种静态查找方法比较9.3动态查找表动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。动态查找表的抽象数据类型定义参见书P226页。9.3.1二叉排序树和平衡二叉树1、二叉排序树（BinarySortTree）二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树了分别为二叉排序树。2、二叉排序树的查找BiTreeSearchBST(BiTreeT,KeyTypekey){//在根为T的二叉排序树中递归地查找关键字等于//key的记录，若找到则返回指向该数据元素的指//针，否则返回空指针。if（(!T)||(T->data.key==key))return(T);elseif(key<T->data.key)return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild.key));}//SearchBST算法9.5a3、二叉排序树的插入如删除1）插入前面讲了二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的