顺序检索算法 template <class Type> class Item f public: Item(Type value): key(value)t] Type getKey({ return key}//取关键码值; void setKey( Type k)key=k;}//置关键码 private: Type key //关键码域 string other /其它域 Fi vector<Item<Type>*> datalist 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 11
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 顺序检索算法 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;
“监视哨”顺序检索算法 检索成功返回元素位置,检索失败统一返回0 template <class Type> int SeqSearch(vector<Item<Type>*k>& dataList int length, Type k) int i=length; /将第0个元素设为待检索值 dataList[O]-> setKey(k);//设监视哨 while(dataList[i]->getKey ol=ki-i return /返回元素位置 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 12
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 “监视哨”顺序检索算法 检索成功返回元素位置，检索失败统一返回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; //返回元素位置 }
顺序检索性能分析 检索成功 假设检索每个关键码是等概率的,Pi=1/n 12 ∑= Pi·(n-i)=-∑(n-i) 0 0 n+1 2 检索失败 假设检索失败时都需要比较n+1次(设置了一个 监视哨) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 13
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 顺序检索性能分析 检索成功 假设检索每个关键码是等概率的，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 2 +q·(n+1) n+1 p 2 +(1-p)(n+1) =(n+1)(1-p/2) (n+1)/2<ASL<(n+1) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 14
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 顺序检索平均检索长度 假设检索成功的概率为p，检索失败的概率 为q=(1-p) （n+1)/2 < ASL < (n+1) 1 A SL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p qn n p pn n p + = ⋅ +⋅ + + = ⋅ +− + =+ −
顺序检索优缺点 优点:插入元素可以直接 加在表尾⊙(1) 缺点:检索时间太长⊙(n) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 15
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 顺序检索优缺点 优点：插入元素可以直接 加在表尾Θ(1) 缺点：检索时间太长Θ(n)