09-查找

顺序查找法、折半查找法、分块查找法

顺序查找法

//顺序表顺序查找法
int Search(int a[],int n,int k){
	int i;
	for(i=0;i<=n;i++){
		if(a[i]==k) return i;
	}
	return -1;
}
//链表顺序查找法
LNode *Search(LNode *head,int key){
	LNode *p=head->next;
    while(p!=NULL){
    	if(p->data==key) return p;
    	p=p->next;
    }
    return NULL;
}

3	1	0	2	5	8	F
1次	2次	3次	4次	5次	6次	7次

p_i=1/n;

查找成功：ASL₁=C₁*P₁+…+C_iP_i+…+C_n*P_n=7/2;

查找失败：ASL₂=7

折半查找法

折半查找判定树构造：

下标	0	1	2	3	4	5	6	7	8	9	10	11	12
关键字	k1	k2	k3	k4	k5	k6	k7	k8	k9	k10	k11	k12	k13

1）T1中各结点下标范围0~12

2)（0+12）/2=6，T1根结点为K7。T1左子树T2下标范围0到5，T1右子树T3下标范围7到12；

3）(0+5)/2=2,T2根结点为K3。T2左子树T4下标范围0到1，右子树T5范围3到5；

4）(7+12)/2=9,T3根结点为K10，T3左子树T6,下标范围7到8，右子树T7下标范围为10到12；

5）(0+1)/2=0可知，T4根结点为K1。T4左子树空，右子树只有一个结点K2，T4结束；

6）(3+5)/2=4可知，T5根结点为K5，T5左子树只有一个结点K4，右子树也只有一个结点K6，T5结束；

7）(7+8)/2=7可知，T6根结点为K8。T6左子树空，右子树只有一个结点K9，T6处理结束；

8）(10+12)/2=11可知，T7根结点为K12。T7左子树只有一个结点K11，右子树只有一个结点K13，T7处理结束；

查找成功时：

关键字	k1	k2	k3	k4	k5	k6	k7	k8	k9	k10	k11	k12	k13
比较次数	3	4	2	4	3	4	1	3	4	2	4	3	4

ASL₁=(3+4+2+4+3+4+1+3+4+2+4+3+4)/13=41/13;

查找失败时，即空指针处的比较次数：

查找不成功的位置	1	2	3	4	5	6	7	8	9	10	11	12	13	14
比较次数	3	4	4	4	4	4	4	3	4	4	4	4	4	4

ASL₂=(3+4+4+4+4+4+4+3+4+4+4+4+4)/14=27/7;

折半查找法要求线性表是有序的（假设是递增有序的）

//顺序表折半查找法
int Bsearch(int a[],int low,int high,int k){
	int mid;
	while(low<=high){
		mid=(low+high)/2;
		if(a[mid]==k)	return mid;
		else if(a[mid]>k)	high=mid-1;		//说明需要在左边找
		else low=mid+1;
	}
	return -1;
}

分块查找法（索引顺序查找）

分块查找把线性表分为若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按照关键字大小有序排列，即前一块中的最大关键字一定要小于后一块中的最小关键字。

//索引表
typedef struct{
	int maxKey;				//块内最大关键字
	int low,high;			//记录块中第一个和最后一个元素的位置
}indexElem;
indexElem index[maxSize];	//定义索引表，maxSize为已定义的常量

索引表上使用折半查找,块内使用顺序查找。

平均查找长度=折半查找平均查找长度+顺序查找平均查找长度；

二叉排序树与平衡二叉树

二叉排序树

定义

二叉排序树或者是空树，或者是满足一下性质的二叉树：

1）左左子树不空，则左子树上所有关键字均小于根关键字的值；

2）若右子树不空，则右子树上所有关键字均大于根关键字的值；

3）左右子树有各是一颗二叉排序树；

二叉排序树的存储结构

二叉排序树通常用二叉链表进行存储，其结点定义与一般二叉树类似

typedef struct BTNode{
	int key;
	struct BTNode *lchild;
	struct BTNode *rchild;	
}BTNode;

查找关键字

BTNode *BSTSearch(BTNode *bt,int key){
	if(bt=NULL){
		return NULL;						//查找不成功返回NULL
	}else if(bt->key==key){
		return bt;
	}else if(bt->key>key){
		return BSTSearch(bt->lchild,key);	//小于根结点中的关键字到左子树中查找
	}else{
		return BSTSearch(bt->rchild,key);	//大于根结点中的关键字到右子树中查找
	}
}

插入关键字

插入一个关键字首先要找到插入位置，对于一个不存在于二叉排序树中的关键字，其查找不成功的位置即为该关键字的插入位置。

int BSTInsert(BTNode *&p,int key){		//p用了指针引用型，因为p可能找到一个空指针位置，需要对空指针做改变
	if(p==NULL){
		p=(BTNodde*)malloc(sizeof(BTNode));
		p->lchild=p->rchild=NULL;
		p->key=key;
		return 1;
	}else{
		if(key==p->key){				//待插入关键字已存在于树中，插入失败
			return 0;
		}else if(key<p->key){
			return BSTInsert(p->lchild,key);
		}else{
			return BSTInsert(p->rchild,key);
		}
	}
}

二叉排序树的构造

void CreateBST(BTNode *&bt,int key[],int n){
	int i;
	bt=NULL;					//将树清空
	for(i=0;i<n;i++){			//调用插入函数，诸葛插入关键字
		BSTInsert(bt,key[i]);
	}
}

删除关键字

1）被删除的结点为叶子结点，则直接删除

2）被删除的结点只有左子树或只有右子树

3）被删除结点左右子树都存在，将前驱结点的值保存在当前结点，继而删除前驱结点

平衡二叉树

平衡二叉树的建立与建立二叉排序树的简易基本一样，不同的是在建立平衡二叉树的时候，每插入一个新的关键字都要进行检查，看是否新关键字的插入会使得原平衡二叉树失去平衡，即树中出现平衡因子绝对值大于1的结点，如果失去平衡则需要进行平衡调整。

平衡调整

1）LL型（左子树根结点的左子树上插入新结点，顺时针）

2）RR型（右子树根结点的右子树上插入新结点，逆时针）

3）LR型（左子树根结点的右子树上插入新结点,先逆时针，再顺时针）

4）RL型（右子树根结点的左子树上插入新结点,先顺时针，再逆时针）

B-树（B树）和B+树

B-树的基本概念

1）每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点则至少有2个分支，非根非叶子结点至少有m/2个分支；

2）有n个分支的结点有n-1个关键字，他们按递增顺序排列，k=2(根结点)或（m/2非根节点）；

3）每个结点结构为：

n	k1	k2	…	kn
P0	P1	P2	…	Pn

其中n为该结点中关键字个数；K_i为该结点关键字且满足K_i<K_i+1;

P_i为该结点的孩子结点指针且满足P_i所指结点上的关键字大于K_i且小于K_i+1,P₀所指结点上的关键字小于K₁，P_n所指结点上的关键字大于K_n;

4）结点内各关键字互不相等且按从小到大排列；

5）叶子结点处于同一层，可以用空指针表示，是查找失败到达的位置；

解释上图五条特性：

1）结点的分支数=关键字数+1，最大分支数为B-树的阶数，因此B-树中结点最多有m个分支，上图是一颗5阶B-树；

2）图中除了根结点有两个分支外，其他所有结点至少有（5/2）=3个分支；

3）如果根结点中没有关键字就没有分支，此时B-树是空树；如果根结点中有关键字，则其分支数必大于或等于2，因为分支数等于关键字+1；

4）除根结点外，结点中关键字个数至少为2；结点内关键字有序，并且在同一层上，左边结点内所有关键字均小于右边结点内的所有关键字

下层关键字取值总是落在上层结点关键字划分的区间内，具体落在那个区间可由指向他的指针看出来

5）图中B-树的叶子结点均落在第4层，代表查找不成功的位置

B-树的基本操作

查找关键字

插入关键字

原始序列：{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}

删除关键字

B+树

1）B+树中具有n个关键字的结点含有n个分支；B-树中，具有n个关键字的结点含有n+1各分支；

2）B+树中，每个结点（除根结点）中关键字个数n的取值范围为┎m/2┒≤n≤m,根结点取值范围为2≤n≤m;B-树中，他们的取值范围分别为┎m/2┒-1≤n≤m-1和1≤n≤m-1;

3）B+树中叶子结点包含信息，并且包含了全部关键字，叶子结点引出的指针指向记录；

4）B+树中的所有非叶子结点仅起到一个索引的作用，即结点中的每个索引项值含有对应子树的最大管关键字和指向该子树的的指针，不含有该关键字对应记录的存储地址；B-树中，每个关键字对应一个记录的存储地址；

5）在B+树上有一个指针指向关键字最小的叶子结点，所有叶子结点链接成一个线性链表；B-树没有。

散列表

概念

根据关键字的值来计算出关键字在表中的地址；

函数值ad=H(key);

关键字序列为{7,4,1,14,100,30,5,9,20,134}，设Hsh函数为：H(key)=key Mod 13(除以13取余),试给出表长为15的Hash表？

1）H(7)=7 H(4)=4 H(1)=1 H(14)=1 H(100)=9 H(30)=4 H(5)=5 H(9)=9 H(20)=7 H(134)=4

2）插入表中，表中某些位置上有冲突

地址	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
关键字		1,14			4,30,134	5		7,20		100,9

3）解决冲突利用公式H_i(key)=(H(key)+1) Mod len,i属于1~len-1,len为表长，边建表边检测冲突，当发生冲突时立即解决冲突，执行过程如下表所示

关键字	用Hash函数计算地址	是否冲突	解决冲突	地址
7	7 Mod 13=7	否	无	7
4	4 Mod 13=4	否	无	4
1	1 Mod 13=1	否	无	1
14	14 Mod 13 =1	是	从冲突地址后移一位，得到新地址2，不冲突	2
100	100 Mod 13=9	否	无	9
30	30 Mod 13=4	是	从冲突地址后移一位，得到新地址5，不冲突	5
5	5 Mod 13=5	是	从冲突地址后移一位，得到新地址6，不冲突	6
9	9 Mod 13=9	是	从冲突地址后移一位，得到新地址10，不冲突	10
20	20 Mod 13=7	是	从冲突地址后移一位，得到新地址8，不冲突	8
134	134 Mod 13=4	是	从冲突地址后移一位，得到地址5，仍然冲突，继续后移知道到达新地址11，不冲突	11

4）由此得到新Hash表

地址	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
关键字	空	1	14	空	4	30	5	7	20	100	9	134	空	空	空

查找关键字

先用Hash函数计算出一个地址，然后用key和这个地址上的关键字进行比较

​ 1）如果当前地址上为空，则证明查找失败；

​ 2）如果key和当前地址上关键字值相同，则证明查找成功；

​ 3）如果不相同，则根据冲突处理方法到下一个地址继续比较，知道相同为止，证明查找成功；

​ 4）如果按照冲突处理方法需找地址过程中又遇到空位置，则证明查找失败；

关键字查找成功比较次数：

关键字	1	14	4	30	5	7	20	100	9	134
比较次数	1	2	1	2	2	1	2	1	2	8

ASL₁=(1+1+2+1+2+2+1+2+1+2+8)/10=11/5;

关键字查找失败比较次数：

地址	由地址开始到空位置为止所要发生比较操作的地址	比较次数
0	0	1
1	1,2,3	2
2	2,3	2
3	3	1
4	4,5,6,7,8,9,10,11,12	9
5	5,6,7,8,9,10,11,12	8
6	6,7,8,9,10,11,12	7
7	7,8,9,10,11,12	6
8	8,9,10,11,12	5
9	9,10,11,12	4
10	10,11,12	3
11	11,12	2
12	12	1

ASL₂=(1+2+2+1+9+8+7+6+5+4+3+2+1)/13=4

注意：查找不成功的位置是Hash函数所能映射到的位置，而不是表中所有位置i

常见的Hash函数构造方法

直接地址法

取关键字或关键字的某个线性函数为Hash地址，即：

H(key)=key 或者 H(key)=a*key+b,其中a和b为常数;

数字分析法

适用于关键字位数比较多且表中可能关键字都是已知情况；

分析的原则是尽量取冲突较少的位数段；

例如存储电话号码，由于前七位重复率较高，所以我们挑选电话号码的后四位组成Hash地址；

平方取中法

取关键字平方后的中间几位作为Hash地址。一个数平方后的中间几位数和数的每一位都相关，由此得到的Hash地址随机性更大。

除留余数法

取关键字被某个不大于Hash表表长m的数p出后所得的玉树为Hash地址，即：

H(key)=key Mod p(p≤len);

在本方法中，p的选择很重要，一般p选择小于或者等于表长的最大素数，这样可以减少冲突；

常见的Hash冲突处理方法

开放定址法

1）线性探测法

即概念中所举得例子用到的冲突解决方法；

H_i(key)=(H(key)+1) Mod len,i属于1~len-1,len为表长;

**特点：**可以探测到表中所有位置但是易产生堆积问题；

2）平方探测法

设发生冲突的地址为d，则探测到的新地址为：d+1²、d-1²、d+2²、d-2²、d+3²、d-3²…；

**特点：**不可以探测到表中所有位置（至少可以探测到一位置），但不容易出现堆积问题；

链地址法

例子

用关键字序列{1,9,12,11,25,35,17,29}创建一个Hash表，装填因子a为1/2，试着确定表长len，采用除留余数法构造Hash函数，采用链地址法来处理冲突？

**装填因子：**a=n/m(n是关键字个数，m为表长)；因此表长len=16；

**除留余数法：**H(key)=key Mod p,其中p为不大于表长的最大素数，所以p=13,Hash函数为Hash(key)=key Mod 13;

查找关键字成功比较次数：

关键字	1	29	17	9	35	11	12	25
比较次数	1	1	1	1	2	1	1	2

ASL₁=(1+1+1+1+2+1+1+2)/8=5/4=1.25;

查找关键字失败比较次数：

地址	0	1	2	3	4	5	6	7	8	9	10	11	12
比较次数	0	1	0	1	1	0	0	0	0	2	0	1	2

ASL₂=(0+1+0+1+1+0+0+0+0+2+0+1+2)/13=8/13=0.65;

| 1 | 2 |

ASL₁=(1+1+1+1+2+1+1+2)/8=5/4=1.25;

查找关键字失败比较次数：

地址	0	1	2	3	4	5	6	7	8	9	10	11	12
比较次数	0	1	0	1	1	0	0	0	0	2	0	1	2

ASL₂=(0+1+0+1+1+0+0+0+0+2+0+1+2)/13=8/13=0.65;