查找

线性表的查找

顺序查找

1
2
3
4
5
6
7
8
9
10
11
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;
}
1
2
3
4
5
6
7
8
9
10
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;
}

折半查找/二分查找

注意：二分查找仅适用于有序递增或递减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

分块查找

见：查找(全)

数表的查找

二叉排序树

1
2
3
4
5
6
7
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)$$实现

  1. 散列函数和散列地址：$$p=H(key)$$，$$H$$为散列函数，$$p$$为散列地址
  2. 散列表：一个连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录
  3. 冲突和同义词：$$key_1\not=key_2$$，$$H(key_1)=H(key_2)$$，这种现象称为冲突，$$key_1$$，$$key_2$$互为同义词

散列函数的构造方法

  1. 数字分析法

    选取数码分布较为均匀的若干位作为散列地址

    设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。

    这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

  2. 平方取中法：取关键字的平方值的中间几位作为散列地址

    具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

  3. 折叠法

    将关键字分割成位数相同的几部分，然后取这几部分叠加和作为散列地址。根据数叠加的方式，可以把折叠法分为移位叠加、边界叠加。

    $$key=45387765213$$，表长为1000：

  4. 除留余数法
    $$
    H(key)=key%p
    $$
    $$p$$为不大于表长$$m$$但最接近或等于$$m$$的最大质数

    用质数取模，分布更均匀，冲突更少

  5. 直接定址法
    $$
    H(key)=key 或H(key)=a*key+b
    $$
    其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

处理冲突的方法

  1. 开放地址法

    所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为:
    $$
    H_i=(H(key)+d_i)%m,i=1,2…,k(k<=m-1)
    $$

    $$m$$为散列表表长；$$d_i$$为增量序列

    根据$$d$$的取值不同，可分为以下三种方法：

    1. 线性探测法
      $$
      d_i=1,2,3,…,m-1
      $$
      发生冲突时，每次往后探测相邻的下一个单元是否为空

      线性探测法很容易造成同义词、非同义词的“聚集(堆积)”现象，严重影响查找效率

      产生原因：冲突后再探测一定是放在某个连续的位置

    2. 二次探测法
      $$
      d_i=1^2,-1^2,2^2,-2^2,3^2,…,k^2,-k^2(k<=m/2)
      $$

    3. 伪随机探测法
      $$
      d_i=伪随机数序列
      $$

  2. 链地址法(拉链法)：把具有相同散列地址的记录放在同一个单链表中，称之为同义词单链表

散列表的查找

$$
\alpha=\frac{表中填入的记录值}{散列表的长度}
$$

$$\alpha$$：装填因子$$=ASL_{失败}$$

装填因子表示的是散列表装填的满不满，越大，越空；越小，越满。