基本概念基本概念线性表的查找线性表的查找 树表的查找 树表的查找 散列散列 (Hash)(Hash) 技术 技术 第八章 查找第八章 查找 8.18.1 查找的基本概念查找的基本概念 查找（查找（ SearchingSearching ））的定义是：给定一个关的定义是：给定一个关键字值键字值 KK ，在含有，在含有 nn 个结点的表中找出关键字个结点的表中找出关键字等于给定值等于给定值 KK 的结点。若找到，则查找成功，的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息则查找失败，返回相关的指示信息。。 查找表的数据结构表示查找表的数据结构表示 若在查找的同时对表做修改操作（如插入和删除若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为等），则相应的表称之为动态查找表动态查找表（（ Dynamic Dynamic Search TableSearch Table ）。否则称之为）。否则称之为静态查找表静态查找表 (Stati(Static Search Table)c Search Table) 。。 若整个查找过程都在内存进行，则称之为若整个查找过程都在内存进行，则称之为内查内查找找；反之，若查找过程中需要访问外存，则称之；反之，若查找过程中需要访问外存，则称之为为外查找外查找 平均查找长度 平均查找长度 ASLASL （（ Average Search LengthAverage Search Length ））定义为定义为 ：ASL=ASL= 其中：其中： 11 、、 nn 是结点的个数；是结点的个数； 22 、、 PiPi 是查找第是查找第 ii 个结点的概率。若不特别个结点的概率。若不特别声明 ，认为每个结点的查找概率相等，即声明 ，认为每个结点的查找概率相等，即 pl = p2…… = pn = 1/npl = p2…… = pn = 1/n 33 、、 cici 是找到第是找到第 ii 个结点所需进行的比较次个结点所需进行的比较次数。数。niiicp1 顺序查找顺序查找 (Sequential Search) (Sequential Search) 基本思想是：基本思想是：从表的一端开始，顺序扫描线性表，依从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值次将扫描到的结点关键字和给定值 KK 相比较。若当相比较。若当前扫描到的结点关键字与前扫描到的结点关键字与 KK 相等，则查找成功；若相等，则查找成功；若扫描结束后，仍未找到关键字等于扫描结束后，仍未找到关键字等于...
