查找算法

顺序查找

从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。

折半查找（二分查找）

先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（查找不成功）为止。

• 这种方法要求查找表进行顺序存储并且按关键字有序排列
•  查找效率比顺序查找要高，但要求关键字有序排列。
• 适用于表不易变动，且又经常进行查找的情况。

折半查找判定树

从折半查找的过程来看，可以用一棵二叉树来描述。通常称这个描述折半查找二叉树的过程称为折半查找判定树。

树表查找

二叉查找树是一种动态查找表，表结构本身是在查找过程中动态生成的。

其实就是二叉排序树/二叉查找树

• 左边节点小于父节点，左子树所有节点小于根节点
• 右边节点大于父节点，右子树所有节点大于根节点

索引顺序查找(分块查找)

• 是对顺序查找的一种改进
• 将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的。

哈希查找

• 哈希函数：关键字作为自变量，关键字存放的地址作为因变量
• Hi=Hash(Key)
• 哈希冲突：对于某个哈希函数Hash和两个关键字K1和K2，如果K1≠K2而Hash(K1)=Hash(K2)，则称出现了冲突。

开放地址法

链地址法

• 它将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时，表示已没有后继记录。
• 地址里存放的是指针，而不是关键字，将哈希函数值相同的记录组成一个链表