算法与诗数据结构 --- 查找 --- 线性表的查找

目录

第一部分 --- 查找的概念​编辑

第二部分 --- 线性表的顺序查找

​编辑

第二部分 --- 线性表的折半查找（二分 / 对分查找） ​编辑

第三部分 --- 线性表的分块查找（索引顺序查找）

---

第一部分 --- 查找的概念

1.查找是在查找表中进行的，查找表是一个用同类型数据元素组成的集合，这个集合中的元素之间存在着松散的关系（既每个元素没有严格的前驱和后继，它们的前驱和后继可以随时改变且改变后也不会影响查找表，可以有多个，也可以没有）

1.查找表中的一个元素称为查找表中的一个记录

2.每个记录都有关键字，关键字是记录的某一项数据域的值

3.给定一个值在查找表中进行查找的本质就是：在查找表中找到关键字和我们给定的值相同的记录

 

1.看看特定数据是否存在

2.看看已存在的数据的相关属性

3.插入元素（查找后不存在进行插入），删除元素（查找特定已存在元素，并将其进行删除）

1.静态查找表：只读不可操作；动态查找表：可读可操作

1.评价一个查找算法的好坏不是用我们常用的时间复杂度来评价，而是用平均查找长度来进行评价（这个值越大，对应的查找算法的效率越低）

2.求平均查找长度方法：用关键字比较次数的期望值来求解

首先查找任意一个记录的关键字比较次数的期望值等于 查找这个记录出现的概率（一般认为每一个记录出现的概率都是 1 / （记录总数）） * 找到这个记录所需的关键字比较次数

然后将每一个记录的关键字比较次数的期望值累加，得到的值就是平均查找长度（ASL）

1.如果说毫无规律的向查找表中存放元素的话，当我们要在表中查找特定的元素的时候就只能从表中第一个元素开始进行查找，直到找到或者所有都查找完了也没找到

2.为了提高查找效率，我们常常在往查找表中存储元素的时候，在这些元素之间人为的加上某种关系，要查找的时候就通过这些关系来进行查找，以此使得效率提升

---

第二部分 --- 线性表的顺序查找