算法与数据结构ppt课件.ppt

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

1、第九章.查找（Chapter9.Searching)查找运算是计算机中最常用的操作之一。有人统计过，计算机大约有40%的运算是与查找相关的。数据元素（或记录）的某个数据项，能用来标识一个数据元素。若能唯一的标识一个数据元素，则称为主关键字（primarykey），反之则为次关键字（secondarykey）。关键字（key）查找表（searchtable）§9.1静态表的查找查找（searching）根据某个给定的值，在查找表中找寻关键字等于给定值的数据元素（或记录）。若表中存在这样的数据元素，则称查找是成功的，查找结果即为查找到的数据元素；反之则称查找是不成功的，此时查找结果为空

2、。由同一类型的数据元素（或记录）构成的集合。表中的元素基本上是固定的，这类查找表称为静态查找表（staticsearchtable）；若在查找过程中将不存在的元素插入查找表中，则称这类查找表为动态查找表（dynamicsearchtable）。实际查找时，通常将给定值放在第0个记录处，然后从后向前查找，直到找到所查记录为止，找不到则返回结果0。因为记录0像哨兵一样看守着查找表下界，所以不会越界。typedefstruct{keytypekey;......}elemtype;一、无序表的查找：查找表中的各元素（或记录）的关键字的值是无序的。typedefstruct{elemtyp

3、e*elem;intlength;}sstable;intseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].key!=K;i--);returni;}查找表的长度为n：查找性能分析：平均查找长度（averagesearchlength）为了确定记录在查找表中的位置，需与给定值比较的关键字的个数的期望值称为平均查找长度。对含有n个记录的查找表，查找成功时的平均查找长度为：ASL=∑PiCi，其中Pi为查找第i个记录的概率，且∑Pi=1。ni=1i=1n在等概率情况下，顺序查找无序表的平均查找长

4、度为：ASL成功=（n+1)/2和ASL不成功=n+1。二、有序表的查找：查找表中的各元素（或记录）的关键字的值是有序的。这类有序表的查找仍可以用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。在等概率情况下，顺序查找有序表的平均查找长度为：ASL成功=（n+1)/2和ASL不成功=（n+2)/2。有序表的查找比较好的方法是折半查找（binarysearch）：将给定值与中间的记录进行比较，若找到则查找成功；否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一半子表进行折半查找。若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败。in

5、tseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].key>K;i--);if(R.elem[i].key=K)returni;elsereturn0;}intbinsearch(sstableR,keytypeK){low=1;high=R.length;while(low<=high){mid=(low+high)/2;if(R.elem[mid]==K)returnmid;elseif(R.elem[mid]>K)high=mid-1;elselow=mid+1;}return0;}i

6、ntbinsearch(sstableR,intlow,inthigh,keytypeK){if(low>high)return0;mid=(low+high)/2;if(R.elem[mid]==K)returnmid;if(R.elem[mid]>K)returnbinsearch(R,low,mid-1,K);returnbinsearch(R,mid+1,high,K);}查找性能分析：折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过log2n+1。有一组记录的关键字为{1，2，3，

7、4，5，6，7，8}，求其在等概率情况下查找成功的平均查找长度：例：42516378其查找树如左图所示：ASL成功==21/8。1*1+2*2+3*4+4*18有序表的查找也可用其它的查找方法，如费波拉契查找（Fibonaccisearch）。设查找表记录数为某个费波拉契数减一，即n=Fu-1，则可将给定值与第Fu-1个记录比较，若比其小，则在1~Fu-1-1记录间查找，否则在Fu-1+1~Fu-1记录间查找。如下图所示：4251637若有序表的关键字是均匀分布的，则