算法与数据结构|查找

1.查找基本概念

分为静态查找和动态查找；静态查找时构造的存储结构成为静态查找表，动态查找时构造的存储结构为动态哈招标

2.静态查找表

静态查找表包括：顺序表、有序顺序表、索引顺序表三种结构。

2.1 顺序表

在顺序表上查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个与顺序表中各数据元素的关键字比较，若存在，则查找成功；反之，则查找失败。

查找成功的平均查找长度ASL_成功=(1+n)/2；查找失败平均查找长度ASL_失败=n

2.2 有序顺序表

有序顺序表上的查找算法主要有顺序查找和二分查找方法

2.2.1 顺序查找

与之前的查找一样，但是由于是有序的因此在失败时平均查找长度与之前是有不同的：

ASL_成功=(n+1)/2；ASL_失败=(n+1)/2。

2.2.2 二分查找

基本思想：在一个查找区间，确定查找区间的中心位置，用待查找的元素的关键字与之对比，若相等则查找成功；否则，若若小于则把查找区间改为原区间的左部分；若大于则把查找区间改为原区间的右部分；这样查找一直到查找区间的上界小于下界为止。

2.3 索引顺序表

当顺序表的数据元素个数非常大时，无论使用哪种查找算法都需要很长的时间，此时，我们可以在顺序表上建立索引表。我们把在其上建立索引表的顺序表叫做主表，主表中存放数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。

当数据元素个数非常庞大时，可以对索引表再做索引表，这样的索引表叫做耳机索引表或者多级索引表。

索引表还分为等长索引表、不等长索引表(多一个length域)(主表分段有序即可，要求比有序低)。

3.动态查找表

3.1 二叉排序树

二叉排序树：或者是一个空树或者具有以下性质：(1)若左子树不空，则左子树上所有节点的关键字值均小于根节点的关键字值；(2)若右子树不空，则右子树上所有节点的关键字均大于等于根节点的关键字值；

3.2 B_树

与二叉排序树相比，B_树是一种平衡多叉排序树。这里说的平衡是指所有叶节点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象；多叉指多余二叉，B_是一种动态查找效率高于二叉排序树的树。

B_树中所有节点的孩子节点的最大值成为B_树的阶通常用m表示。一棵m阶的B_树或者是一棵空树，或者是满足下列要求的m叉树：

1，树中每个节点最多有m个孩子节点

2，除根节点外，其他节点至少有[m/2]（向上取整）个孩子节点

3，若根节点不是叶节点，则根节点至少有两个孩子节点。

4，每个节点的结构：

n表示该节点中关键字个数；Ki表示该节点的关键字且满足Ki<Ki+1；Pi为该节点的孩子节点指针且满足Pi指针所指及诶但的关键字均大于等于Ki小于Ki+1。Pn指针所指的关键字大于等于Kn

4.哈希表

哈希函数：把数据元素的关键字和该数据元素的存放位置之间的映射函数称为哈希函数；哈希表就是通过哈希函数确定数据元素存放位置的一种特殊结构。

哈希冲突，当数据元素关键字不相等，但是经过哈希函数映射的位置相同时，我们管这个叫做哈希冲突.哈希冲突主要与三个因素有关：a，装填因子(存入元素与哈希池地址空间壁纸；b，使用的哈希函数相关；c，与解决哈希冲突的冲突解决函数有关)

解决哈希冲突的方法，基本思想：当哈希冲突时，通过哈希函数产生一个新的哈希地址是不产生冲突，通常哈希函数是一组函数。

一旦构造好哈希表，只需要以关键字K和哈希函数来映射到地址，然后从地址中取出关键字元素对比是否相同，相同则查找成功，否则以建立哈希表时所用的冲突函数得到新的地址查看关键字是否相同，一直到查找成功或查找完成m次而未查找到。数据分析师培训

常用的哈希函数构造方法：1，除留余数法；2，直接定址法；3，数字分析法。

哈希冲突解决方法：1，开放定址法(线性探查法、平方探查法、伪随机数法)；2，链表法。