61数据结构C语言描述第8章

第8章查找第8章查找8.1查找的基本概念　8.2基于线性表的查找法8.3基于树的查找法8.4计算式查找法——哈希法第8章查找8.1查找的基本概念列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。　关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。第8章查找查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。显然，查找算法中涉及到三类参量：①查找对象K（找什么）；②查找范围L（在哪找）；③K在L中的位置（查找的结果）。其中①、②为输入参量，③为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。第8章查找平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为：niiinnCPCPCPCPASL12211其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。第8章查找查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH（哈希）查找法。第8章查找8.2基于线性表的查找法8.2.1顺序查找法　顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。下面给出顺序结构有关数据类型的定义：＃defineLIST　-SIZE20　typedefstruct{　KeyTypekey;第8章查找OtherTypeother　-data;　}RecordType;　typedefstruct{　RecordTyper［LIST-SIZE+1］;/*r［0］为工作单元*/intlength;　}RecordList;第8章查找基于顺序结构的算法如下：　intSeqSearch（RecordListl,KeyTypek）　/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/　{l.r［0］.key=k;i=l.length;　while(l.r［i］.key![KG-*2]=k)i--;　return（i）;　}　第8章查找【算法8.1设置监视哨的顺序查找法】其中l.r［0］称为监视哨，可以起到防止越界的作用。不用监视哨的算法如下：　intSeqSearch（RecordListl,KeyTypek）　/*不用监视哨法，在顺序表中查找关键字等于k的元素*/　{　l.r［0］.key=k;i=l.length;　while(i=1&&l.r［i］.key![KG-*2]=k)i--;　if(i=1)return（i）　elsereturn(0);　}第8章查找【算法8.2不设置监视哨的顺序查找法】其中，循环条件i=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。　　下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：niniiniiininnCnCPASL111)1(21)1(11第8章查找8.2.2折半查找法折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。图8.1给出了用折半查找法查找12、50的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。第8章查找6121518222528354658601234567891011low＝1mid＝6high＝116121518222528354658601234567891011low＝1mid＝3high＝56121518222528354658601234567891011low＝1mid＝1high＝26121518222528354658601234567891011low＝2mid＝2high＝2(a)用折半查找法查找12的过程6121518222528354658601234567891011low＝1mid＝6high＝116121518222528354658601234567891011low＝7mid＝9high＝116121518222528354658601234567891011low＝10mid＝10high＝116121518222528354658601234567891011low＝10high＝9(b)用折半查找法查找50的过程图8.1折半查找示意第8章查找折半查找的算法如下：intBinSrch（SqListl,KeyTypek）　/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/　{　low=1;high=l.length;/*置区间初值*/　while(low=high)　第8章查找{　mid=(low+high)/2;　if(k==l.r［mid］.key)return（mid）;/*找到待查元素*/　elseif(kl.r［mid］.key)high=mid-1;/*未找到，则继续在前半区间进行查找*/　elselow=mid+1;/*继续在后半区间进行查找*/　}　return(0);　}第8章查找【算法8.3折半查找法】折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应的结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数昀多不超过判定树的深度。第8章查找由于判定树的叶子结点所在层次之差昀多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为［log2n］+1。这样，折半查找成功时，关键字比较次数昀多不超过［log2n］+1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功时，关键字比较次数昀多也不超过判定树的深度［log2n］+1。为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为　njjniiibsnnnjnCPASL12111)1(log121第8章查找8.2.3分块查找法分块查找法要求将列表组织成以下索引顺序结构：　·首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，昀后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。　·构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的昀大关键字（或昀小关键字）。索引表按关键字有序排列。　图8.2所示为一个索引顺序表。其中包括三个块，第一个块的起始地址为0，块内昀大关键字为25；第二个块的起始地址为5，块内昀大关键字为58；第三个块的起始地址为10，块内昀大关键字为88。　第8章查找图8.2分块查找法示意255888索引表各块内的昀大关键字各块的起始地址1814122582832453658608871列表0123456789101112第8章查找分块查找的基本过程如下：　(1)首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。　(2)进一步用顺序查找法，在相应块内查找关键字为K的元素。例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为25＜36≤58，所以36在第二个块中，进一步在第二个块中顺序查找，昀后在8号单元中找到36。第8章查找分块查找的平均查找长度由两部分构成，即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度为LW。　　　ASLbs=LB+LW　　假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有21,21111siLbjbLsibjWB第8章查找12sbLLASLWBbs将代入,得snb121ssnASLbs若用折半查找法确定待查元素所在的块，则有1)1(log2bLB21log211)1(log22ssnsbASLbs第8章查找8.3基于树的查找法基于树的查找法又称为树表查找法，是将待查表组织成特定树的形式并在树结构上实现查找的方法，主要包括二叉排序树、平衡二叉排序树和B树等。8.3.1二叉排序树二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；　（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；　（3）它的左右子树也分别为二叉排序树。第8章查找图8.3二叉排序树526148973CAOZHAODINGCHENWANG(a)二叉排序树示例1(b)二叉排序树示例2(根据字符ASCⅡ码的大小)第8章查找在下面讨论的二叉排序树的操作中，使用二叉链表作为存储结构，其结点结构说明如下：typedefstructnode　{KeyTypekey;/*关键字的值*/　structnode*lchild,*rchild;/*左右指针*/　}BSTNode,*BSTree;第8章查找1.二叉排序树的插入和生成已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行：①若二叉排序树是空树，则key成为二叉排序树的根；②若二叉排序树非空，则将key与二叉排序树的根进行比较，如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插入左子树；如果key的值大于根结点的值，则将key插入右子树。相应的递归算法如下：第8章查找voidInsertBST(BSTree*bst,KeyTypekey)　/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/　{BSTrees;　if(*bst==NULL)/*递归结束条件*/　{　s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/　s-key=key;　s-lchild=NULL;s-rchild=NULL;　*bst=s;　}　elseif(key(*bst)-key)　InsertBST(&((*bst)-lchild),key);/*将s插入左子树*/　elseif(key(*bst)-key)　Ins