数据结构PPT资料.ppt

《数据结构PPT资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第7章　查找7.1查找的基本概念查找表:由同一类型的数据元素（或记录）构成的集合静态查找表：对查找表没有修改操作动态查找表：对查找表具有修改操作关键字记录中某个数据项的值，可用来识别一个记录主关键字：唯一标识数据元素次关键字：可以标识若干个数据元素是一种数据结构关键字的平均比较次数，也称平均搜索长度ASL(AverageSearchLength)n：记录的个数pi：查找第i个记录的概率(通常认为pi=1/n)ci：找到第i个记录所需的比较次数查找算法的评价指标7.2线性表的查找一、顺序查找（线性查找）二

2、、折半查找（二分或对分查找）顺序查找应用范围：顺序表或线性链表表示的静态查找表表内元素之间无序typedefstruct{ElemType*R;//表基址intlength;//表长}SSTable;顺序表的表示intLocateELem(SqListL,ElemTypee){for(i=0;i

3、章在顺序表L中查找值为e的数据元素intSearch_Seq(SSTableST,KeyTypekey){//若成功返回其位置信息，否则返回0ST.R[0].key=key;for(i=ST.length;ST.R[i].key!=key;--i);//不用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;}空间复杂度：一个辅助空间。时间复杂度：1)查找成功时的平均查找长度设表中各记录查找概率相等ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功时的平均查

4、找长度ASLf=n+1顺序查找的性能分析算法简单，对表结构无任何要求（顺序和链式）n很大时查找效率较低改进措施：非等概率查找时，可按照查找概率进行排序。顺序查找算法有特点n个数存在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度ASL不同。练习:判断对错查找概率相等时，ASL相同；查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其ASL要比无序表ASL小。lowhighmid1234567891011513192137566475808892找21123456

5、7891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid折半查找若k==R[mid].key，查找成功若kR[mid].key，则low=mid+11234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011

6、513192137566475808892lowhighmid若k==R[mid].key，查找成功若kR[mid].key，则low=mid+11234567891011513192137566475808892lowhigh1234567891011513192137566475808892lowhighmid直至low>high时，查找失败折半查找（非递归算法）设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始

7、时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==R[mid].key，查找成功若kR[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败折半查找（递归算法）intSearch_Bin(SSTableST,keyTypekey,intlow,inthigh){if(low>high)return0;//查找不到时返回0mid=(low+high)/2;if(key==ST.e

8、lem[mid].key)returnmid;elseif(key小于ST.elem[mid].key)……..//递归else…….//递归}-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点内结点><=折半查找的性能分析－判定树1234567891011513192137566475808892若所有结点的空指针域设置