二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法

第 9 章 查 找查找 search 又称为检索。它是人们在日常生活中经常要进行的一项操作，比如从字典中查找单词，从电话号码薄中或向电信局的服务台查询电话号码，从图书馆中查找图书，从地图上查找交通路线或地址，在互联网上检索某篇文章等等。对于少量信息，可以人工方式来查找，但要想在大量的信息中快速、及时、准确地进行查找，人工方式就显得无能为力，这就需要用计算机来进行处理。查找与排序一样也是计算机数据处理中常用的一种重要运算，而且两者又有密切的联系。可以说，排序的主要目的就是为了便于查找。在前面的章节中，曾经讨论过一些简单的查找运算，但由于查找运算的使用频率非常高，几乎在任何一个计算机系统软件和应用软件中都会用到。所以当问题所涉及的数据量相当大时，查找的效率就显得至关重要，特别在一些实时查询系统中更是如此。因此，需要研究各种查找方法，通过效率分析来比较各种查找方法的优劣和它们的适用范围。本章先介绍与查找有关的基本概念，然后分别讨论性表上的查找方法和在树形结构以及文件结构上的查找方法，最后介绍一类特殊的、也是十分重要的查找技术 散列表的查找。9.1 基本概念所谓查找 检索 就是在数据结构中寻找满足某种条件的结点。

最常见的方式是给出一个值，在数据结构中找出关键字等于指定值的结点。查找的结果有两种可能：一种是在结构中搜索到满足查找条件的结点，称为查找成功；另一种是该结构中不存在满足查找条件的结点，则称为查找失败。例9.1 在图9-1所示的学生成绩表中，学号是学生成绩表的关键字。现在要查找学号为9904的学生成绩，由于学生成绩表中存在满足查找条件的结点，所以可以通过某种查找方法，找到该结点，即确定在第4个结点的位置上，然后取出成绩字段的值63。这是查找成功的情况；如果要查找学号为9908的学生成绩，由于在图9-1所示的学生成绩表中不存在满足此查找条件的结点，所以无论通过何种查找方法，最终都找不到学号为9908的结点，也就不可能查找到对应的成绩，这是查找失败的情况。上例中是基于关键字的查找，若查找成功，则结构中只能存在一个满足查找条件的结点。除了基于关键字的查找之外，还有一种常用的查找方式是按其他属性字段进行查找，若查找成功，则结构中可能存在多个满足查找条件的结点。例如，在上例的学生成绩表中，查找学生成绩为82分的学生，就存在两个成绩为82分的学生。由于基于属性字段的查找可能存在多个满足查找条件的结点，这时可根据查找要求，来决定是找出其中的一个还是找出全部这样的结点。

本章主要讨论按关键字进行查找的各种方法。一般说来，基于关键字的查找与基于属性字段的查找没有本质上的太多区别。查找的目的通常是要取得相关的信息，但具体要取得哪些信息，这要根据具体的问题而定。但不管何种查找要求都有的一个共性就是：对于成功的查找应确定满足查找条件结点的位置。在下面的介绍中，问题也就讨论到此为止，而取哪些相关信息忽略不谈，应用时根据实际问题来决定。查找的方法与数据结构有关，特别是与存储结构直接相关。对不同的结构，查找的方法也不尽相同；反之，为了提高查找速度，往往采用某些特殊的数据 存储 结构来存储要查找的信息。通常把要查找的数据结构称之为查找表 search table 。如果对查找表仅进行查找操作、没有引起表本身内容的改动，则称此类表为静态查找表 static search table 。若在查找的同时对表还要做修改操作 如插入、删除 ，则称此类表为动态查找表 dynamic search table 。由于查找运算的主要操作是对关键字的比较，因此，衡量一个查找算法效率的主要标准是查找过程中对关键字需要执行的平均比较次数，或者称为平均查找长度 average search length, ASL 。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-1.html