查找算法平均查找长度的计算方法.doc

查找算法平均查找长度的计算方法()Vol,32,No,4324渤海大学学报自然科学版第卷第期Dec,2011JournalofBohaiUniversity(NaturalScienceEdition)2011年12月查找算法平均查找长度的计算方法312,,伟秦玉平王丽君刘(1,,121013;2,121013;3,,121013)渤海大学工学院辽宁锦州渤海大学大学计算机教学部辽宁锦州渤海大学旅游学院辽宁锦州:,摘要给出了常用查找算法平均查找长度的计算方法包括查找成功和查找失败平均查找,,,长度的计算并通过实例进行了解析便于学习者学习和掌握查找算法同时为应用者选择查找。算法提供依据:;;关键词查找平均查找长度等概率:TP391,41:A:1673,0569(2011)04,0353,05中图分类号文献标识码文章编号0引言。,查找就是在含有若干记录的表中找出关键字值与给定值相同的记录若表中存在这样的记录则查,;,。找成功返回所找到记录的信息或记录在表中的位置否则查找失败返回空记录或空指针查找表有静〔1〕、。。态查找表动态查找表和散列表三种每种查找表都有相应的查找算法一般的查找过程都是对查找,表内的记录按一定顺序进行关键字的比较所以一个查找算法效率的优劣主要取决于查找过程中的比较()。,次数绝对比较次数计算起来比较繁琐所以一般用平均比较次数也称为平均查找长度作为衡量一个〔2〕SL(Averagesearchength)。Al查找算法效率的标准平均查找长度定义为n(1)ASL=pc?iii=1p,n,i。,其中为查找表中记录的个数是在查找表中查找第个记录的概率为了简单起见通常认为查找每i,,p=1/n(1in);ci。个记录的概率是相等的即是查找第个记录所需的比较次数计算给定查找算法??ii3,5〔〕,查找成功或查找失败时的平均查找长度是各类数据结构课程考试常考的题目也是实际中选择查找〔6,8〕,。,方法的依据但所有教材和指导书介绍的都不够全面为此本文给出了常用查找算法查找成功和查,。找失败时平均查找长度的计算方法并通过实例进行解析1常用查找算法平均查找长度的计算方法1,1顺序查找法平均查找长度。:,顺序查找法要求查找表顺序存储或链式存储顺序查找的过程为从表的一端开始依次将表中元素,,;,关键字与给定的值比较如果表中某个记录的关键字值与给定值相等则查找成功若到表的另一端后仍,。然没有找到关键字与给定值相等的记录则查找失败n,,若查找表有个记录且采用顺序查找法查找一个记录则在等概率情况下查找成功时的平均查找长度为:2011,09,30,收稿日期:(2009B145),基金项目辽宁省教育厅高等教育教学改革研究项目:(1965,),,,,,,作者简介秦玉平男博士教授硕士生导师从事计算机教学和科研工作n11n(n+1)n+1ASL=i=×=(2)?nn22i=1,则在等概率情况下查找失败时的平均查找长度为ASL=n+1(3)fail,哨则在等概率情况下查找失败时的平均查找长度为ASL=n(4)fail,,有序表则在等概率情况下查找成功时的平均查找长度与无序表相同查找失败时的平均nnn1ASL=(i+n)=+(5)fail?2n+1n+1=1i平均查找长度,。:要求查找表按顺序存储且表中记录按关键字有序二分查找的过程为首先确定查找表,,;,待查值与查找表中间位置上记