基于线性表的查找：
顺序查找，折半查找，索引查找
基于树的查找
二叉排序树特性（或为空树）：
若他的左子树不空，则左子树上所有结点的值均小于根节点的值。
若他的右结点不空，则右子树上所有结点的值均大于根节点的值。
他的左右子树页都分别是二叉排序树。
对二叉树进行中序遍历，得到的序列递增。
二叉排序树的查找
若给定值等于根节点，查找成功。
若小于根，继续在左子树进行查找；否则，在右子树进行查找。
二叉排序树查找的非递归实现
BSTree SearchBST (BSTree bst, KeyType k
)
{
BSTree q;
q = bst;
while (q
) {
if ( q -> key == k) return q;
if ( k < q
-> key
) q = q -> lchild;
else q = q -> rchild;
}
return NULL;
}
二叉排序树查找的递归实现
BSTree SearchBST (BSTree bst, KeyType k
)
{
if (
!bst)
return NULL;
else if (bst -> key == k
) return bst;
else if (bst -> key < k
) return SearchBST
(bst->lchild, key
);
else return SearchBST(bst->rchild, key
);
}
二叉树的插入
void InsertBST(BSTree *bst, KeyType k
)
{
BiTree s;
if (*bst ==
NULL
) {
s = (BSTree)malloc (sizeof (BSTNode
));
s －>key = k;
s -> lchild = NULL;
s -> rchild = NULL;
*bst = s;
}
else if (k < (*bst
) -> key
) InsertBST((*bst
)->lchild, k
);
else InsertBST((*bst) -> rchild, k
);
}
散列的核心就是
由hash函数决定关键字值与散列地址之间的对应关系。
散列查找方式：
在关键字key和存储地址p之间建立一种对应关系Ｈ, 使得 p = H(key); H为hash函数，p被称为散列地址。创建hash表时，把关键字为key的记录直接存入地址为H(key)的地址单元中，以后寻找key时，再利用 p = H(key)计算出该记录的散列地址p。
hash 函数构造方法：
(1) 除留余数法
假设表长为m, p为小于等于表长m的最大素数，则hash函数为 H(key) = key % p;
(2) 数字分析法
假设关键字集中中的每个关键字都是由s位数字组成(k1,k2......kn), 提取分布均匀的若干位或他们的组合作为hash地址。
(3)平方取中法
将一组关键字平方后取中间的几位作为散列地址集。
(4)分段叠加法
若关键字太复杂，可将其分成位数相同的几部分，然后进行移位叠加或者折叠叠加。
eg: key = 926483715503
H(926483715503)移位叠加 = 627;
H(926483715503)折叠叠加 = 330;
移位叠加 ９２６ 折叠叠加 ９２６
４８３ ３８４
７１５ ７１５
＋ ５０３ ＋ ３０５
———— ————
６２７ 3 3 0
(4)基数转换法
将关键字看成是另一种进制的数，然后再转成原来的进制数，再选择其中几位作为散列地址。
有时这种找地址的方法会出现冲突，比如在取余法中如果数字较多很容易出现余值相同的现象。
下面列举一些处理冲突的方法：
１．开放定址法
hi = (H(key) + di) % m; i = 1,2,......,n
(1)线性探测再散列
di = i;(即di = 1,2,......,n)
冲突发生时，顺序查看下一单元，若冲突，继续下一个，直到找到空表把它放进去就行。
(2)二次探测再散列
di = 1^2, (-1)^2, 2^2, (-2)^2,.......k^2, (-k)^2 (k <= m/2)
冲突发生时，分别在表的左右进行跳跃式探测，优点是灵活不易聚集，缺点是不能探查到整个散列地址空间。
(3)随机探测再散列
di = 伪随机数
这种方法需要建立一个随机数发生器，并给定一个随机数作为起点。
２. 链地址法
此方法为若哈希表长度为m,则将哈希表定义为一个有m个头指针组成的指针数组。散列地址为i的记录，均插入到以指针数组第i个单元为头指针的单链表中。
计算平均查找长度即所有比较次数的和除以所有数字个数。