第仙0章查找 静态查找表 动态查找表 哈希查找表 在各种系统软件和应用软件中,查 找表是一种最常见的数据结构,有着广 泛的应用
第10章 查找 • 静态查找表 • 动态查找表 • 哈希查找表 在各种系统软件和应用软件中，查 找表是一种最常见的数据结构，有着广 泛的应用
10.1查找表基本概念 查找表( table):由同类型的DE(或记录)构成的集合 查找表上的基本运算 建立查找表 create(ST,n) 查找 search(ST,k) 遍历查找表 traverse(ST) 其抽象数据类型定义见书P216. 关键字(key):是表中数据元素中某个数据元素的某值, 用它可以标识(识别)这个数据元素。若此关键字可以唯一地标 识这个元素,则它称为主关键字( Primary Key);反之,若用 它能识别一批元素,则称它为次关键字( Secondary Key)
10.1 查找表基本概念 查找表(table):由同类型的DE(或记录)构成的集合. 查找表上的基本运算: • 建立查找表create(ST, n) • 查找search(ST, k) • 遍历查找表traverse(ST) 其抽象数据类型定义见书P216. 关键字（key）：是表中数据元素中某个数据元素的某值， 用它可以标识（识别）这个数据元素。若此关键字可以唯一地标 识这个元素，则它称为主关键字（Primary Key）；反之，若用 它能识别一批元素，则称它为次关键字（Secondary Key）
查找表基本概念 查找:在查找表中确定一个关键字与给定值相等的DE 的过程 查找结果: 查找成功 table中存在给定值的记录) 查找不成功(tabe中不存在给定值的记录) 查找表分为: 静态查找表(对查找表中的数据元素不进行插入和删 除操作) 动态查找表(对查找表中的数据元素可进行插入和删 除操作)
查找表基本概念 查找 : 在查找表中确定一个关键字与给定值相等的DE 的过程. 查找结果: • 查找成功 (table 中存在给定值的记录) • 查找不成功(table 中不存在给定值的记录) 查找表分为: • 静态查找表(对查找表中的数据元素不进行插入和删 除操作) • 动态查找表(对查找表中的数据元素可进行插入和删 除操作)
查找表基本概念 本章中涉及的关键字类型及数据元素类型如下 典型的关键字类型说明可以是: typedef float Key Type;∥关键字类型为实型 typedef int Key Type;∥关键字类型为整型 typedef char Key Type;∥关键字类型为字符串型 数据元素类型定义为: typedef struct( Key Type key;∥关键字域 ∥其它域 Elem Type
查找表基本概念 本章中涉及的关键字类型及数据元素类型如下： 典型的关键字类型说明可以是： typedef float KeyType; //关键字类型为实型 typedef int KeyType; //关键字类型为整型 typedef char KeyType; //关键字类型为字符串型 数据元素类型定义为： typedef struct{ KeyType key; //关键字域 ….. //其它域 }ElemType;
查找表基本概念 关键字比较的常用宏定义 用于数值关键字的有: #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))<o #define LQ(a, b) (strcmp((a),(b))<=0
查找表基本概念 关键字比较的常用宏定义 用于数值关键字的有： #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)