查找总结

顺序表的查找

顺序查找（线性查找）：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等则查找成功，找到所查的记录，如果直到最后一个（或第一个）记录，其关键字和给定值比较都不相等时，则表中没有所查的记录，查找不成功。

/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if (a[i]==key)
			return i;
	}
	return 0;
}

可以设置一个哨兵，这样便不用每次让i与n比较，这样在数据较多时，可以大大提高效率。

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
	int i;
	a[0]=key;
	i=n;
	while(a[i]!=key)
	{
		i--;
	}
	return i;
}

顺序表查找最优情况是O(1)，最坏为O(n),平均为O(n)。

有序表的查找

当线性表中的记录是关键码有序的(通常从大到小有序），且采用顺序存储结构，此时可以使用折半查找。其基本思想是：在有序表中取中间记录作为比较对象，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。其复杂度为O(logn)

/* 折半查找 */
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;		/* 若相等则说明mid即为查找到的位置 */
		}
		
	}
	return 0;
}

二叉查找树

二叉排序树又称二叉查找树，它或者是一颗空树，或者是具有下列性质的二叉树：

1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2.若它的右子树不空，则左子树上所有结点的值均大于它的根结点的值；

3.它的左右子树也分别为二叉排序树；

二叉查找树的结构定义

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode	/* 结点结构 */
{
	int data;	/* 结点数据 */
	struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
} BiTNode, *BiTree;

二叉查找树的查找：

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
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);  /*  在右子树中继续查找 */
}

二叉查找树的插入操作

/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) 
{  
	BiTree p,s;
	if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;  
		s->lchild = s->rchild = NULL;  
		if (!p) 
			*T = s;			/*  插入s为新的根结点 */
		else if (key<p->data) 
			p->lchild = s;	/*  插入s为左孩子 */
		else 
			p->rchild = s;  /*  插入s为右孩子 */
		return TRUE;
	} 
	else 
		return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
}

二叉查找树的删除

二叉树的删除可分为三种情况

1.删除叶子结点；

2.仅有左右子树的结点；（结点删除之后，将他的左右子树整个移动到删除结点的位置）

3.左右子树都有的结点；（找到需要删除结点p的（中序遍历后的）直接前驱（或直接后继）s，用s来替换p然后再删除此结点s）

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
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; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
		if(q!=*p)
			q->rchild=s->lchild; /*  重接q的右子树 */ 
		else
			q->lchild=s->lchild; /*  重接q的左子树 */
		free(s);
	}
	return TRUE;
}

/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
	if(!*T) /* 不存在关键字等于key的数据元素 */ 
		return FALSE;
	else
	{
		if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
			return Delete(T);
		else if (key<(*T)->data)
			return DeleteBST(&(*T)->lchild,key);
		else
			return DeleteBST(&(*T)->rchild,key);
		 
	}
}

平衡二叉树（AVL树）

也是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1.将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子（BF），那么平衡二叉树上所有结点的平衡因子只可能是-1,0,1。

距离插入节点最近的且平衡因子的绝对值大于1的结点为根的子树，我们称之为最小不平衡子树（如图）。

平衡二叉树的构建思想是：在构建二叉排序树的过程中，每当插入一个结点，先检查是否因插入而破坏了树的平衡，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下调整最小不平衡子树之间的链接关系，进行相应的旋转，使之成为新的平衡子树。结点平衡因子BF大于1时就右旋，小于-1时就左旋，当插入结点后，最小不平衡子树的BF与它的子树BF符号相反时，先对结点进行一次旋转以使得符号相同后，再反向旋转一次才能完成平衡操作。（如图平衡二叉树，插入9）此时查找，插入和删除的时间复杂度均为O(logn)。

多路查找树

多路查找树：其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

2-3树

定义：首先它是一颗多路查找树，其中每一个结点都具有两个孩子（我们称之为2结点）或三个孩子（我们称之为3结点）。一个2结点包含一个元素和两个孩子（或没有孩子）

其左子树包含的结点小于该元素，右子树包含的结点大于该元素。一个3结点包含一小一大两个元素和三个孩子（或者没有孩子），若果有三个结点那么左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素且2-3树所有的叶子都在同一层上。

B树

定义：是一种平衡的多路查找树，2-3树即是B的特例，结点最大的孩子数目称为B树的阶。

它具有如下属性：

1.如果根结点不是叶子结点，则其至少有两颗子树；

2.每一个非根的分支节点都有k-1个元素和k个孩子，其中[m/2]<=k<=m，每一个叶子结点n都有k-1个元素，其中[m-2]<=k<=m；

3.所有分支结点包含下列信息（n,A0,K1,A1,K2...Kn,An),其中Ki(i=1,2...n)为关键字,且Ki<Ki+1;Ai为指向子树根结点的指针，且Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,3...n),An所指子树中所有结点的关键字均大于Kn,n为关键字个数[m-2]-1<=n<=m-1；

4.所有叶子结点都位于同一层次；

B加树

1.有n颗字数的结点中包含有n个关键字；

2.所有叶子结点包含全部的关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序连接；

3.所有分支结点可以看成是索引，结点中仅含有其子树中的最大或最小关键字；

如果随机查找就从根结点出发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，它也只是用来索引的不能提供实际记录的访问，还需要到达包含此关键字的终端结点，如果需要从最小关键字进行从小到大的查找

散列表查找（哈希表）

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

散列技术最适合的求解问题是查找与给定值相等的记录。

散列函数的构造方法：

如果是字符串可以直接使用字符串的ASCLL值。

直接定址法

取关键字的某个线性函数值为散列地址：

f(key)=aXkey+b

这样的散列函数优点就是简单，均匀也不会产生冲突，但需要事先知道关键字的分布情况，适合查找表较小且连续的情况。

数字分析法

抽取方法是使用关键字的一部分来计算散列存储位置的方法。它适合处理关键字位数比较大的情况，如果事先知道关键字分布且关键字若干位分布较均匀，可以使用这种方法。

平方取中

对所取关键字求平方然后取中间的几位，它适合不知道关键字的分布，而位数又不是很大的情况。

折叠法

将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按照散列表的表长，取后几位作为散列地址。它适合事先不知道关键字的分布，但关键字位数较多的情况。

除留余数法

对于散列表长为m的散列公式为f(key)=key mod p(p<=m),mod为取模（求余运算）。

随机数

选择一个随机数，取关键字的随机函数值作为它的散列地址，f(key)=random(key)。random是随机函数。

在设计散列函数时，需要综合考虑以下几种情况：

1.计算散列地址所需要的时间；

2.关键字的长度；

3.散列表的大小；

4关键字的分布情况；

5.记录查找的频率；

处理散列冲突的方法

当key1≠key2，但是f(key1)=f(key2)这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。

开放定址法

一旦发生了冲突就去寻找下一个空的散列函数，只要散列函数表足够大，空的散列地址总能找到，并将记录存入。

1.线性探测法

在线性探测法中f(key)是key的线性函数fi(key)=(f(key)+di) MOD m(di = 1,2,3,4...m-1)，不断地调用知道找到空余的位置

2.二次探测法

fi(key)=(f(key)+di) MOD m(di = 1,-1,4,-4...q²,-q²，q<=m/2)

这样可以双向寻找到可能的空位置，另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。

3.随机探测法

fi(key)=(f(key)+di) MOD m(di 是一个随机数列)这里的di是伪随机数。

再散列函数法

可以事先准备多个散列函数，当发生冲突时调用不同的散列函数，总有一个能解决冲突。

链地址法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

例如对于关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}以12为除数进行除留余数法可得如图结构

公共溢出区法

凡是出现冲突的关键字，另外建一个溢出区存放。

对给定的值通过散列函数计算散列地址后，先与基本表相应位置进行对比，如果相等，则成功，如果不等，则到溢出表去进行顺序查找。