“监视哨”顺序检索算法 检索成功返回元素位置,检索失败统一返回0; template <class Type> int Seqsearch(vector<Item<Type>*>& datalist, int length, Type k)i int ilength 将第0个元素设为待检索值 data list|0→> setKey(k);∥设监视哨 while(datalist]->getKeyo: =k i-- return i ∥返回元素位置 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 “监视哨”顺序检索算法 ◼ 检索成功返回元素位置，检索失败统一返回0; template <class Type> int SeqSearch(vector<Item<Type>*>& dataList, int length, Type k) { int i=length; //将第0个元素设为待检索值 dataList[0]->setKey (k); //设监视哨 while(dataList[i]->getKey()!=k) i--; return i; //返回元素位置 }
顺序检索性能分析 索成功 设检索每个关键码是等概率的:P1=1/m ∑Pi·(n-i)=-∑(n-i) i=0 i=0 n+1 ∑i= 检索失败 设检索失败时都需要比较n+1次(设置了一个 监视哨) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序检索性能分析 ◼ 检索成功 假设检索每个关键码是等概率的：Pi = 1/n ◼ 检索失败 假设检索失败时都需要比较n+1次（设置了一个 监视哨） Pi n i i n n n i i n i n i n ·( − ) ( ) = − = − = − = = + = 0 1 1 0 1 1 2 1
顺序检索平均检索长度 假设检索成功的概率为,检索失败的概率为 q=(1-p) n+1 ASL= p +q·(n+1) n+1 +(1-p)(n+1) =(n+1)(1-p/2) a(n+1)/2<ASL<(n+1) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序检索平均检索长度 ◼ 假设检索成功的概率为p，检索失败的概率为 q=(1-p) ❑ （n+1)/2 < ASL < (n+1) 1 ASL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p q n n p p n n p + = + + + = + − + = + −
顺序检索优缺点 优点:插入元素可以直接加在表尾 e(1) 缺点:检索时间太长(m) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序检索优缺点 ◼ 优点：插入元素可以直接加在表尾 Θ(1) ◼ 缺点：检索时间太长Θ(n)
10.12二分检索法 将任一元素 datalist]. Key与给定值K比较 口三种情况: (1)Key=K,检索成功,返回 datalist闻 (2)Key>K,若有则一定排在 dataList前 (3)Key<K,若右则一定排在 datalist后 缩小进一步检索的区间 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1.2 二分检索法 ◼ 将任一元素dataList[i] .Key与给定值K比较 ❑ 三种情况： （1）Key = K，检索成功，返回dataList[i] （2）Key > K，若有则一定排在dataList[i]]前 （3）Key < K，若右则一定排在dataList[i]后 ◼ 缩小进一步检索的区间