查找基本概念、方法和查找法
查找的基本概念
列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。

关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。

  • 主关键字：惟一标识列表中的一个数据元素
  • 次关键字：不是主关键字，就为次关键字
  • 当数据元素仅有一个数据项时，数据元素的值就是关键字
查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。
  • 静态查找：在查找过程中只是对数据元素进行查找
  • 动态查找：在实现查找的同时，插入找不到的元素，或从查找表中删除已查到的某个元素。
平均查找长度（ASL）：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

查找的基本方法

1. 比较式查找法 —— （1）基于线性表的查找 （2）基于树的查找法

2. 计算式查找法 —— HASH（哈希）查找法

 

基于线性表的查找法 —— 顺序查找法；折半查找法

顺序查找法

若列表长度为 n，查找从最后一个元素开始找起，查找每个数据元素的概率相等，

则顺序查找算法的平均查找长度为：ASL=（n + 1）/ 2  （从首元素开始同样）

若查找第 i 个元素，需进行（n – i + 1）次比较。

折半查找法

前提条件：

  • 必须采用顺序储存结构
  • 必须按关键字大小有序排列

版权声明：本文为lin2001原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/lin2001/p/13025885.html