第8章查找关键字：数据元素中某个数据项的值，用它可以标识一个数据元素。主关键字：可以唯一地标识一个记录的关键字，称为主关键字。次关键字：用以识别若干个记录的关键字，称为次关键字。查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素的过程，称为查找。若表中存在这样的一个记录，则称为查找成功。若表中不存在这样一个记录，则称为查找不成功。可采用顺序存储结构表示静态查找表：typedefstructlinear_list{intkey;//数据元素intn;//表长度};顺序表的查找顺序查找的方法：首先从表中第n个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直到第一个记录，其关键字和给定值比较都不等，则表明表中没有所查的记录，查找不成功。解：实现该查找过程的方法如前所述，具体的程序如下：intserial_search(list,k)structlinear_listlist[];intk;{inti;i=n-1;//从尾部开始查找while(i>=0){if(list[i].key!=k)i=i-1;elsebreak;}return(i+1);}顺序查找的性能分析：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度（AverageSearchLength－ASL），定义为：在顺序查找算法中，若顺序表的长度为n,每个记录的查找概率分别为P1,P2,….,Pn,则其平均查找长度为：ASL=nP1+(n-1)P2+….+2Pn-1+Pn若假设每个数据元素的查找概率相同，则其平均查找长度为：折半查找(二分查找)－－在有序表中查找，效率高05，13，19，21，37，56，64，75，80，88，92上面的查找过程可用下面的程序实现：intbi_search(list,k)structlinear_listlist[];intk;{intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(k==list[mid].key)returnmid;elseif(key<list[mid].key)high=mid-1;elselow=mid+1;}return0;//未找到返回0}二叉树的性质上述的查找过程可用下面的二叉树来描述。树中每个结点表示一个记录，结点中的值为该记录在表中的位置，通常这个描述查找过程的二叉树为判定树。在该树中，和给定值进行比较的次数恰为该结点在判定树中的层次。因此折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为log2n+1，所以折半查找法在查找成功时和给定值进行比较的关键字个数至多为log2n+1。此方法只能适用于有序表，且限于顺序存储结构。比较次数最多：log2n+1不超过判定树的深度查找一个记录的时间复杂度：O(log2n)分块查找（前提：元素分块有序）分块查找又称索引顺序查找，除表本身外需建立一个索引表，内容包括关键字项和指针项。索引表按关键字有序，则表或者有序或者分块有序。分块有序是指第二个子表中所有记录的关键字均大于第一个子表中的最大关键字。性能分析：ASL=Lb+Lw，Lb为确定块的平均查找长度；Lw为块内查找次数。表长为n，每块长为L。若顺序查找:ASL=Lb+Lw=(n/L+1)/2+(L+1)/2=(n/L+L)/2+1若折半查找:ASL=Lb+Lw=[log2(n/L)]+1+(L+1)/2≈log2(n/L+1)+L/2三种查找方法比较动态查找表动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则在查找成功后返回，否则插入关键字等于key的记录。二叉排序树（二叉查找树）－树表查找的典型二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3、它的左、右子树也分别为二叉排序树。例如下面的树即为二叉排序树。例：将序列（45，24，53，12，90）构造成为二叉排序树；并求ASL。解：将上述序列构造成二叉排序树的过程如下二叉排序树的查找方法：类似于折半查找，当二叉排序树不空时，首先将给定值k与根结点的关键字比较，若相等，则查找成功；否则依k的大小在左子树或右子树上查找。程序实现：typedefstructBSTno