数据结构第九章-查找-课件

1数据结构9.1查找的基本概念第9章查找9.2基于线性表的查找法9.3基于树的查找法9.4计算式查找法—哈希表2数据结构9.1查找的基本概念第9章查找查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。3数据结构9.1查找的基本概念第9章查找对查找表常进行的操作:1）查询某个“特定的”数据元素是否在查找表中静态查找动态查找3）在查找表中插入一个数据元素2）检索某个“特定的”数据元素的各种属性4）从查找表中删去某个数据元素4数据结构9.1查找的基本概念第9章查找查找表的分类仅作查询和检索操作静态查找表“不在查找表中”的数据元素插入到查找表中；删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找还可分为：内查找和外查找。5数据结构9.1查找的基本概念第9章查找关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。主关键字：可以识别唯一的一个记录的关键字。次关键字：可以识别若干记录的关键字。6根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（记录）。查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。数据结构9.1查找的基本概念第9章查找7由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说,用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的结构。数据结构9.1查找的基本概念第9章查找8数据结构9.2基于线性表的查找第9章查找①顺序查找②折半查找③分块查找9数据结构9.2基于线性表的查找第9章查找①顺序查找key=64key=6021378819920564568072130123456789101112iiiiiiiiiii结果：查找成功，返回位置7结果：查找不成功intSeqSearch(RecordListl,KeyTypek){inti;i=l.length;while(i=1&&l.r[i].key!=k)i--;if(i=1)return(i);elsereturn(0);}10数据结构9.2基于线性表的查找第9章查找①顺序查找key=64key=60结果：查找成功，返回位置7结果：查找不成功6460intSeqSearch(RecordListl,KeyTypek){inti;l.r[0].key=k;/*标识边界*/i=l.length;while(l.r[i].key!=k)i--;return(i);}技巧：r[0]起到监视哨兵的作用,可免去检查表是否查完,且提高算法的执行效率,但并不是真正的待查找记录。21378819920564568072130123456789101112iiiiiiiiiiii11数据结构9.2基于线性表的查找第9章查找①顺序查找分析查找的时间性能:查找算法的平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值(查找成功时）ASL=∑PiCii=1n其中:n为表长；Pi为查找表中第i个记录的概率，且;Ci为找到该记录时，曾和给定值比较过的关键字的个数。∑Pi=1i=1n12在等概率查找的情况下，顺序表查找成功的平均查找长度为：Pi=1/n对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn9.2基于线性表的查找第9章查找数据结构21111+=+-==n)i(nnASLniSUCC若查找概率无法事先测定，则查找过程采取的改进办法是，附设一个访问频度域或者在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。①顺序查找139.2基于线性表的查找第9章查找数据结构②折半查找顺序查找的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。若以有序表表示查找表，则查找过程可以基于“折半”进行。折半查找只适用于有序表，且限于顺序存储结构149.2基于线性表的查找第9章查找数据结构②折半查找1.首先确定查找表的中间位置；2.然后将待查的值与中间位置的值进行比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。基本思想:159.2基于线性表的查找第9章查找数据结构②折半查找例1:key=64的查找过程如下：lowmidhighlowmidmidhigh①low=11211109876543219288807564563721191305low指示查找区间的下界high=11mid=(1+11)/2=6②keymid指向的记录值low=mid+1=7mid=(7+11)/2=9③keymid指向的记录值high=mid-1=8mid=(8+7)/2=7key=mid所指向的记录值查找成功举例:high指示查找区间的上界mid=(low+high)/270lowmidhighhighlow查找不成功169.2基于线性表的查找第9章查找数据结构②折半查找算法intBinSrch(RecordListl,KeyTypek){intlow=1,high=l.length,mid;while(low=high){mid=(low+high)/2;if(k==l.r[mid].key)returnmid;elseif(kl.r[mid].key)high=mid-1;elselow=mid+1;}return0;}179.2基于线性表的查找第9章查找数据结构②折半查找先看一个具体的情况，假设：n=11判定树i1234567891011Ci3423413423431496710281151.找到有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，2.给定值进行比较的关键字个数恰是该结点在判定树上的层次数。ASLsuccss=(11+22+43+44)/11=33/11ASLunsucc=(44+85)/12=56/12折半查找的判定树是唯一的。平均查找长度189.2基于线性表的查找第9章查找数据结构③分块查找（索引顺序查找）基本思想：1、把线性表分成若干块，每块包含若干个记录，在每一块中记录的存放是任意的，但块与块之间必须排序。（分块有序）2、建立一个索引表，把每块中的最大关键字值及每块的第一个记录在表中的位置和最后一个记录在表中的位置存放在索引项中。19索引表141186106485122keystartfinish01232212138933423824485874498614131211109876543219.2基于线性表的查找第9章查找数据结构③分块查找（索引顺序查找）209.2基于线性表的查找第9章查找数据结构③分块查找（索引顺序查找）索引顺序表的查找过程：1）由索引确定记录所在区间（块）；2）在某个区间（块）内进行顺序查找。注意：索引可以根据查找表的特点来构造。可见，分块查找的过程也是一个“缩小区间”的查找过程。分块查找的平均比较次数=查找“索引”的平均比较次数+查找“块内”的平均比较次数21第9章查找数据结构9.2基于线性表的查找线性表的三种查找方法比较因此，对于不同的表长n、不同的表结构和表存储结构，应采用不同的查找方法。顺序查找折半查找分块查找表的结构有序、无序有序表间有序表的存储顺序、链式顺序顺序、链式ASL最大最小次之22第9章查找数据结构9.3基于树的查找①二叉排序树②二叉平衡树③B-树④B+树⑤键树23第9章查找数据结构9.3基于树的查找①二叉排序树定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：1.若它的左子树不空，则左子树上所有结点的值均小于根结点的值；3.它的左、右子树也都分别是二叉排序树。2.若它的右子树不空，则右子树上所有结点的值均大于根结点的值；24第9章查找数据结构9.3基于树的查找503080209010854035252388例如:是二叉排序树。66不①二叉排序树25第9章查找数据结构9.3基于树的查找①二叉排序树查找算法1.若给定值等于根结点的关键字，则查找成功；2.若给定值小于根结点的关键字，则继续在左子树上进行查找；3.若给定值大于根结点的关键字，则继续在右子树上进行查找。否则，若二叉排序树为空，则查找不成功；在二叉排序树上进行查找，类似折半查找2650308020908540358832第9章查找数据结构9.3基于树的查找例如:二叉排序树查找关键字==50,35,90,953080209085403588325050304035508090①二叉排序树查找算法失败27第9章查找数据结构9.3基于树的查找从上述查找过程可见，在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。——查找成功——查找不成功①二叉排序树查找算法28①二叉排序树插入算法第9章查找数据结构9.3基于树的查找根据动态查找表的定义，“插入”操作在查找不成功时才进行；若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。294830103523402025①二叉排序树插入算法第9章查找数据结构9.3基于树的查找设key=30304830①二叉排序树生成算法第9章查找数据结构9.3基于树的查找例如：设关键字输入顺序为：45，24，53，12，28，9028125324459024，45，53，90，12，28289045122453所以，二叉排序树的形态完全由一个输入序列决定，一个无序序列可以通过构造一棵二叉排序树而得到一个有序序列。314830103523402025二叉排序树特点:1.中序遍历二叉排序树可得到关键字有序序列。2.在构造二叉排序树时，每次插入的新结点都是新的叶子结点，则进行插入时，不必移动其它结点。3.二叉排序树不但拥有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。中序遍历：10，20，23，25，30，35，40，48第9章查找数据结构9.3基于树的查找32①二叉排序树删除算法第9章查找数据结构9.3基于树的查找和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。33①二叉排序树删除算法第9章查找数据结构9.3基于树的查找50802090403588328530（1）被删除的结点是叶子结点例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”34①二叉排序树删除算法第9章查找数据结构9.3基于树的查找50802090403588328530（2）被删除的结点只有左子树或只有右子树例如:被删关键字=4080其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。35①二叉排序树删除算法第9章查找数据结构9.3基于树的查找50802090403588328530（3）被删除的结点既有左子树也有右子树例如:被删关键字=50以其前驱或后继替代之，然后再删除该前驱或后继结点4036数据结构①二叉排序树性能分析第9章查找9.3基于树的查找由关键字序列1，2，3，4，5构造而得的二叉排序树例如：ASLsucc=（1+2+3+4+5）/5=3ASLsucc=（1+22+23）/5=2.24321514352最好情况是与折半查找判定树相同最差情况蜕化为单支树与顺序查找相同3，1，4，2，5371.含有值相同的n个关键字，构造的二叉排序树中，ASL和树的形态有关；2.最差的情况：当关键字有序时,树的深度为n，其平均查找次数为（n+1）/2。3.最好的情况：二