资源描述：
《有序顺序表斐波那契搜索-东南大学计算机科学与工程学院ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、东南大学计算机学院方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第七章搜索结构本章主要内容搜索的概念静态搜索结构顺序搜索有序顺序表顺序搜索折半搜索斐波那契搜索二叉搜索树2搜索的概念在数据集合中寻找满足某种条件的数据元素搜索可能成功也可能不成功可唯一标识一个元素的属性称为关键字(key)基于关键字的搜索结果是唯一的基于其他属性的搜索结果可能不唯一衡量搜索算法时间效率的标准平均比较次数，或平均搜索长度(ASL)3顺序搜索从表头(或尾)开始，依次用各对象的关键字与给定值x比较若值相等
2、，搜索成功，返回下标若整个表都未找到，搜索失败pi:搜索第i个元素概率ci:搜索到第i个元素所需比较次数pi=1/nci=i+1ASLunsucc=n+1搜索不成功的平均搜索长度搜索成功的平均搜索长度：…n个元素4有序顺序表顺序搜索从表头(或尾)开始，依次用各对象的关键字与给定值x比较若值相等，搜索成功，返回下标若x比关键字大时，搜索失败搜索成功的平均搜索长度：搜索不成功的平均搜索长度…n个元素，n+1个空档5有序顺序表折半搜索low=0,high=n-1,mid=(low+high)/2x先和m
3、id元素比较若相等，搜索成功，返回下标若x更小，继续在前半部分搜索high=mid-1,mid=(low+high)/2若x更大，继续在后半部分搜索low=mid+1,mid=(low+high)/2搜索40lowmidhigh102030405060012345lowmidhigh102030405060012345lowmidhigh10203040506001234540>3040<5040=40搜索成功6有序顺序表折半搜索low=0,high=n-1,mid=(low+high)/2x先和
4、mid元素比较若相等，搜索成功，返回下标若x更小，继续在前半部分搜索high=mid-1,mid=(low+high)/2若x更大，继续在后半部分搜索low=mid+1,mid=(low+high)/2搜索25lowmidhigh102030405060012345lowmidhigh102030405060012345lowmidhigh10203040506001234525<3025>1025>20lowmidhigh102030405060012345low>high，搜索失败7有序顺序表
5、折半搜索折半搜索构造的判定树设满二叉树n=2h-1则有2h=n+1，h=log2(n+1)平均搜索长度50======30<<<<<<>>>>>>20406010错位相减法8有序顺序表斐波那契搜索F(n)=n,F(n-1)+F(n-2),n=0,1n≥20112350123458132134558967891011nF(n)9有序顺序表斐波那契搜索low=1,high=n,mid=F(x-1),F(x)是最小的≥n的斐波那契数x先和mid元素比较若相等，搜索成功，返回下标若x更小，继续在前半部分搜
6、索high=mid-1,mid=low+F(x-2)-1若x更大，继续在后半部分搜索low=mid+1,mid=low+F(x-3)-10112350123458132134558967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索2510有序顺序表斐波那契搜索low=1,high=n,mid=F(x-1),F(x)是最小的≥n的斐波那契数x先和mid元素比较若相等，搜索成功，返回下标若x更小，继续在前半部分搜索high
7、=mid-1,mid=low+F(x-2)-1若x更大，继续在后半部分搜索low=mid+1,mid=low+F(x-3)-10112350123458132134558967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索5511二叉搜索树二叉搜索树的概念或者是空树或者具有以下性质每个结点都有一个关键字(key)左子树上所有结点的key小于根结点的key右子树上所有结点的key大于根结点的key左子树和右子树也是二叉搜索
8、树12二叉搜索树搜索x操作从根开始搜索x若当前结点为空，则搜索失败，否则x小于当前结点key，在左子树搜索x大于当前结点key，在右子树搜索53658781947809452317搜索2313二叉搜索树搜索x操作从根开始搜索x若当前结点为空，则搜索失败，否则x小于当前结点key，在左子树搜索x大于当前结点key，在右子树搜索53658781947809452317搜索9414二叉搜索树插入x操作从根开始搜索x，若存在，放弃否则搜索到叶子结点时x小于叶子结点key，作为叶子结点左孩子
