平均检索长度的例子 假设线性表为(a,b,c)检索a、b、c的概 率分别为04、0.1、0.5 口顺序检索算法的平均检索长度为 0.4×1+0.1×2+05×3=2.1 口即平均需要21次给定值与表中关键码值的 比较才能找到待查元素 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6 平均检索长度的例子 ◼ 假设线性表为（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次给定值与表中关键码值的 比较才能找到待查元素
检索算法评估的几个问题 衡量一个检索算法还需要考虑 口算法所需的存储量 口算法的复杂性 “十一五”国家级规划教材。铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,208.6。7
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7 检索算法评估的几个问题 ◼ 衡量一个检索算法还需要考虑 ❑ 算法所需的存储量 ❑ 算法的复杂性 ❑
10.1基于线性表的检索 1011顺序检索 中1012二分检索 1013分块检索 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1 基于线性表的检索 ◼ 10.1.1 顺序检索 ◼ 10.1.2 二分检索 ◼ 10.1.3 分块检索
10.11顺序检索 针对线性表里的所有记录,逐个进行 关键码和给定值的比较。 口若某个记录的关键码和给定值比较相等, 则检索成功; 口否则检索失败(找遍了仍找不到)。 存储:可以顺序、链接 排序要求:无 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1.1 顺序检索 ◼ 针对线性表里的所有记录，逐个进行 关键码和给定值的比较 。 ❑ 若某个记录的关键码和给定值比较相等， 则检索成功 ； ❑ 否则检索失败(找遍了仍找不到)。 ◼ 存储：可以顺序、链接 ◼ 排序要求：无
顺序检索算法 template <class Type> class Item i private Type key; ∥关键码域 其它域 public: Item(Type value): key (value)t ype getKeyo{ return key;}∥取关键码值 void setKey( Type k){key=k;}∥置关键码 vector<Item<Type>*> datalist “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序检索算法 template <class Type> class Item { private: Type key; //关键码域 //… //其它域 public: Item(Type value):key(value) {} Type getKey() {return key;} //取关键码值 void setKey(Type k){ key=k;} //置关键码 }; vector<Item<Type>*> dataList;