数据结构 第8章VIP免费

第8章查找8.1查找的基本概念8.2基于线性表的查找法8.3基于树的查找法8.4计算式查找法——哈希法8.1查找的基本概念列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。显然，查找算法中涉及到三类参量：①查找对象K（找什么）；②查找范围L（在哪找）；③K在L中的位置（查找的结果）。其中①、②为输入参量，③为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为：niiinnCPCPCPCPASL12211其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH（哈希）查找法。8.2基于线性表的查找法8.2.1顺序查找法顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。下面给出顺序结构有关数据类型的定义：＃defineLIST_SIZE20typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;typedefstruct{RecordTyper［LIST-SIZE+1］;/*r［0］为工作单元*/intlength;}RecordList;基于顺序结构的算法如下：intSeqSearch（RecordListL,KeyTypek）{L.r［0］.key=k;i=l.length;while(L.r［i］.key!=k)i--;return（i）;}【算法8.1设置监视哨的顺序查找法】不用监视哨的算法如下：intSeqSearch（RecordListL,KeyTypek）/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{L.r［0］.key=k;i=l.length;while(i>=1&&L.r［i］.key!=k)i--;if(i>=1)return（i）elsereturn(0);}【算法8.2不设置监视哨的顺序查找法】其中，循环条件i>=1判断查找是否越界。利用监视哨可省去这个条件，从而提高查找效率。下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：niniiniiininnCnCPASL111)1(21)1(118.2.2折半查找法折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到查找成功或查找不成功。lowhighmid1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185210741936判定树：1234567891011513192137566475808892图8.1折半查找示意折半查找的算法如下：intBinSrch...