|
|
|
|
|
对查找表经常要进行两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。通常只进行这两种操作的查找表称为静态查找表。静态查找表主要有顺序查找、折半查找和分块查找。
|
|
|
|
|
|
顺序查找，又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
|
|
|
|
折半查找是一种采用顺序存储结构的线性表进行查找的方法，也称二分查找。在进行折半查找之前，线性表中的数据元素必须按照关键字的值升序或降序排列。
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。平均查找长度为：
|
|
|
|
|
|
|
|
分块查找又称索引顺序查找，是顺序查找的一种改进方法。在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块，然后在块中顺序查找。
|
|
|
|
假设长度为n的分块表分成b块，每块中元素个数为s，又设每个元素的查找概率都相等，块间块内均采用线性查找方法，则平均查找长度为：
|
|
|
|
|
|
|
|
若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
|
|
|
|
|
|
二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树。
|
|
|
|
.若它的左子树非空，则左子树上所有节点的值均小于根节点的值。
|
|
|
|
.若它的右子树非空，则右子树上所有节点的值均大于或等于根节点的值。
|
|
|
|
|
|
|
|
若二叉树为非空，将给定值与根节点的关键字值进行比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树进行查找。
|
|
|
|
|
|
二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的，具体过程如下：读入一个元素，建立一个新节点。若二叉排序树非空，则将新节点的值与根节点的值进行比较，如果小于根节点的值，则插入左子树中，否则插入右子树中；若二叉树为空，则新节点作为二叉排序树的根节点。
|
|
|
|
|
|
在二叉排序树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性。
|
|
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。当选择了某个散列函数后，不同的关键字可能与同一个散列地址相对应，这种现象称为冲突。
|
|
|
|
对于哈希表，主要考虑两个问题：一是如何构造哈希函数，二是如何解决冲突。
|
|
|
|
|
|
常用的哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
|
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个"空"的哈希地址。常见的冲突处理方法有：开放地址法、链地址法、再哈希法等。
|
|
|
