数据结构与算法设计（第二版）课件 第8章 查找.pptx

第八章查找;第八章查找;在计算机各种系统软件或应用软件中，查找表也是一种最常见的结构之一。如编译程序中符号表、信息处理系统中的信息表等。所有需要被查的数据所在的集合就是查找表。

查找表(searchtable)：由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构，可以是线性表、树、图。;所谓“查找”，即为在一个含有众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。为了便于讨论，必须给出这个“特定的”词的确切含义，引入“关键字”的概念。

关键字(key)：数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。如果一个关键字可以唯一地标识一个数据元素，则称其为主关键字；否则为次关键字。当数据???素仅有一个数据项，数据元素的值就是关键字。;查找;显然，在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的位置。因此，对表进行查找的方法取决于表中数据元素依赖何种关系(这个关系是人为地加上的)组织在一起的。;查找表是一种非常灵便的数据结构，数据元素之间仅存在着“同属一个集合”的松散关系，给查找带来不便。为此，需在数据元素之间人为地加上一些关系，以便按某种规则进行查找，即以另一种数据结构来表示查找表。

本章所讨论的查找表分两大类：

静态查找表、动态查找表。

静态查找表：只做查找操作的查找表。它的主要操作有：

(1)查询某个“特定的”数据元素是否在查找表中。

(2)查找某个“特定的”数据元素的各种属性。

静态查找表在查找之前已经存在，查找是在已经有的数据集中找我们需要的。但是，随着时间的推移，新的信息不断出现，查找表也应该不断更新。为此，引进了动态查找表。

;动态查找表：在查找的过程中同时插入查找表中不存在的数据元素，或者删除已经存在的某个数据元素。显然动态查找表的操作就是两个：

(1)查找时插入数据元素。

(2)查找时删除数据元素。

此外，还有一种表——哈希表，它是一种既适合于静态查找也适合于动态查找的查找表，具体技术会在8.4节详细介绍。;平均查找长度(averagesearchlength)：为确定记录在查找表中的位置，需和给定值进行比较的关键字次数的期望值称为查找算法在查找成功时的平均查找长度。对于长度为n的查找表，查找成功时的平均查找长度为;基于静态查找表主要有顺序表、有序顺序表、索引顺序表、倒排表，查找法可分为顺序查找法、折半查找法和分块查找法。

8.2.1顺序表

在顺序表上查找的基本思想是：用给定关键字与顺序表中各元素的关键字逐个比较，直到成功或失败(所有元素均不成功)。存储结构可为顺序存储结构，也可为链式存储结构。这种查找方法叫做顺序查找。;下面给出顺序结构有关数据类型的定义：

#defineLISTSIZE20

typedefstruct

{

KeyTypekey;/*关键字域*/

…/*其他域*/

}ElemType;

typedefstruct

{

ElemTyper[LISTSIZE];

intlength;

}STable;

STablest;;查找过程可用下述算法描述之：

1intSearchSeq(STablest,KeyTypek)

/*在顺序表中查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/

2{

3inti;

4st.r[0].key=k;

5i=st.length;

6while(st.r[i].key!=k)i--;

7return(i);

8};假设表长为n，那么查找第i个数据元素时需要进行n-i+1次比较，即Ci=n-i+1，又假设查找每个元素的概率相等，即Pi=1/n，则顺序查找算法查找成功时的平均查找长度为：;8.2.2有序顺序表

在有序顺序表上查找的算法主要有顺序查找、折半查找和插值查找方法。

1.顺序查找

在有序顺序表上顺序查找的方法和8.2.1节讨论的顺序表上的查找方法