ch08-查找.

第8章查找本章要点：查找分类线性查找的种类和查找方法树型查找的种类和查找方法二叉排序树的查找及效率分析哈希表的构造方法和查找方法。8.1查找的基本概念查找表（列表）：是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系．因此查找表是一种非常灵便的数据结构。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。8.1查找的基本概念（续）查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。8.1查找的基本概念（续）•对查找表经常进行的操作有：•(1)查询某个“特定的”数据元素是否在查找表中；•(2)检索某个“特定的”数据元素的各种属性；•(3)在查找表中插入一个数据元素；•(4)从查找表个删去某个数据元素。8.1查找的基本概念（续）静态查找表若对查找表只作前两种统称为“查找”的操作，则称此类查找表为静态查找表。动态查找表若在查找过程中有插入查或删除某个数据元素、既允许表中元素有变化，则称此类表为动态查找表。8.1查找的基本概念（续）平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数（的期望值），称为查找算法在查找成功时的平均查找长度。对于长度为n的查找表，查找成功时的平均查找长度为：niiinncpcpcpcpASL12211其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。8.1查找的基本概念（续）查找方法的分类HASH(哈希)查找法比较式查找法1、基于线性表的查找法2、基于树的查找法计算式查找法8.2基于线性表查找基于线性表的查找具体可分为：顺序查找折半查找分块查找。顺序查找的特点是：用所给的关键字与线性表中各个元素的关键字逐个比较，直到成功或失败。存储结构既可以是顺序存储结构，也可以是链式存储结构，通常采用顺序存储结构。8.2基于线性表查找（续）顺序存储结构有关数据类型的定义如下：#defineMAXSIZE100typedefstruct{keytypekey；/*关键字项*/otherelemtypeotheritem；/*另外的数据项*/}rcdtype；typedefstruct{rcdtyper[MAXSIZE+1]；/*r[0]可用作哨兵单元或空闲*/intlength；/*顺序表长度*/}Seqlist；顺序表的查找（SequentialSearch)适用于顺序存储和链表存储的记录表。从表的任一端开始逐个与给定值相比较，若相等，则查找成功。返回值为该记录在表中的位置序号；若超出界限，则查找失败。返回值为零。适用于顺序存储与链表存储。8.2.1顺序查找458.2.1顺序查找（续）算法一：采用监视哨的方法，将给定的关键字k放到数组中下标为０的位置intSearch_seq(SeqlistL,keytypekey)/*在表L中顺序查找关键字为key的元素，查找成功返回元素位置，否则返回值为0*/{L.r[0].key=key；/*将待查的关键字放在表的下标为０的位置上,设个监视哨*/for(i=L.length；L.r[i].key!=key；--i)；/*从表的尾部开始向头部方向逐个比较*/returni；/*当i为０时，说明没有与给定k值相同的元素*/}4518238764945225077设key=450123456789不等查找成功458.2.1顺序查找（续）算法二：从线性表的第一个位置开始查找，查找成功返回元素的位置，否则返回0。intSearch_seq1(SeqlistL,keytypekey){i=1；/*从表的头部开始向尾部方向逐个比较*/while(i=L.length&&L.r[i].key!=key)++i；if(iL.length)return0；/*查找失败*/returni；}18238764945225077设key=450123456789不等查找成功8.2.1顺序查找（续）设n=L.length，则顺序查找的平均查找长度为：nnpppnnpASL1212)1(niniiininncpASL1121)1(1假设每个记录的查找概率相等，即，查找第i个数据元素时需进行n-i+1次比较，即ci=n-i+1。则在等概率情况下顺序查找的平均查找长度为：8.2.2折半查找折半查找又称二分查找(BinarySearch)，折半查找对待查的线性表有两个要求：(1)必须采取顺序存储结构；(2)必须按关键字大小排序的有序表。二分查找过程：取表的中间记录关键字与查找key进行比较，三种情况：相等：查找成功；小于：要查找的记录只可能在表的后半部分；大于：要查找的记录只可能在表的前半部分。经过—次比较就可将查找范围缩小一半。如此反复进行，直到找到给定关键字key记录，查找成功；当前查找范围为空，查找失败。8.2.2折半查找（续）折半查找的过程可描述为:⑴low＝1；high＝n⑵若low＞high，则查找失败⑶若key＝L.r[mid].key，则查找成功，返回mid若key＜L.r[mid].key，则high＝mid-1，转⑵若key＞L.r[mid].key，则low＝mid+1，转⑵其中，low和high分别指示查找区间的起始位置和相终止位置，mid指示中间元素的位置。2highlowmid8.2.2折半查找（续）例如对关键字为：{14，25，35，40，45，55，62，72，77，92}的顺序存储的有序表进行折半查找，(1)查找关键字key＝55的记录，查找过程如下。1234567891014253540455562727792lowmidhigh∵L.r[mid].key551234567891014253540455562727792Lowmidhigh新查找范围∵L.r[mid].key﹥55新查找范围1234567891014253540455562727792Lowmidhigh∵L.r[mid].key==55查找成功8.2.2折半查找（续）(2)查找关键字key＝50的记录，查找过程如下。1234567891014253540455562727792lowmidhigh∵L.r[mid].key501234567891014253540455562727792Lowmidhigh新查找范围∵L.r[mid].key﹥50新查找范围1234567891014253540455562727792Lowmidhigh∵L.r[mid].key﹥501234567891014253540455562727792HighLowhighlow查找失败8.2.2折半查找（续）折半查找算法如下：intSearch_bin(SeqlistL,keytypekey){low=1;high=L.length;while(low=high){mid=(low+high)/2;if(L.r[mid].key==key)returnmid;/*若找到元素，返回该元素的位置*/if(L.r[mid].key)＞key)high=mid-1;/*改在前半部分查找*/if(L.r[mid].key＜key)low=mid+1;/*改在后半部分查找*/}}8.2.2折半查找（续）5131921375664758088921234567891011lowmidhigh5656lowmidhighlowmidhigh19801980lowhighlowhighlowhighlowhigh5216488216458813377592折半查找演示8.2.2折半查找（续）折半查找21的过程恰好是走过一条从根到结点的路径。进行比较的关键字次数为该路径上的结点数或结点21在判定树上的层数。因此,折半查找在查找成功时进行比较的关键字个数不超过树的深度（log2n+1），所以折半查找在查找成功时与关键字比较的次数最多为log2n+1。5619805216488133775928.2.2折半查找（续）折半查找方法的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。8.2.3分块查找分块查找又称索引顺序查找。这种查找方法中除了表本身以外尚需建立一个索引表。如图所示该表的构造过程是：把要查找的表分成长度相等的几个子表（称为块）。对每个子表建立一个索引项，其中包括两项内容：关键字项（存放该块中最大的关键字）指针项（存放该块中第一个记录的地址）。索引表中关键字递增有序，表中记录可以有序，也可以无序。但块之间一定有序（即后一块中的最小关键字都大于前一块中的最大关键字）。查找过程分两步：首先在索引表中确定待查记录所在的块；然后，在块中按顺序查找。由于索引表中的关键字递增有序，且是顺序存储可以用折半查找。而块中记录只能用顺序查找。4062921583540142555456292777212345678910最大关键字起始地址索引表8.2.3分块查找（续）索引表的结构可描述如下：#defineMAX_INDEX10typedefstruct{keytypemaxkey；intfirst；}indextype,Indexlist[MAX_INDEX+1]；typedefstruct{Indexlist[MAX_INDEX+1]index；/*index[0]作哨兵或空闲*/intlength；/*索引表长度*/}Indexlist；8.2.3分块查找（续）分块顺序查找算法如下：intSearch_blk(SeqlistL，Indexlistid，keytypekey)/*在L中分块顺序查找关键字key的元素，查找成功函数值返回元素在表中的位置*/{for(i=1；i=id.length&&id.index[i].maxkey＜key；++i)；/*顺序查找索引表id*/if(i＞id.length)return0；/*所有表元素查找完，没找到匹配的元素*/low=id.index[i].first；/*确定查找块的首地址*/if(i==id.length)high=L.length；/*待查记录在表的最后一块，确定块的尾地址*/elsehigh=id.index[i+1].first-1；/*确定块的尾地址:为后一块首地址减一的位置*/for(j=low；j=high；++j)if(id.index[j].keymax==key)returnj；/*在第i块中从low到high查找关键字等于key的记录*/return0；}8.2.3分块查找（续）分块查找的效率。一般情况下，为了进行分块查找，可将长为m的线性表均匀地分成n块．每块含有s个记录，即n＝m/s。假设每个记录的查找概率相等，则每块的查找概率为1/n，块内记录的查找概率为1/s，所以有：1)(2121211111ssmsnisinASLsini8.2.3分块查找（续）线性表的三种查找方法中，折半查找的效率最高．但折半查找要求线性表中的记录按关键字有序且必须顺序存贮，这就要求线性表的元素基本不变，否则当在线性表上进行插入，删除操作时，为保持表的有序性必须移动元素。顺序查找适用于链表，插入、删除时不必移动元素。但顺序查找的效率较低。分块查找在插入、删除时，也需要移动元素，且需要维护索引表．至于分块查找是否适用于链表