查找

查找表——用于查找的数据集合，由同一类型的数据元素组成
关键字——数据元素中唯一标识该元素的某个数据项的值，查找结果应该是唯一的

操作

查找

静态查找表——仅关注查找速度就可以

插入删除

动态查找表——出了查找速度，也要方便实现插删操作

评价指标

查找长度——在查找运算中，需要对比的关键字次数称为查找长度
平局查找长度(ASL)——所有查找过程中进行关键字比较的次数

查找成功ASL=$$\frac{n+1}{2}$$
查找失败ASL=$$ n+1 $$

顺序查找

1
2
3
4
5
6
7
8
9
10
11
typedef struct{
	ElemType *elem;
	int length;
}SSTable;

int Search_seq(SSTable ST,ElemType key){
	int i;
	for(int i=0;i<ST.length && ST.elem[i]!=key;i++){
		return i==ST.length ? -1:i; //若查找到则返回元素下标否则返回-1
	}
}

哨兵——无需判断是否越界

1
2
3
4
5
6
7
8
9
10
typedef struct{
	ElemType *elem;
	int length;
}SSTable;

int Search_seq(SSTable ST,ElemType key){
	St.elem[0]=key;  //哨兵节点
	for(int i=St.length;ST.elem[i]!=key;i--)  //从后往前查
		return i;  /查找成功返回i，失败返回0
}

查找表的优化
查找表中元素有序存放
ASL失败=
$$ \frac{n}{2}+\frac{n}{n+1} $$
被查概率不相等
被查概率大的放在前边

折半查找(二分查找)

	————仅适用于从小到大的顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Binary_search(SSTable ST, ElemType key)
{
    int low = 0;
    int high = ST.length-1;
    int mid;
    while (low <= high)
    {
        int mid = (low+high)/2;
        if (ST.elem[mid] == key )
            return mid;
        else if (ST.[mid] > key)
            high=mid-1;
        else if (ST.[mid] < key)
            low=mid+1;
    }
    return -1;
}

二叉排序树(BST)

查找

左子树节点值<根节点值<右子树节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef struct BSTNode{
	int key;
	sttruct BSTNode *lch,*rch;
}BSTNode,*BSTree;

//非递归
BSTree BST_Search(BSTree T,int key){
		while(T!=NULL && key!=T->key){
			if(key<T->key)
				T=T->lch;
			else
				T=T->rch;	
		}
		return T;
}

//递归
BSTree BST_Search(BSTree T,int key){
	if(T==NULL)
		return NULL;
	if(key<T->key)
		BST_Search(T->lch,key);
	else if(key > T->key)
		BST_Search(T->rch,key);
	else if(key == T->key)
		return T;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BST_Insert(BSTree &T,int key){
	if(T==NULL){ //若树为空，则新建节点插入
		T = new BSTNode;
		T->key=key;
		T->lch=T->rch=NULL;
		return 1; //插入成功
	}
	else if(key==T->key)  //存在相同节点，插入失败
		return 0;
	else if(key<T->key)
		return BST_Insert(T-lch,key);
	else if(key>T->key)
		return BST_Insert(T->rch,key);
}

创建BST

1
2
3
4
5
6
7
8
void Create_BST(BSTree &T,int str[],int n){
	T=NULL;
	int i=0;
	while(i<n){
		BST_Insert(T,str[i]);
		i++;
	}
}

删除

删除根节点时，需要在其右子树中选取最小的右孩子替代根节点

散列表查找(哈希表)

存储位置=f(关键字)
f为哈希函数

除留余数法

Hkey()=key%p
p一般取小于等于表长的最大质数，以降低冲突概率

冲突解决

当两个数的存储位置相同时，后来的数需要向后遍历，直到遍历到一个空位置，然后存入，当遍历到最后一位后需要从头开始遍历(首尾相接)