数据结构第09章查找课件.ppt

第九章查找查找的概念静态查找表动态查找表哈希表查找表是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的数据结构。对查找表的操作:查询某个“特定的”数据元素是否在查找表中;检索某个“特定的”数据元素的各种属性;在查找表中插入一个数据元素;从查找表中删去某个数据元素查找的概念顺序表的查找typedefstruct{ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空intlength;//表的长度}SSTable;以顺序表表示静态查找表,则Search函数可用顺序查找来实现。其顺序存储结构如下:静态查找表i01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数:查找第n个元素:1查找第n-1个元素:2……….查找第1个元素:n查找第i个元素:n+1-i查找失败:n+1查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较。例如:intSearch_Seq(SSTableST,KeyTypekval){//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到,则函数值为//该元素在表中的位置,否则为0。[0].key=kval;//设置“哨兵”for(i=;[i].key!=kval;--i);//从后往前找returni;//找不到时,i为0}//Search_Seq算法描述:顺序查找性能分析查找算法的平均查找长度(AverageSearchLength):为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值。其中:n为表长 Pi为查找表中第i个记录的概率 Ci为找到该记录时,曾和给定值比较过的 关键字的个数顺序表查找的平均查找长度为:对顺序表而言,Ci=n-i+1ASL=nP1+(n-1)P2+…+2Pn-1+Pn在等概率查找的情况下,顺序表的查找算法简单,但平均查找长度较大,不适用于表长较大的查找表。 若以有序表表示静态查找表,则查找过程可以基于“折半”进行。有序表的查找折半查找查找过程:每次将待查记录所在区间缩小一半。适用条件:采用顺序存储结构的有序表。,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。,令 low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k==r[mid].key,查找成功 若k<r[mid].key,则high=mid-1 若k>r[mid].key,则low=mid+1,直至low>high时,查找失败。折半查找算法实现lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例如key=21的查找过程low指示查找区间的下界;high指示查找区间的上界;mid=(low+high)/2。