四川大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 查找 Search

Chapter 7 Search 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 Chapter 7 Search

所谓搜索,就是在数据集合中寻找 满足某种条件的数据对象 1搜索成功即找到满足条件的数据 对象这时,作为结果,可报告该对 象在结构中的位置,还可给出该对 象中的具体信息 2搜索不成功或搜索失败。作为结 果,应报告一些信息,如失败标 志、位置等 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 所谓搜索，就是在数据集合中寻找 满足某种条件的数据对象 1.搜索成功 即找到满足条件的数据 对象这时, 作为结果, 可报告该对 象在结构中的位置, 还可给出该对 象中的具体信息 2.搜索不成功 或搜索失败。作为结 果, 应报告一些信息, 如失败标 志、位置等

通常称用于搜索的数据集合为搜索结 构,它是由同一数据类型的对象(或记 录)组成 在每个对象中有若干属性,其中有一 个属性,其值可唯一地标识这个对象 称为关键码。使用基于关键码的搜索 搜索结果应是唯一的。但在实际应用 时,搜索条件是多方面的,可以使用 基于属性的搜索方法,但搜索结果可 能不唯一 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 ◼ 通常称用于搜索的数据集合为搜索结 构，它是由同一数据类型的对象(或记 录)组成 ◼ 在每个对象中有若干属性，其中有一 个属性，其值可唯一地标识这个对象。 称为关键码。使用基于关键码的搜索， 搜索结果应是唯一的。但在实际应用 时，搜索条件是多方面的，可以使用 基于属性的搜索方法，但搜索结果可 能不唯一

实施搜索时有两种不同的环境 静态环境搜索结构不用插入和删除 操作 静态搜索表 动态环境为保持较高的搜索效率,搜 索结构在执行插入和删除等操作的前 后将自动进行调整,结构可能发生变 化一动态搜索表 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 实施搜索时有两种不同的环境 ◼ 静态环境 搜索结构不用插入和删除 操作 ⎯ 静态搜索表 ◼ 动态环境 为保持较高的搜索效率, 搜 索结构在执行插入和删除等操作的前 后将自动进行调整，结构可能发生变 化 ⎯ 动态搜索表

查找算法的评价指标 查找成功最少比较次数 最多比较次数 平均比较次数 查找失败最少比较次数 最多比较次数 平均比较次数 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 查找算法的评价指标 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数

顺序查找 以顺序表或线性链 表表示静态查找表 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 以顺序表或线性链 表表示静态查找表 顺序查找

顺序查找过程 k STele 2137881992056456807513 012345 7891011 假设给定值e=64, ST Length 要求ST: elema=e,向:k=? 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem 顺序查找过程 假设给定值 e=64, 要求 ST.elem[k] = e, 问: k = ? k k

STele 642137881992056456807513 234567891011 key=64 ST Length STelem 6012137881992056456807513 5678910 key=60 ST Length 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elemi 60 i key=64 key=60 i 64

int Search Seq( tB st, TYpe key STele0key=key;∥“哨兵 for (i-sTlength; STelem i key!=key i);∥从后往前找 return ∥找不到时,i0 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 int Search_Seq( TB ST, TYPE key ) { ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 }

分析顺序查找的 时向性能 四川大学计算机(软件)学院

四川大学 计算机(软件)学院 分析顺序查找的 时间性能