第七章披索结构 静态搜索结尥 二叉搜索树 AVL树
第七章 搜索结构 • 静态搜索结构 • 二叉搜索树 • AVL树 1
静态披索表 搜索( earch)的概念 所谓搜索,就是在数据集合中寻找满足某种 条件的数据对象。 搜索的结果通常有两种可能: >搜索成功,即找到满足条件的数据对象。 这时,作为结果,可报告该对象在结构中 的位置,还可给出该对象中的具体信息。 >搜索不成功,或搜索失败。作为结果,应 报告一些信息,如失败标志、位置等
静态搜索表 2 搜索(Search)的概念 ◼ 所谓搜索，就是在数据集合中寻找满足某种 条件的数据对象。 ◼ 搜索的结果通常有两种可能： ➢搜索成功，即找到满足条件的数据对象。 这时，作为结果，可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。 ➢搜索不成功，或搜索失败。作为结果，应 报告一些信息, 如失败标志、位置等
通常称用于搜索的数据集合为搜索结构,它是 由同一数据类型的对象或记录)组成。 在每个对象中有若干属性,其中有一个属性 其值可唯一地标识这个对象。称为关键码。使 用基于关键码的搜索,搜索结果应是唯一的。 但在实际应用时,搜索条件是多方面的,可以 使用基于属性的搜索方法,但搜索结果可能不 唯
• 通常称用于搜索的数据集合为搜索结构，它是 由同一数据类型的对象(或记录)组成。 • 在每个对象中有若干属性，其中有一个属性， 其值可唯一地标识这个对象。称为关键码。使 用基于关键码的搜索，搜索结果应是唯一的。 但在实际应用时，搜索条件是多方面的，可以 使用基于属性的搜索方法，但搜索结果可能不 唯一。 3
实施搜索时有两种不同的环境。 ◆静态环境,搜索结构在插入和删除等操作 的前后不发生改变。一静态搜索表 动态环境,为保持较高的搜索效率,搜索结 构在执行插入和删除等操作的前后将自动 进行调整,结构可能发生变化 动态搜索表
• 实施搜索时有两种不同的环境。 ◆ 静态环境，搜索结构在插入和删除等操作 的前后不发生改变。⎯ 静态搜索表 ◆ 动态环境，为保持较高的搜索效率, 搜索结 构在执行插入和删除等操作的前后将自动 进行调整，结构可能发生变化。 ⎯ 动态搜索表 4
静态披索表 在静态搜索表中,数据元素存放于数组中, 利用数组元素的下标作为数据元素的存放地 址。搜索算法根据给定值k,在数组中进行 搜索。直到找到k在数组中的存放位置或可 确定在数组中找不到k为止
静态搜索表 • 在静态搜索表中，数据元素存放于数组中， 利用数组元素的下标作为数据元素的存放地 址。搜索算法根据给定值 k，在数组中进行 搜索。直到找到 k 在数组中的存放位置或可 确定在数组中找不到 k 为止。 5