顺序搜索的平均搜索长度 设数据表中有n个元素,搜索第i个元素的 概率为p,搜索到第i个元素所需比较次数 为c,则搜索成功的平均搜索长度: ASL suCC 在顺序搜索并设置“监视哨”情形: i=i,i=1,…,n,因此 ASL suCC ∑P
顺序搜索的平均搜索长度 • 设数据表中有 n 个元素，搜索第 i 个元素的 概率为 pi，搜索到第 i 个元素所需比较次数 为 ci，则搜索成功的平均搜索长度: • 在顺序搜索并设置“监视哨”情形： ci = i , i = 1, , n，因此 16 = = = = n i i n i ASLsucc pi ci p 1 1 . ( 1) ASL p i n i succ i = =1
一般表中各个元素的搜索概率不同,如果按 搜索概率的高低排列表中的元素,从顺序表 的情况可知,能够得到好的平均搜索长度。 在等概率情形,P;=1/mn,i=1,2,,n。搜索 成功的平均搜索程度为: ∑ 1:1m(n+1)n+1 ASL= 2 2 在搜索不成功情形, ASL=n+1 17
• 一般表中各个元素的搜索概率不同，如果按 搜索概率的高低排列表中的元素，从顺序表 的情况可知，能够得到好的平均搜索长度。 • 在等概率情形，pi = 1/n, i = 1, 2, , n。搜索 成功的平均搜索程度为： • 在搜索不成功情形，ASLunsucc= n+1。 . ( ) 1 = + = + = = n i succ n n n n i n ASL 2 1 2 1 1 1 17
顺序搜索的递归算法 采用递归方法搜索值为x的元素,每递归一 层就向待查元素逼近一个位置,直到到达该 元素。假设待查元素在第i(1n)个位置 则算法递归深度达i(1~i)。 搜索30t=1厘1020301405060 递 i=202030405060 归 i=310203040(5060
顺序搜索的递归算法 • 采用递归方法搜索值为 x 的元素，每递归一 层就向待查元素逼近一个位置，直到到达该 元素。假设待查元素在第 i（1≤i≤n）个位置， 则算法递归深度达 i（1～i）。 18 搜索 30 i = 1 10 20 30 40 50 60 i = 2 10 20 30 40 50 60 i = 3 10 20 30 40 50 60 递 归
顺序披索的递归算法 template <class k, class e> int dataList<K. e> SeqSearch(const K X, int loc) const i ∥在数据表 ElementI1.n中搜索其关键码与给定值 匹配的对象,函数返回其表中位置。参数loc是在 表中开始搜索的位置 if (loc Currentsize) return 0; ∥/搜索失败 else if (element[loc-1]key ==) return loc 搜索成功 else return SeqSearch(x, loc+ 1) 递归搜索
顺序搜索的递归算法 template <class K, class E> int dataList<K, E>:: SeqSearch (const K x, int loc) const { //在数据表 Element[1..n] 中搜索其关键码与给定值 //匹配的对象, 函数返回其表中位置。参数 loc 是在 //表中开始搜索的位置 if (loc > CurrentSize) return 0; //搜索失败 else if (Element[loc-1].key == x) return loc; //搜索成功 else return SeqSearch (x, loc+1); //递归搜索 }; 19
基于有序顺序表的折半披索 设n个对象存放在一个有序顺序表中,并按其关键 码从小到大排好了序。 折半搜索时,先求位于搜索区间正中的对象的下标 mid,用其关键码与给定值x比较: ◆ lement[mid].key==x,搜索成功 E| ement[md]key>x,把搜索区间缩小 到表的節半部分,继续折半搜索 E| ement[mid]key<x,把搜索区间缩小 到表的后半部分,继续折半搜索。 如果搜索区间已缩小到一个对象,仍未找到想要 搜索的对象,则搜索失败
20 基于有序顺序表的折半搜索 • 设n个对象存放在一个有序顺序表中，并按其关键 码从小到大排好了序。 • 折半搜索时, 先求位于搜索区间正中的对象的下标 mid，用其关键码与给定值x比较: ◆ Element[mid].key == x，搜索成功； ◆ Element[mid].key > x，把搜索区间缩小 到表的前半部分，继续折半搜索； ◆ Element[mid].key < x，把搜索区间缩小 到表的后半部分，继续折半搜索。 • 如果搜索区间已缩小到一个对象，仍未找到想要 搜索的对象，则搜索失败