911顺序检索 针对线性表里的所有记录,逐个进 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 等,则检索成功; 否则检索失败(找遍了仍找不到)。 存储:可以顺序、链接 排序要求:无 北京大学信息学院 版权所有,转载或翻印必究 Page 11
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 9.1.1 顺序检索 ◼ 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 ◼ 若某个记录的关键码和给定值比较相 等，则检索成功 ； ◼ 否则检索失败(找遍了仍找不到)。 ◼ 存储：可以顺序、链接 ◼ 排序要求：无
顺序检索算法 /代码9-1顺序检索的存储结构类型定义 template <class Type> class Item t public. Item(Type value): key (value)ts Type getKeyo ireturn keyi /获取关键码值; void setKey (type k key=k;] /设置关键码 private Type keyi /关键码域 string other /其它域 Si vector<Item<Type>k> datalist; 北京大学信息学院 版权所有,转载或翻印必究 Page 12
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 顺序检索算法 ◼ //代码9-1 顺序检索的存储结构类型定义 template <class Type> class Item { public: Item(Type value):key(value) {} Type getKey() {return key;} //获取关键码值; void setKey(Type k){ key=k;} //设置关键码 private: Type key; //关键码域 string other; //其它域 }; vector<Item<Type>*> dataList;
“监视哨”顺序检索算法 ■位置o用来做监视哨位置1到 length用来存储实际元素 检索成功时返回元素位置,检索失败时统一返回0 ∥/代码9-2顺序检索算法 template <class Type> int SeqSearch(vector<Item<Type>*>& dataList int length Typeki int i=length; /将第0个元素设为待检索值 /保证 while循环一定终止 dataList[o]->setKey (ki //从后往前逐个比较 while(dataList[]->getKey ol=k return Ii /返回元素位置 } 北京大学信息学院 版权所有,转载或翻印必究 Page 13
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 “监视哨”顺序检索算法 ◼ 位置0用来做监视哨,位置1到length用来存储实际元素 ◼ 检索成功时返回元素位置，检索失败时统一返回0; //代码9-2 顺序检索算法 template <class Type> int SeqSearch(vector<Item<Type>*>& dataList,int length, Type k) { int i=length; //将第0个元素设为待检索值 // 保证while循环一定终止 dataList[0]->setKey (k); //从后往前逐个比较 while(dataList[i]->getKey()!=k) i--; return i; //返回元素位置 }
顺序检索性能分析 检索成功 假设检索每个关键码是等概率的,Pi=1/n ∑Pi·(n-i)=∑(n-i) i=0 i=0 ÷h+l 2 检索失败 假设检索失败时都需要比较n+1次(设置了一个监视 北京大学信息学院 版权所有,转载或翻印必究 Page 14
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 顺序检索性能分析 ◼ 检索成功 假设检索每个关键码是等概率的，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
顺序检索性能分析(续) 平均检索长度 假设检索成功的概率为p,检索失败的概率为q=(1-p), 则平均检索长度为 n+1 ASL= p +q·(n+1) 2 n+1 +(1-P)(n+1) 2 (n+1)(1-P/2) (n+1)/2<ASL<(n+1) 优缺点 优点:插入元素可以直接加在表尾⊙(1) 缺点:检索时间太长e(n) 北京大学信息学院 版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 顺序检索性能分析（续） ◼ 平均检索长度 假设检索成功的概率为p，检索失败的概率为q=(1-p)， 则平均检索长度为 ◼ （n+1)/2 < ASL < (n+1) ◼ 优缺点 优点：插入元素可以直接加在表尾Θ(1) 缺点：检索时间太长Θ(n) 1 ASL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p q n n p p n n p + = + + + = + − + = + −