【笔记分享】大话数据结构2：查找

查找表：由同一类型的数据元素构成的集合

关键字：数据元素中某个数据项的值，又称键值

查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素

 

查找表按照操作方式分两类：静态查找表和动态查找表

静态查找表：只用作查找操作的查找表，主要操作有：

动态查找表：在查找的过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素，主要操作有：

 

顺序表查找

顺序查找又叫线性查找，过程是：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个相比较都不等，则表中没有所查的记录，查找不成功

顺序查找的算法实现：

 

顺序表查找优化

 

有序表查找

二分查找的前提是线性表中的记录必须是关键码有序，线性表为顺序存储。

二分查找的思想：在有序表中，取中间值作为比较对象，若给定值和中间记录关键字相等，则查找成功，否则按照大小划分继续进行比价，直到结束为止。

插值法对于二分查找的改进：代码第八句

 

斐波拉契查找

斐波拉契数列

斐波拉契代码

 

 

线性索引查找

线性索引三种方式：稠密索引、分块索引、排序索引

稠密索引

在线性索引中，将数据集中的每个记录对应一个索引项

特点：索引项有序，可以通过二分、插值等有序算法查找；但是对于数据集非常大的情况，对于内存有限的计算机，需要反复访问磁盘，查找性能大大降低了

 

分块索引

把数据集的记录分成了若干块，并且这些块块内无序、块间有序。

 

倒排索引

示例：

单词索引表-->倒排索引

 

二叉排序树

又叫二叉查找树，或者是一颗空树，或者具有以下性质：

1. 若其左子树不空，则左子树上所有结点的值均小于其根结点的值
2. 若其右子树不空，则右子树上所有结点的值均大于其根结点的值
3. 其左右子树也分别为二叉排序树

 

二叉树结构定义

二叉排序树查找的代码实现

 

二叉排序树插入：

 

二叉排序树删除操作

 

其中delete代码

 

平衡二叉树（AVL树）

是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1.

平衡因子：二叉树上结点的左子树深度减去右子树深度的值

平衡二叉树实现

树的结点构造

右旋操作：

 

左旋操作

左平衡旋转处理的函数代码

插入平衡二叉树：

主函数调用调试：

 

说明：对于不平衡的二叉排序树，查找效率是非常低的，此时构建这颗二叉树为平衡二叉树，则查找时间复杂度为O(logn)，插入和删除也是O(logn)

 

多路查找树（B树）

每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素；是查找树，所有元素之间存在某种特定的排序关系

因为每个结点可以存储多个元素，以及孩子数的多少非常关键，所以按照特征形式介绍如下四种：2-3树，2-3-4树，B树，B+树

 

2-3树

其中每个结点都具有两个孩子（2结点）或者三个孩子（3结点）。一个2结点包含一个元素和两个孩子（或者没有孩子，不能只有一个孩子），与二叉排序树类似；一个3结点包含一小一大两个元素和三个孩子（或者没有孩子）。

2-3树的插入

针对插入时要往3结点中插入一个新元素可能遇到的情况

1、

2、

3、

 

2-3树的删除

针对删除一个元素可能遇到的情况

1、

2、

 

 

 

3、

 

 

2-3-4树

2-3树概念的推广，一个4结点包含小中大三个元素和四个孩子，一个4结点要么没有孩子，要么具有4个孩子

插入示例

删除示例

 

B树

B树是一种平衡的多路查找树，2-3树和2-3-4树都是其特例。结点最大的孩子数目称为B树的阶，2-3树为3阶B树，2-3-4树是4阶B树

一个m阶的B树具有以下属性

 

B树进行查找时，是一个顺时针查找结点和在结点中查找关键字的交叉过程

 

B+树

一颗m阶B+数和m阶B树的差异在于：

 

哈希表概述

目的：查找某个位置数据，其实就是--->存储位置=function（关键字）

散列技术：在记录的存储位置和其关键字之间建立一个确定的对应关系，使得每个关键字对应一个存储位置，查找时，根据这个确定的对应关系找到给定值的关键字的映射。这个映射关系称为散列函数，也叫哈希函数。

 

散列表查找步骤

Step1：在存储时，通过散列函数计算记录的散列地址，并按散列地址存储该记录。

Step2：查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问记录

 

散列技术既是一种存储方法，也是一种查找方法。与前述各种数据结构不同的是：

前面数据结构数据元素之间都有某种逻辑关系，可以可视化；

而散列技术只与关键字有关，数据间没有逻辑关系，因此散列主要面向查找的存储结构

 

散列最适合的求解场景是查找与给定值相等的记录。

不适合的求解场景：一个关键字对应多条记录的情况；范围查找。

 

散列函数的构造方法

两个原则：

1、计算简单

2、散列地址分布均匀

具体的构造方法介绍

直接定址法：直接取关键字的某个线性函数值为散列地址

说明：适合查找表较小且连续的情况

 

数字分析法：

说明：适合处理关键字位数比较大的情况，如果事先知道关键字的分布且分布均匀

 

平方取中法

示例：1234，平方1234*1234 = 1522756， 抽取中间3位：227

说明：适合不知道关键字的分布，而位数又不是很大的情况

 

折叠法

将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

示例：

说明：适合关键字位数较多的情况

 

除留余数法

示例

说明：余数的选择很重要，若散列表表长为m,通常p为小于或等于表长的最小质数或不包含小于20质因子的合数

 

随机数法

F(Key) = random(key)

说明：当关键字长度不等时，采用这个方法构造散列函数是比较合适的

 

散列表查找实现

定义数据结构

进行初始化

定义散列函数

对散列表进行插入操作

有了散列表，需要的时候就可以直接通过散列表进行查找记录了

 

散列表查找性能分析

1、散列函数是否均匀

2、处理冲突方法不同会导致平均查找长度不同

3、散列表的填装因子，越小，产生冲突的可能性就越小