查找（只含代码）
2023年8月8日大约 4 分钟
查找
线性表的查找
顺序查找
int SerchSqList(SqList &L,int e)
{
for(int i = 0;i<L.length;i++)
{
if(e == L.elem[i]){
cout<<"已找到元素"<<L.elem[i]<<endl;
return e;
}
}
return 0;
}int SearchSqList2(SqList &L,int e)
{
int i;
L.elem[0] = e;
for(i = L.length;L.elem[i] != e;--i){
}
cout<<"元素的位置为"<<i+1<<endl;
return 0;
}折半查找/二分查找
注意：二分查找仅适用于有序递增或递减
int SearchBin(SqList &L,int e)
{
int low = 1;
int high = L.length;
int mid = 0;
while(low <= high){
mid = (low+high)/2;
if(L.elem[mid] = e){
cout<<"找到元素"<<e<<endl;
return 0;
}else if(e<L.elem[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
return 0;
}分块查找
见：查找(全)
数表的查找
二叉排序树
BSTree SearchBST(BSTree T, KeyType key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if ((!T) || key == T->data.key) return T;//查找结束
else if (key < T->data.key) return SearchBST(T->lchild, key);//在左子树中继续查找
else return SearchBST(T->rchild, key);//在右子树中继续查找
}散列表的查找
散列表的基本概念
散列表(哈希表)，是一种数据结构，特点是：数据元素的与其直接相关
如何建立“关键字”与“存储地址”的联系？
通过“散列函数(哈希函数)”：$$Add=H(key)$$实现
- 散列函数和散列地址：$$p=H(key)$$，$$H$$为散列函数，$$p$$为散列地址
- 散列表：一个连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录
- 冲突和同义词：$$key_1\not=key_2$$，$$H(key_1)=H(key_2)$$，这种现象称为冲突，$$key_1$$，$$key_2$$互为同义词
散列函数的构造方法
数字分析法
选取数码分布较为均匀的若干位作为散列地址
设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。
这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
平方取中法：取关键字的平方值的中间几位作为散列地址
具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
折叠法
将关键字分割成位数相同的几部分，然后取这几部分叠加和作为散列地址。根据数叠加的方式，可以把折叠法分为移位叠加、边界叠加。
其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
处理冲突的方法
开放地址法
所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为:
d_i=1,2,3,...,m-1
d_i=12,-12,22,-22,32,...,k2,-k^2(k<=m/2)
d_i=伪随机数序列
散列表的查找
装填因子表示的是散列表装填的满不满，越大，越空；越小，越满。