天津大学：《数据结构 Data Structures》课程教学资源（PPT课件）第九章 查找

第九章查找 查找的概念 静商查找表 今动态查找表 令哈希表 米。米

第九章 查找 v查找的概念 v静态查找表 v动态查找表 v 哈希表

查找的概念 查找表是由同一类型的数据元素(或记录) 构成的集合,由于“集合”中的数据元素之 间存在着松散的关系,因此查找表是一种 应用灵便的数据结构。对查找表的操作: 查询某个“特定的”数据元素是否在査找表中; 检索某个“特定的”数据元素的各种属性; 在查找表中插入一个数据元素; 从查找表中删去某个数据元素

查找表 是由同一类型的数据元素(或记录) 构成的集合,由于“集合”中的数据元素之 间存在着松散的关系，因此查找表是一种 应用灵便的数据结构。对查找表的操作: §查询某个“特定的”数据元素是否在查找表中； §检索某个“特定的”数据元素的各种属性； §在查找表中插入一个数据元素； §从查找表中删去某个数据元素 查找的概念

查找表的分类: 静态查找表 仅作查询和检索操作的查找表。 动态查找表 在查找过程中同时插入查找表中不存在的 数据元素,或者从查找表中删除已存在的某个 数据元素,此类表为动态查找表

静态查找表 仅作查询和检索操作的查找表。 动态查找表 在查找过程中同时插入查找表中不存在的 数据元素，或者从查找表中删除已存在的某个 数据元素,此类表为动态查找表。 查找表的分类：

关键字 是数据元素(或记录)中某个数据项 的值,用以标识(识别)一个数据元素 (或记录)。若此关键字可以识别唯一的 个记录,则称之谓“主关键字”。若此 关键字能识别若干记录,则称之谓“次关 键字

关键字 是数据元素（或记录）中某个数据项 的值，用以标识（识别）一个数据元素 （或记录）。若此关键字可以识别唯一的 一个记录，则称之谓“主关键字” 。若此 关键字能识别若干记录，则称之谓“次关 键字”

查找 根据给定的某个值,在查找表中确定一个其关 键字等于给定值的数据元素或(记录)。 若查找表中存在这样一个记录,则称“查 找成功”,查找结果:给出整个记录的信 息,或指示该记录在查找表中的位置 否则称“查找不成功”,查找结果:给 “空记录”或“空指针

根据给定的某个值，在查找表中确定一个其关 键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查 找成功” ，查找结果：给出整个记录的信 息，或指示该记录在查找表中的位置； 否则称“查找不成功” ，查找结果：给 出 “空记录”或“空指针” 。 查找

如何进行查找? 查找的方法取决于查找表的结构 由于查找表中的数据元素之间不存在明显的组 织规律,因此不便于查找。 为了提高查找的效率,需要在查找表中的 元素之间人为地附加某种确定的关系,换句 话说,用另外一种结构来表示查找表

如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组 织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的 元素之间人为地 附加某种确定的关系，换句 话说， 用另外一种结构来表示查找表

查找方法评价 查找速度 占用存储空间多 算法本身复杂程度 平均查找长度 ASL(Average Search Length) 为确定记录在表中的位置,需和给定值进行比 较的关键字的个数的期望值叫査找算法的 对含有n个记录的表,ASL=∑pC 其中:P为查找表中第计个元素的概率∑P1=1 c为找到表中第i个元素所需比较次数

查找方法评价 • 查找速度 • 占用存储空间多少 • 算法本身复杂程度 • 平均查找长度ASL(Average Search Length)： 为确定记录在表中的位置，需和给定值进行比 较的关键字的个数的期望值叫查找算法的~ 为找到表中第 个元素所需比较次数 其中： 为查找表中第 个元素的概率， 对含有 个记录的表， c i p i p n ASL p c i n i i i n i i i 1 1 1      

静查找表 抽象数据类型静态查找表的定义: ADT StaticSearchTable i 数据对象D:D是具有相同特性的 数据元素的集合。每 个数据元素含有类型 相同的关键字,可唯 标识数据元素。 数据关系R:数据元素同属一个集合

抽象数据类型静态查找表的定义: ADT StaticSearchTable { D是具有相同特性的 数据元素的集合。每 个数据元素含有类型 相同的关键字，可唯 一标识数据元素。 数据关系R：数据元素同属一个集合。 静 态 查 找 表 数据对象D:

基本操作P: Create(&ST,n);/构造一个含n个数据 元素的静态查找表ST Destroy( &st); ∥销毁表ST。 Search(ST,key);查找ST中其关键字等 于kval的数据元素。 Traverse(sT, visito) ∥按某种次序对 ST的每个元素调用函数 s0一次且仅一次, 3 ADT StaticSearchTable

Create(&ST, n); //构造一个含 n 个数据 元素的静态查找表ST。 Destroy(&ST); //销毁表ST。 Search(ST, key); //查找 ST 中其关键字等 于kval 的数据元素。 Traverse(ST, Visit()); //按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次， } ADT StaticSearchTable 基本操作 P：

顺序表的查找 以顺序表表示静态查找表,则 Search函数可 用顺序查找来实现。其顺序存储结构如下: typedef struct i ElemType *elem;∥数据元素存储空间基址,建表时 按实际长度分配,0号单元留空 int length;∥表的长度 3 SSTable;

§顺序表的查找 typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; 以顺序表表示静态查找表，则Search函数可 用顺序查找来实现。其顺序存储结构如下：