数据结构,二叉树的搜索ppt课件.ppt

《数据结构,二叉树的搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章查找查找的概念顺序表和线性表方法树索引方法散列法（哈希表）查找表是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。对查找表的操作:查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素查找的概念关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键

2、字能识别若干记录，则称之谓“次关键字”。根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。查找查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度抽象数据类型静态

3、查找表的定义:ADTStaticSearchTable{D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。顺序表的查找数据对象D:顺序表的查找typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空intlength;//表的长度}SSTable;以顺序表表示静态查找表，则Search函数可用顺序查找来实现。其顺序存储结构如下：i01234567891011513192

4、137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：intSearch_Seq(SSTableST,KeyTypekval){//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。ST.elem[0].key=kval;//设置“哨兵”for(i=

5、ST.length;ST.elem[i].key!=kval;--i);//从后往前找returni;//找不到时，i为0}//Search_Seq算法描述：顺序查找性能分析查找算法的平均查找长度(AverageSearchLength)：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。其中:n为表长Pi为查找表中第i个记录的概率Ci为找到该记录时，曾和给定值比较过的关键字的个数顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1

6、+Pn在等概率查找的情况下，在不等概率查找的情况下，ASLss在Pn≥Pn-1≥···≥P2≥P1时取极小值。表中记录按查找概率由小到达重新排列,以提高查找效率。若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。有序表的查找折半查找查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。1.设表长

7、为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。2.初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若kr[mid].key，则low=mid+13.重复上述操作，直至low>high时，查找失败。折半查找算法实现lowhighmid例1234567891011513192137566475808892找211

8、234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例如key=21的查找过程low指示查找区间的下界;high指示查找区间的上界;mid=(low+high)/2。例key=70的查找过程1234567891011513192137566475808892lowhighmid找70123456789101151319213756647580889