数据结构与算法[6]----查找_结构体数组中按关键字查找满足条件的数据节点

1. 查找概论

查找表：是由同一类型的数据元素构成的集合。
关键字：数据元素中某个数据项的值，称为键值，用它可以标识一个数据元素。如果关键字可以唯一标识一个记录，那么称此关键字为主关键字。对于那些可以识别多个数据元素的关键字，我们称为次关键字。
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

2. 查找算法

2.1 顺序表查找

int Sequential_Search(int *a,int n ,int key)
{
	int i;
	for(i=0;i<=n;j++)
	{
		if(a[i]==key)
		return i;
	}
return 0; //没找到
}
1
2
3
4
5
6
7
8
9
10

2.2优化顺序表

顺序表查找每一个循环都需要进行判断是否越界，下列使用哨兵免去每一次都要进行判断。

int Sequential_Search2(int *a,int n,int key)
{
	int i;
	a[0]=key;
	i=n;
	while(a[i]=key)
	{
	i--;}
	return i;
}
1
2
3
4
5
6
7
8
9
10

2.3 折半查找

又称为二分查找，线性表必须采用顺序存储，每次查找取区间的中间位置作为上界或者下界。直到查找成功或者查找失败。

int Binary_Search(int *a ,int n,int key)
{
	int low,high,mid;
	low=1;
	high=n;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key <a[mid])
			high=mid-1;
		else if(key >a[mid])
		 	low=mid+1;
		 	else
		 	return mid;
	}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.4 插值查找

考虑查找并不是一定要折半的，可以1/4或者折更多，选取根据查找内容定义查找区间的方式进行查找。

int Binary_Search(int *a ,int n,int key)
{
	int low,high,mid;
	low=1;
	high=n;
	while(low<=high)
	{
		mid=low+(high-low)*(key-a[low])/(a[high]-a[low]);
		if(key <a[mid])
			high=mid-1;
		else if(key >a[mid])
		 	low=mid+1;
		 	else
		 	return mid;
	}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.5 线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程。

稠密索引：

在线性索引中，将数据集中的每个记录对应一个索引项，通过稠密索引的方式，将索引数值进行有序排列，再进行线性查找。

分块索引：

1. 块内无序，每一块内的记录不要求有序。
2. 块间有序，第二块内的数据其关键字一定要大于第一块内所有的记录的关键字。
   对于分块有序的数据集，将每一块对应一个索引项，这种索引方法叫做分块索引。我们定义

分块索引项结构分为三个数据项：

1. 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在他之后的下一块的最小关键字都要比当前块的最大关键字还要大。

2. 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在他之后的下一块的最小关键字都要比当前块的最大关键字还要大。

3. 存储了块中的记录个数，以便循环的时候使用。

4. 用于指向块首元素的指针，便于开始对这一块中的记录进行遍历。

2.6 二叉树查找

将数据形成一个二叉树，左孩子节点小于双亲节点，右孩子节点大于双亲节点。对数据进行二叉树构建。对二叉树进行中序遍历得到：
[35,37,47,51,58,62,73,88,93,99]

代码：

"""
递归查找二叉排序树T中是否存在key，
指针f指向T的双亲，其初始值调用值为NULL,
若查找成功，则指针p指向该数据元素的节点，并且返回TRUE，
否则指针p 指向查找路径上访问的最后一个节点并且返回。
"""
typedef struct BiTNode()
{
	int data;
	struct BiTNode *lchild ,*rchild; 
}BiTNode ,*BiTree

Status SearchBST(BiTree T,int key ,BiTree f ,BiTree *p)
{
	if(!T)
	{
		*p=f;
		return False;
	}
	else if(key==T->data)
	{
		*p=T;
		return True;
	}
	else if(key<T->data)
		return SearchBST(T->lchild,key,T,p);
	else
		return SearchBST(T->rchild,key,T,p);
}
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
28
29

二叉树插入操作

Status InsertBST(BiTree *T, int key)
{
	if(!SearchBST(*T ,key, NULL, &p))
	{
		s=(BiTree)malloc(sizeof(BiTNode));
		s->data=key;
		s->lchild=NULL;
		s->rchild=NULL;
		if(!p)
		{
			*T=s;
		}
		else if(key<p->data)
			p->lchild==s;
		else
			p->rchild=s;
		return TRUE;
	}
	else 
		return FALSE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

根据现有数据创建树：

int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i =0;i<10;i++)
{
	InsertBST(&T,a[i]);
}
1
2
3
4
5
6
7

二叉树的删除：

二叉树的删除针对叶子节点以及节点只有左孩子节点或者右孩子节点的时候，只有一个孩子节点的时候，可以“子承父业”，但是当有两个孩子节点的时候，则有些麻烦。

Status DeleteBST(BiTree *T ,int key)
{
	if(!*T)
		return FALSE;
	else
	{
		if(key == (*T)->data)
			return Delete(T);
		else if(key<(*T)->data)
			return DeleteBST( &(*T)->lchild,key）;
		else
			return DeleteBST(&(*T)->rchild,key);
	}
}

Status Delete(BiTree *p)
{
	BiTree q,s;
	if((*p)->rchild==NULL)
	{
		q=*p;*p=(*p)->lchild;free(q);
	}
	else if ((*p)->lchild==NULL)
	{
		q=*p;*p=(*P)->rchild;free(q);
	}
	else //左右子树都不是空的
	{
		q=*p;s=(*p)->lchild;
		while(s->rchild)
		{
			q=s;s=s->rchild;
		}
		(*p)->data=s->data;

		if(q!=*p)
			q->rchild=s->lchild;
		else
			q->lchild=s->lchild;
		free(s);	
	}
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

二叉树总结：

以链接的方式存储，保持了链接存储结构在执行插入或删除操作时，不用移动元素的优点，只要找到合适的插入和删除的位置，仅仅需要改动链表和指针要查找的节点的路径。插入删除的时间性能比较好，而对于二叉排序树的查找，从根节点开始进行查找，极端情况下等于根节点，或者等于树的深度，然后树的形状是不确定的

2.7 平衡二叉树

P358 ----------大话数据结构
是一种高度平衡的二叉排序树，即左子树和右子树都是平衡二叉树，且左子树和右子树的数量差值称为平衡因子，平衡因子的取值范围[-1,0,1]，只要二叉树上有一个节点的平衡因子不在范围内，则二叉树不平衡。
距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称为最小不平衡树。

当传入一个二叉排序树P，将它的左孩子节点定义为L，将L的右子树编程P的左子树，再将P改成L的右子树。，最后将L替换成P称为根节点。

二叉树支持动态的插入和查找，保证操作在O（height），但是有可能存在最坏的情况，平衡二叉树是为了将查找的时间复杂度保证在O（logn=(n)）内，主要有点集中于快速查找。

2.8 B-Tree 和 B+

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点;

1. 树种的每个节点最多拥有m个子节点且m>=2,空树除外（注：m阶代表一个树节点最多有多少个查找路径，m阶=m路,当m=2则是2叉树,m=3则是3叉）；

2. 除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个;（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)

3. 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子

4. 如果一个非叶节点有N个子节点，则该节点的关键字数等于N-1;

5. 所有节点关键字是按递增次序排列，并遵循左小右大原则；
   
   
   

B树节点的删除:

1. 当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1小于等于5

2. 满足左大右小的排序规则;

3. 关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放.

在B树结构中，我们往返于每个节点之间也就希望，我们必须得在硬盘得页面进行多次访问，遍历夏下列这棵树得时候，都会对节点中得元素进行一次遍历，如何让遍历得是的时候每个元素只访问一次？
B+树结构

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

1. B+跟B树不同,B+树的非叶子节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字大大增加；

2. B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；

3. B+树的根节点关键字数量和其子节点个数相等;

4. B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；

3. 哈希表

3.1各类散列方式

散列基础既是一种存储技术，也是一种查找方法。

散列技术是在记录存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应的一个存储位置f(key)。我们把对应关系f（）称为散列函数，又称为哈希（Hash）函数，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表。

散列技术最适合的求解问题是查找与给定值相等的记录。可能会遇到key1!=key2 但是经过散列函数计算过后的数值相等，这种现象称之为冲突，并且key1与key2称为这个散列函数的同义词。冲突很糟糕，如何处理冲突是一个很重要的课题。

直接定址法：
直接根据某个关键字进行直接确定地址。

也可以取关键字的某个线性函数作为散列值：
f(key)=a*key+b (a,b)为常数 这样的散列函数是简单并且均匀的，也不会产生冲突，但是需要事先知道关键字的分布情况，适合查找表比较小而且连续的情况。

数字分析法
例子：针对关键字位数比较多的数字，例如11位手机号：130xxxxxxxx1234 ，前三位为接入号，后四位为用户号，可以采用后四位作为散列地址，如果后四位依旧容易冲突，可以再对四位进行反转，左移，右移等操作。

平方取中：
假设为123，则平方后为1522756，再抽取中间的三位即 227.用作为散列地址。

折叠法：
将关键字从左到右分割成位数相等的几部分，再将这几部分求和，按照散列列表表长，取最后几位作为散列地址。

除留余数法：
最为常用：f(key)=key mod p(p<=m)mod是取模运算，不仅可以直接对关键字进行取模，也可以先对关键字进行平方后，再进行取模运算，该方法的关键在于如何选取合适的p，如果p选取不好，则会造成冲突的情况。

随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址，也就是f(key)=random(key)，这里的random是随机函数，当关键字长度不等的时候，采用这种方式比较合适。

选择散列函数的参考方式：

1. 计算散列地址所需要的时间
2. 关键字的长度
3. 散列表的大小
4. 关键字的分布情况
5. 记录查找的频率

3.2 处理散列冲突方法

3.2.1 开放地址法

当一旦发生冲突，就去寻找下一空的散列地址，只要散列列表够大，空的地址总能找到并且将记录存入：
fi(key)=(f(key)+di) MOD m (di=1，2，3...m-1)

比如说，我们的关键字合集为{12，67，56，16，25，37，22，29，15，47，48，34}，表长为12，当散列函数f(key)=key mod 12,当计算f(key)=key mod 12时：

37的散列值和25的散列值发生冲突，此时地址存入的是1，则冲突后+1 存入地址下标为2中，

这种解决冲突的开放式定数值法称为线性探测法，由于A,B冲突后，B占据了别的哈希值的位置，导致原本B,C不是同义词缺需要抢夺一个位置的情况，称为堆积。
其中可以改进为：二次探测法，以及随机探测法。
二次探测：将d改为双向的，不仅可以向后方寻找空的地址，也可以向前方寻找空的地址。
随机探测法：可以随机生成一个探测值d，利用d进行移位探测。

3.2.2 再散列函数法

对于散列表而言，实现准备多个散列函数：fi(key)=RHi(key) (i=1,2,3,4.....,k)这里的RHi就是不同的散列函数，包括前方列的所有散列函数，当散列地址发生冲突的时候，那么就换一个散列函数进行计算，总有散列函数能解决掉冲突。

3.2.3 链地址法

为什么冲突了就要换地方了？直接原地想办法？ so 链地址法应运而生，这种方法原理就像是哈希桶，对于同一散列值的数据放入一同一个桶里。直接用链表进行链接冲突项，但是会有搜索单链表的时候的性能损失。

3.2.4 公共溢出区法

直接开辟一个存储空间存储所有冲突的区域，即溢出表存储溢出的数据。

3.3 散列表查找实现

/*定义一个散列表，相关常数，HashTable就是散列表结构，elem是一个动态数组*/
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
	int *elem;  //elem[]
	int count;
}HashTable;
1
2
3
4
5
6
7
8
9
10

有了结构的定义，可以对散列进行初始化

Status InitHashTable(HashTabls *H)
{
	int i;
	m=HASHSIZE;
	H->count=m;
	H->elem=(int *) malloc (m*sizeof(int));
	for(i=0;i<m;i++)
	{
		H->elem[i]=NULLKEY;
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

散列函数

int Hash(int key)
{
	return key%m;
}
1
2
3
4

对散列表进行插入操作

void InserHash(HashTable *H, int key)
{
	int addr=Hash(key); //求得hash地址
	while(H->elem[addr]!=NULLKEY)
		addr=(addr+1)%m;
	H->elem[addr]=key;
}
1
2
3
4
5
6
7

散列表存在后，在需要时通过散列表查找要的记录

//因为是放到下一空地址，所以如果遇到了空地址，或者一个循环，那么说明没有该元素。
Status SearchHash(HashTable H ,int key,int *addr)
{
	*addr=Hash(key);
	while(H.elem[*addr]!=key)
	{
		*addr=(*addr+1)%m;  //开放定址的线性探测
		if(H.elem[*addr]==NULLKEY || *addr ==Hash(key))
			return UNSUCCESS;    //
	}
	return SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.4 性能分析

如果没有冲突，散列查找是查找算法中效率最高的，因为时间复杂度位1，但是往往有冲突的情况存在，一般平均查找长度取决于以下因素：

1. 散列是否均匀，散列函数的好坏直接影响出现冲突的频繁程度，不过由于不同的散列函数对同一随机的关键字，产生冲突的可能性是相同的，因此不考虑它对平均查找长度的影响。
2. 处理冲突的方式，相同的散列后汉书，处理冲突的方法不同，会使得平均查找长度不同。
3. 散列表的装填因子 装填因子=填入表中的记录个数/散列表长度，α标志着散列表的装满的程度。α的数值越大，则出现冲突的概率越高，即散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。

4.总结

围绕主题“查找”，其中二叉树排序树是动态查找最重要的数据结构，查找，插入和删除的效率也都很高，合理的二叉树结构是高效查找的必要条件，因此如何构建平衡二叉树是重点。
散列表是一种高效的查找方法，也是掌握的重点。