查找

静态查找和动态查找

只做查找操作不对数据元素进行修改,称为静态查找

反之在查找的同时进行增删替换等数据操作,称为动态查找

内查找和外查找

整个查找过程都在内存中进行称为内查找

查找过程中需要访问外存称为外查找

关键字

能用来查找的和其它能区分开来的独一无二的数据

例如学生的学号,图书的编号等等


顺序查找算法

可以用顺序表,也可以用链表

从最后一个元素开始依次和查找的量进行比较

如果相等就是查找成功,如果到第一个还是没有符合的便是查找失败

顺序查找的性能分析

对于查找算法来说

评价其性能的好坏的标准是时间复杂度

查找成功时,查找的关键字和查找表中的数据元素中进行比较的个数的平均值

被称为平均查找长度(ASL)


折半查找(二分查找)

使用前提:表中的元素一定要是有序的

所以在遇到乱序的表时

需要根据查找的顺序决定降序或者升序

假如现在有个表为1 2 3 4 5

我们要查找的元素是2

这里有三个指针

  • 指向1的头指针
  • 指向5的尾指针
  • 指向3的中指针

一开始你需要让2和中指针3进行比较

很明显2是小于3的,因为表是升序排列

此时尾指针指向中指针左侧的位置2

原来的中指针就和1重叠了

所有很明显可以判断尾指针是我们要找的元素

可能有的人会说这是奇数个,偶数个会不会有影响

偶数事实上并没有任何区别

当你遇到头尾中间间隔的元素是偶数的时候

直接取整就行

折半查找的性能分析

折半查找到运行过程可以用二叉树来表示

这棵树通常被称为“判定树”

输入表中的数据元素:
5 13 19 21 37 56 64 75 80 88 92
请输入查找数据的关键字:
21
数据在查找表中的位置为:4

除了叶节点以外的节点都是中指针指向的元素

第一次遍历后中指针可能指向19也可能指向80

第二次遍历就可以看到21了

也就是说只要进行三次比较就可以找到21了

对于n个节点的判定树至多有log2n + 1层


分块查找算法(索引查找算法)

除了查找表本身,再建立一个索引表

可以看到索引表需要包含两个东西

一个是最大的元素,一个是第一个关键字在表里的位置

建立的索引表要求要升序排列

查找表要么整体有序(整体就是升序的)

要么分块有序(分块最大关键字是升序排列)

假设我们现在要查找38这一元素

因为22<38<48

可以确定38在第二张表里

之后就要在第二张表里进行顺序查找

索引表里查找可以使用二分法

但是到了查找表后因为不能确定是否有序所以用顺序查找

分块查找的性能分析

受两部分影响

查找块的操作和块内查找的操作

总体来说时间上是介于顺序查找和二分查找之间的


二叉排序树(BST)

前面讲的都是静态查找表,也就是只查找不修改

从这里开始讲的是动态查找表,可以进行增删查改

二叉排序树要么是空二叉树,要么具有如下特点:

  • 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点的值;
  • 二叉排序树中,如果其根结点有右子树,那么右子树上所有结点的值都大小根结点的值;
  • 二叉排序树的左右子树也要求都是二叉排序树;

二叉排序树的插入和创建

基本算法和二叉树是一样的

关键在于插入元素后还要保持其作为二叉排序树的特性

也就是查找失败的时候把数据插入到该节点的左孩子或右孩子

删除关键字

对于删除的节点p来说有三种情况

  • 结点 p 为叶子结点,此时只需要删除该结点,并修改其双亲结点的指针即可
  • 结点 p 只有左子树或者只有右子树,此时只需要将其左子树或者右子树直接变为结点 p 双亲结点的左子树即可
  • 结点 p 左右子树都有,此时有两种处理方式:
    • 1)令结点 p 的左子树为其双亲结点的左子树;结点 p 的右子树为其自身直接前驱结点的右子树
    • 2)用结点 p 的直接前驱(或直接后继)来代替结点 p,同时在二叉排序树中对其直接前驱(或直接后继)做删除操作

平衡二叉树(BBT or AVL)

  • 每棵子树中的左子树和右子树的深度差不能超过 1
  • 二叉树中每棵子树都要求是平衡二叉树

平衡因子:每个结点都有其各自的平衡因子,表示的就是其左子树深度同右子树深度的差

平衡二叉树中各结点平衡因子的取值只可能是:0、1 和 -1


哈希表

在我们数学的学习过程中我们常常会使用函数来表示关系

哈希表的原理便和函数类似

只要把关键字传入一个设计好的公式就会有一个对应的值

这个值就是记录这个关键字的地址,也就是哈希地址

这个转换的公式就是哈希函数

我们知道函数会出现多对一的情况,可能有不同的x值对应同一个y值

哈希函数如果出现了这种情况就代表着发生了冲突(多个关键字共用了一个地址)

在设计哈希函数的时候需要尽量避免这种情况的发生

哈希函数的构造

直接定址法:一次函数

H(key)= key 或者 H(key)=a * key + b

其中 H(key)表示关键字为 key 对应的哈希地址,a 和 b 都为常数

数字分析法:

如果关键字由多位字符或者数字组成

就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址

在取法上尽量选择变化较多的位,避免冲突发生

平方取中法:

对关键字做平方操作,取中间的几位作为哈希地址

折叠法:

是将关键字分割成位数相同的几部分(最后一部分的位数可以不同)

然后取这几部分的叠加和(舍去进位)作为哈希地址

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

折叠时有两种方式,一种是移位折叠,另一种是间界折叠

移位折叠是将分割后的每一小部分,按照其最低位进行对齐,然后相加(a)

间界折叠是从一端向另一端沿分割线来回折叠(b)

除留余数法:

若已知整个哈希表的最大长度 m,可以取一个不大于 m 的数 p

然后对该关键字 key 做取余运算,即:H(key)= key % p

随机数法:

是取关键字的一个随机函数值作为它的哈希地址,即:H(key)=random(key)

此方法适用于关键字长度不等的情况

哈希查找算法

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注