顺序搜索的平均搜索长度 设数据表中有n个元素，搜索第i个元素的 概率为p:,搜索到第i个元素所需比较次数 为：，则搜索成功的平均搜索长度： ASLc=∑P,·C. (∑p,=1) i=1 i=1 .在顺序搜索并设置“监视哨”情形： ci=i,i=1,,n,因此 ASLsuee=∑p,·i i=1 16
顺序搜索的平均搜索长度 • 设数据表中有 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/,i=1,2,.,n。搜索 成功的平均搜索程度为： 2: ,n+1 i=1 2 2 。 在搜索不成功情形，ASLunsuce=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（1≤达n)个位置 则算法递归深度达i（1~i) 搜索 30 i= 10 20 30 40 50 60 谱 i=2 10 20 30 40 50 60 i=3 10 20 30 40 50 60 18
顺序搜索的递归算法 • 采用递归方法搜索值为 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 /在数据表Element[1.n中搜索其关键码与给定值 /匹配的对象，函数返回其表中位置。参数0C是在 川表中开始搜索的位置 if (loc CurrentSize)return 0; /搜索失败 else if (Elementfloc-1].key ==x)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
基于有序顺序表的折半搜索 。 设个对象存放在一个有序顺序表中，并按其关键 码从小到大排好了序。 折半搜索时，先求位于搜索区间正中的对象的下标 mid,用其关键码与给定值x比较： ◆ Element[mid].key=x,搜索成功； ◆ Element[mid].key>×,把搜索区间缩小 到表的前半部分，继续折半搜索 ； Element[mid].key<x,把搜索区间缩小 到表的后半部分，纟 继续折半搜索。 如果搜索区间已缩小到一个对象，仍未找到想要 搜索的对象，则搜索失败。 20
20 基于有序顺序表的折半搜索 • 设n个对象存放在一个有序顺序表中，并按其关键 码从小到大排好了序。 • 折半搜索时, 先求位于搜索区间正中的对象的下标 mid，用其关键码与给定值x比较: ◆ Element[mid].key == x，搜索成功； ◆ Element[mid].key > x，把搜索区间缩小 到表的前半部分，继续折半搜索； ◆ Element[mid].key < x，把搜索区间缩小 到表的后半部分，继续折半搜索。 • 如果搜索区间已缩小到一个对象，仍未找到想要 搜索的对象，则搜索失败