欢迎来到天天文库
浏览记录
ID:59486630
大小:505.50 KB
页数:44页
时间:2020-09-13
《算法与数据结构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若有序表的关键字是均匀分布的,则
此文档下载收益归作者所有