平均检索长度的例子 检索算法评估的几个问题 ■假设线性表为(a,bc)检索a、 衡量一个检索算法还需要考虑 b、c的概率分别为04、01、05 算法所需的存储量 顺序检索算法的平均检索长度为 n算法的复杂性 04×1+01×2+05×3=2.1 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 攻大_息单 有,命叠 张铭 叔省。斩就即究 9.1基于线性表的检索 9.1.1顺序检索 1.1顺序检索 ■针对线性表里的所有记录,逐个进 令9.1.2二分检索 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 9.1.3分块检索 等,则检索成功; 否则检索失败(找遍了仍找不到)。 ■存储:可以顺序、链接 排序要求:无 张帖 顺序检索算法 监视哨”顺序检索算法 template <class Type> class Item i 索成功返回元位量,检索失败统一返回0 template <class Type> int Item(Type value): key value)& ector <item Type getKeyo ireturn key}//取关键码值 dataList, int length, Type e void setKey( Type k key=k}//置关键码 private //将第0个元素设为待检值 //关键码域 dataList0]> setKey(k//设监视哨 string other; /其它域 while(dataList[]->getKeyol=k)i--' /返回元素位置 vector<Item<Type>*> dataList 学恤息 权新有,种2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 平均检索长度的例子 „ 假设线性表为（a, b, c）检索a、 b、c的概率分别为0.4、0.1、0.5 „ 顺序检索算法的平均检索长度为 0.4×1+0.1×2+0.5×3 = 2.1 „ 即平均需要2.1次给定值与表中关键 码值的比较才能找到待查元素 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 检索算法评估的几个问题 „ 衡量一个检索算法还需要考虑 „ 算法所需的存储量 „ 算法的复杂性 „ ... 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 9.1 基于线性表的检索 „ 9.1.1 顺序检索 „ 9.1.2 二分检索 „ 9.1.3 分块检索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 9.1.1 顺序检索 „ 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 „ 若某个记录的关键码和给定值比较相 等，则检索成功 ； „ 否则检索失败(找遍了仍找不到)。 „ 存储：可以顺序、链接 „ 排序要求：无 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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; //返回元素位置 }