第11章查找 主「查找的基本概念 要)静态查找表 知 识动态查找表 点哈希表
第11章 查找 查找的基本概念 静态查找表 动态查找表 哈希表 主 要 知 识 点
111查找的基本概念 查找查询某个关键字是否在(数据元素集合)表中的过程。也 称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素
11.1 查找的基本概念 查找:查询某个关键字是否在(数据元素集合）表中的过程。也 称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字:通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素
静态查找只查找,不改变数据元素集合内的数据元素 动态查找:既查找,又改变(增减)集合内的数据元素 静态查找表:静态查找时构造的存储结构 动态查找表动态查找时构造的存储结构 平均查找长度查找过程所需进行的关键字比较次数的平 均值,是衡量查找算法效率的最主要标准,其数学定 义为: ASL ∑ P XO
= = × n i ASL Pi C i 1 静态查找:只查找，不改变数据元素集合内的数据元素 动态查找:既查找，又改变（增减）集合内的数据元素 静态查找表:静态查找时构造的存储结构 动态查找表:动态查找时构造的存储结构 平均查找长度:查找过程所需进行的关键字比较次数的平 均值,是衡量查找算法效率的最主要标准,其数学定 义为：
其中,P是要查找数据元素出现的概率,C是 查找相应数据元素的比较次数。 定义要查找数据元素的结构体为: typedef struct KeyType key; 3 DataType
其中，Pi是要查找数据元素出现的概率，Ci是 查找相应数据元素的比较次数。 定义要查找数据元素的结构体为： typedef struct { KeyType key; } DataType;
112静态查找表 静态查找表主要有三种结构 顶序表 序顺序表 引顺序表
11.2 静态查找表 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表