数据结构第8章 查找

预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

第8章

查找

本章重点难点重点：顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。

难点：二叉排序树的删除算法和平衡二叉树的构造算法。

预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

预备知识

第8章

查找

有关概念(1) 查找表：

是由同一类型的数据元素(或记录)构成的集合。(2) 静态查找表： 仅作查询和检索操作的查找表。

(3) 动态查找表：在查找时包含插入、删除或修改。4

预备知识 有关概念 (4) 主关键字

第8章

查找

可以识别唯一的一个记录的数据项(字段)。 (5) 次关键字 关联若干项记录的数据项(字段)。 (6) 查找 根据给定的某个值，在查找表中确定一个其关键字 等于给定值的数据元素或(记录)。5

预备知识 有关概念 (7) 查找成功 查找表中存在满足条件的记录。 (8) 查找不成功 查找表中不存在满足条件的记录。

第8章

查找

预备知识

第8章

查找

类型定义 typedef float Keytype; //Keytype定义为浮点数据类型 typedef int Keytype; //Keytype定义为整型数据类型 typedef char *Keytype; //Keytype定义为字符指针数据类型

预备知识

第8章

查找

类型定义

数据元素类型定义为： typedef struct{ Keytype key;//关键字 … }SElemType; // SElemType结构体数据类型

预备知识

第8章

查找

宏定义//数值型关键字的比较 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) //字符型关键字的比较 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b)<=0)

预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

第8章

查找

8.1 静态查找表8.1.1 顺序表的查找 8.1.2 有序表的查找 *8.1.3 静态树表的查找 //自学 8.1.4 索引顺序表的查找

8.1 静态查找表 静态查找表的抽象数据类型 ADT StaticSearchTable {

第8章

查找

D是具有相同特性的数据元素 数据对象D: 的集合。每个数据元素含有 类型相同的关键字，可唯一 标识数据元素。数据关系R:数据元素同属一个集合。 基本操作 P: 见下页

} ADT StaticSearchTable12

8.1 静态查找表

第8章

查找

基本操作

Create(&ST, n); //建立静态查找表 Destroy(&ST); //销毁静态查找表

Search(ST, key); //按关键字字key查找Traverse(ST, Visit()); //遍历查找表

第8章

查找

8.1 静态查找表8.1.1 顺序表的查找 8.1.2 有序表的查找 *8.1.3 静态树表的查找 //自学 8.1.4 索引顺序表的查找

8.1.1 顺序查找表

第8章

查找

顺序查找表存储结构typedef struct {

ElemType *elem;// 数据元素存储空间基址，建表时

//

按实际长度分配，0号单元留空int length; // 表的长度 } SSTable;

8.1.1 顺序查找表

第8章

查找

顺序查找表的思想(1)从查找表的第一个元素向后(或从最后一 个元素向前),比较当前位置数据元素的关键字 与查找关键字； (2)若相等，输出当前位置，查找成功，若不 相等，走向下一个位置； (3)循环执行(1)、(2)步，直到查找成功或超 出范围，表示查找失败。