第11章查找11.1查找的基本概念查找技术（分类一）静态查找：不涉及插入和删除操作的查找。静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作；动态查找：涉及插入和删除操作的查找。动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。查找技术（分类二）内查找：查找过程不涉及内外存的交互，即整个查找过程都在内存中进行。外查找：查找过程涉及内外存的交互，即在查找过程中需要访问外存。注意：本章讨论的主要是内查找的各种查找技术。查找算法的性能查找算法时间性能通过关键码的比较次数来度量。平均查找长度：查找算法进行的关键码的比较次数的数学期望值。计算公式为：结论：关键码的比较次数与哪些因素有关呢？(1)问题规模n；(2)查找频率p。查找频率与算法无关，取决于具体应用。通常假设pi是已知的。(3)待查关键码在查找集合中的位置；(4)算法；11.2主要查找方法简介11.2静态查找表一、顺序查找（Sequentialsearch）基本思想：从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后未找到关键字等于K的结点，则查找失败。回顾顺序表的查找过程：算法实现：intSeqSearch(sqListL,KeyTypekey){inti;for(i=L.len;i>=1&&L.data[i].key!=key;i--);if(i>=1)returni;elsereturn0;}改进算法：使用下标为0的地址为监视哨算法实现：intSeqSearch(SqListL,KeyTypekey){intj;L.data[0].key=key;//设置哨兵for(j=L.len;L.data[j].key!=key;j--);returnj;}结论二、二分查找使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。折半查找基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。例：查找值为14的记录的过程：例：查找值为22的记录的过程：算法思想与实现（4）重复步骤（2）、（3）直到查找成功或查找范围空low>high），即查找失败为止。（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。intBinsrch(SqListL,KeyTypekey){low=1;high=L.len;//置区间初值while(low<=high){mid=(low+high)/2;//找到待查元素if(key==L.data[mid].key)returnmid;elseif(key<L.data[mid].key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称二叉判定树。判定树的构造方法⑴当n=0时，折半查找判定树为空；⑵当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1]~r[n]相对应的折半查找判定树。具有n个结点的折半查找判定树的深度为设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。试画出对其进行折半搜索时的二叉判定树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。三、分块查找－索引顺序表查找查找方法比较9.3动态查找B-树（2）对树中关键字个数的要求：所有的非终端结点中包含以下信息(n，A0，K1，A1，K2，…，Kn，An)。其中，n为关键字个数，m/21≤n≤m1；Ki（i=1,2,…,n）为关键字，且Ki<Ki+1；Ai为指向子树根结点的指针（i=0,1,…,n），且指针Ai－1所指子树中所有结点的关键字值均小于Ki（i=1,2,…,n），An所指子树中所有结点的关键字值均大于Kn。（3）对叶子结点的要求：所有的叶子结