数据与算法课程讲义（吴及）查找 整理.pdfVIP

内容提要 查找 顺序查找和索引查找 二叉有哪些信誉好的足球投注网站树 散列 数据与算法 2 吴及 电子工程系 查找表  查找表(Search Table)是由同一类型数据元素构成的集合  按关键字(Key)查找 1. 查询某数据元素是否存在 2. 检索某数据元素的各种属性 3. 在查找表中插入一个数据元素 4. 从查找表中删除一个数据元素  查找表的种类 1. 静态查找表 - 仅进行1 ，2两种操作 2. 动态查找表 - 可进行1 ，2 ，3 ，4所有操作 数据与算法 4 吴及 电子工程系 查找的性能分析  平均查找长度：在查找过程中，为确定目标在查找表中的位置，需要进行关 键字比较次数的期望值 = 和分别为第 条记录的查找概率和查找长度  每条记录的查找概率相等  每条记录的查找概率不等  考虑查找不成功的情况  小，查找的性能就越好 数据与算法 5 吴及 电子工程系 顺序查找表  假设每个元素的查找概率相等，则平均查找长度为： = = 1 + 1 = + 1 2  对于长度为线性表，平均来说顺序查找需要进行2次比较  更多考虑  如果每个元素的查找概率不等  对于长度为的无序表，查找失败需要 次比较  越界判断 数据与算法 7 吴及 电子工程系 折半查找  如果顺序表有序，我们可以采用高效率的折半查找 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 56 = 0, = 10 , = 5