内容纲要

查找:是对已存入计算机中的数据所进行的一种运算,在数据元素集合中查找满足某种条件的数据元素的过程。采用何种查找方法,首先取决于使用哪种数据结构来表示“表”,即表中数据元素是按何种方式组织的。

查找表:是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。

静态查找表:检索某个“特定的”数据元素的各种属性, 则称此类查找表为静态查找表。

动态查找表:若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表。

关键字:是数据元素中的某个数据项。唯一能标识数据元素(或记录)的关键字,即每个元素的关键字值互不相同,我们称这种关键字为主关键字;若查找表中某些元素的关键字值相同,称这种关键字为次关键字。

平均查找长度ASL:由于查找运算的主要运算是关键字的比较,所以通常把查找过程中和给定值进行比较的关键字个数的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。ASL(n)=ΣPiCi其中n个元素,pi是查找第i(1≤i≤n)个元素的概率,一般地,除特别指出外,均认为每个元素的查找概率相等,即pi=1/n,ci是找到第i个元素所需进行的比较次数。

静态查找

顺序查找

顺序查找:又称为线性查找,是一种最简单的查找方法。

查找步骤:将查找表作为一个线性表,可以是顺序表,也可以是链表,依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较,若某个记录的关键字值与给定值相等,则查找成功,返回该记录的存储位置,反之,若直到最后一个记录,其关键字值与给定值均不相等,则查找失败,返回查找失败标志。

代码实现:

//----- 典型的关键字类型说明-----
typedef float KeyType ; /* 实型*/
typedef int KeyType ; /* 整型*/
typedef char KeyType ; /* 字符串型*/
//----- 数据元素类型的定义-----
typedef struct RecType {
	KeyType key ; /* 关键字码*/
	otherinfo /* 其他域*/
} RecType ;
/* 对数值型关键字*/
#define EQ(a, b) ((a)==(b))
#define LT(a, b) ((a)<(b))
#define LQ(a, b) ((a)<=(b))
/* 对字符串型关键字*/
#define EQ(a, b) (!strcmp((a), (b)) )
#define LT(a, b) (strcmp((a), (b))<0 )
#define LQ(a, b) (strcmp((a), (b))<=0 )
// ------ 静态查找表的顺序存储结构------
typedef struct {
// 数据元素存储空间基址,建表时按实际长度分配,0号单元留空
	ElemType *elem;
	int length; // 表长度
} SSTable;

int SeqSearch(SSTable ST, KeyType k) //顺序查找算法
{
	int i=0;
	while (i<ST.length && ST.elem[i]!=k) //从表头往后找
		i++;
	if (i==ST.length) //未找到返回0
		return 0;
	else
		return i+1; //找到后返回其逻辑序号i+1
}

int Search_Seq(SSTable ST, KeyType key)
{ // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则返回
	// 该元素在表中的位置,否则返回0。算法9.1
	int i;
	ST.elem[0].key = key; // 哨兵
	for(i = ST.length; !EQ(ST.elem[i].key, key); --i)
		; // 从后往前找
	return i; // 找不到时,i为0
}

查找成功平均查找长度:

查找失败平均查找长度:

折半查找

折半查找:又称二分查找,它是一种效率很高的查找方法。折半查找要求顺序表中元素是有序的,即表中元素按关键字有序。

查找步骤:设elem[low..high]是当前的查找区间,首先确定该区间的中点位置mid= ⌊ (low+high)/2 ⌋ ;然后将待查的key值与elem[mid].key比较:

  • 若elem[mid].key=key,则查找成功并返回该元素的逻辑序号
  • 若elem[mid].key>key,则由表的有序性可知elem[mid..n].key均大于key,因此若表中存在关键字等于key的元素,则该元素必定在位置mid左子表elem[1..mid-1]中,故新的查找区间是左子表elem[1..mid-1];
  • 若elem[mid].key<key,则要查找的key必在位置mid的右子表elem[mid+1..n]中,即新的查找区间是右子表elem[mid+1..n]。
  • 下一次查找是针对新的子表重复上述的步骤。

代码实现:

int Search_Bin(SSTable ST, KeyType key)
{ 	// 在有序表ST中折半查找其关键字等于key的数据元素。若找到,则返回
	// 该元素在表中的位置,否则返回0。算法9.2
	int low, high, mid;
	low = 1; // 置区间初值
	high = ST.length;
	while(low <= high) {
		mid = (low + high) / 2;
	if EQ(key, ST.elem[mid].key) // 找到待查元素
		return mid;
	else if LT(key, ST.elem[mid].key)
		high = mid - 1; // 继续在前半区间进行查找
	else
		low = mid + 1; // 继续在后半区间进行查找
	}
	return 0; // 顺序表中不存在待查元素
}

折半查找判定树:折半查找过程构成一个判定树,把当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树。当折半查找表中元素个数n较大时,可以将整个判定树近似看成是一棵满二叉树,所有的叶子结点集中在同一层。不考虑外部结点,二叉树的高度h= ⌈ log2(n+1) ⌉ 。

查找成功平均查找长度:

查找失败平均查找长度:

索引顺序表查找

索引表:一般地,索引存储结构需要在数据表基础上建立一个关于索引项的索引表。索引表的结构为:(索引关键字,该关键字记录在数据表中的相对地址),其中索引关键字项有序排列。索引存储结构= 数据表+ 索引表。

查找步骤:

  • 先在索引表中查找,由于索引表是按关键字有序排列的,所以可以采用折半查找。
  • 当找到后通过其对应地址直接在数据表中找到其记录。

分块查找:数据表可以分成若干块,每一块中的元素是无序的,但块与块之间元素是有序的,即前一块中的最大关键字小于(或大于)后一块中的最小(或最大)关键字值。索引表中的一项对应数据表中的一块,索引项由关键字域和链域组成,关键字域存放相应块的最大关键字,链域存放指向本块第一个元素的指针,索引表按关键字值递增(或递减)顺序排列。

查找步骤:

  • 首先确定待查找的元素属于哪一块,即查找其所在的块。
  • 然后在块内查找相应的元素。
  • 由于索引表是递增有序的,可以对索引表进行折半查找,当索引表中元素个数(即分块的块数)较少时,也可以对索引表采用顺序查找方法。在进行块内查找时,由于块内元素无序,所以只能采用顺序查找方法。

查找成功平均查找长度:

平均查找长度 = 索引表中查找子表位置的平均查找长度 + 子表内查找元素位置的查找成功的平均查找长度

动态查找表

二叉排序树

二叉排序树(二叉搜索树或二叉查找树,BST):是一棵空树;或者是若它的左子树不空,则左子树上所有结点的值均小于根结点的值;若它的右子树不空,则右子树上所有结点的值均大于根结点的值;它的左、右子树也都分别是二叉排序树。(二叉排序树中没有相同关键字的结点,中序序列是有序序列)

查找算法:在二叉排序树T中查找关键字为k的结点,找到后返回该结点的指针,找不到返回NULL。

  • 若当前结点p的关键字等于k,则返回p。
  • 否则若k小于当前结点的关键字,则在左子树中查找。
  • 否则若k大于当前结点的关键字,则在右子树中查找。

代码实现:

//----- 数据元素类型的定义-----
typedef struct {
	KeyType key ; /* 关键字码*/
	otherinfo /* 其他域*/
} RecType ;
// ----- 二叉排序树的二叉链表存储表示------
typedef struct {
	RecType data;
	BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;


BiTree SearchBST(BiTree T, KeyType key)
{
	// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,
	// 若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。
	if(!T || EQ(key, T->data.key))
		return T; // 查找结束
	else if LT(key, T->data.key) // 在左子树中继续查找
		return SearchBST(T->lchild, key);
	else
		return SearchBST(T->rchild, key); // 在右子树中继续查找
}

插入算法:

  • 根据动态查找表的定义,“插入”操作在查找不成功时才进行;
  • 若二叉排序树为空树,则新插入的结点为新的根结点;
  • 否则,新插入的结点必为一个新的叶子结点,其插入位置由查找算法SearchBST()得到。

代码实现:

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

创建二叉排序树算法:由包含n个关键字的数组a建立相应的二叉排序树。依次扫描a数组的所有元素,调用InsertBST()将其插入到二叉排序树T中。

代码实现:

void CreateBST(BiTNode *&T, KeyType a[], int n)
{
	T = NULL; //初始时T为空树
	int i = 0;
	while(i < n) {
		InsertBST(T, a[i]); //将关键字a[i]插入到二叉排序树T中
		i++;
	}
}

删除算法:在二叉排序树T中删除关键字为k的结点后,仍需要保持二叉排序树的特性。先在二叉排序树T中查找关键字为k的结点p,用f指向其双亲结点。

  1. 若p结点没有左子树(含p为叶子结点的情况),则用p结点的右孩子替换它。
  2. 若p结点没有右子树,则用p结点的左孩子替换它。
  3. 若p结点既有左子树又有右子树,用其左子树中最大的结点替代它。通过p结点的左孩子q找到它的最右下结点q1,q1结点就是p结点左子树中最大的结点,将q1结点值替代p结点值,然后将q1结点删除。由于q1结点一定没有右孩子,可以采用2.的操作删除结点q1。

代码实现:

void Delete(BiTree &p)
{
	// 从二叉排序树中删除结点p,并重接它的左或右子树。算法9.8
	BiTree q, s;
	// p的右子树空则只需重接它的左子树(待删结点是叶子也走此分支)
	if(!p->rchild) {
		q = p;
		p = p->lchild;
		free(q);
	}else if(!p->lchild) { // p的左子树空,只需重接它的右子树
		q = p;
		p = p->rchild;
		free(q);
	}else { // p的左右子树均不空
		q = p;
		s = p->lchild;
		// 转左,然后向右到尽头(找待删结点的前驱)
		while(s->rchild) {
			q = s;
			s = s->rchild;
		}
		// s指向被删结点的"前驱"(将被删结点前驱的值取代被删结点的值)
		p->data = s->data;
		if(q != p)
			q->rchild = s->lchild; // 重接*q的右子树
		else
			q->lchild = s->lchild; // 重接*q的左子树
		free(s);
	}
}

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

平均查找长度:平均查找长度和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其平均查找长度为(n+1)/2(和顺序查找相同),这是最差的情况。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2n成正比。

平衡二叉树

平衡二叉树(AVL):是一棵空树;或者是二叉排序树中任何一个结点的左子树和右子树高度之差的绝对值不超过1;它的左、右子树也分别都是平衡二叉树。(若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1,即平衡因子取值为1、0或-1,则该二叉树称为平衡二叉树。)

平衡因子:二叉树中每个结点设置一个平衡因子bf(balancd factor)域。每个结点的平衡因子是该结点左子树的高度减去右子树的高度。

平衡化旋转:如果在一棵AVL树中插入一个新结点,造成了不平衡。必须调整树的结构,解决方法是调整(旋转),使之平衡化。平衡化旋转有两类:单旋转(LL旋转和RR旋转)和双旋转(LR旋转和RL旋转)。每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一个新结点后,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子。

LL型调整过程:

  • B结点带左子树α一起上升
  • A结点成为B的右孩子
  • 原来B结点的右子树β作为A的左子树

RR型调整过程:

  • B结点带右子树β一起上升
  • A结点成为B的左孩子
  • 原来B结点的左子树α作为A的右子树

LR型调整过程:

  • C结点穿过A、B结点上升
  • B结点成为C的左孩子,A结点成为C的右孩子
  • 原来C结点的左子树β 作为B的右子树;原来C结点的右子树γ 作为A的左子树

平均查找长度:含有n个结点的平衡二叉树的平均查找长度为O(log2n)。

B-树和B+树

B-树:B-树中所有结点的最大度称为B-树的阶,通常用m表示,从查找效率考虑,要求m≥3。

  • 一棵m阶B-树或者是一棵空树,或者是树中每个结点至多有m棵子树
  • 若根结点不是叶子结点,则至少有两棵子树
  • 除根结点外,所有内部结点至少有 ⌈ m/2 ⌉ 棵子树。
  • 所有的内部结点中包含:关键字、指向子树根结点的指针。
  • 所有叶子结点在同一层上并且不带信息(实际上这些结点不存在,指向这些结点的指针为空)。

B+树:在索引文件组织中,经常使用B-树的一些变形,其中B+树是一种应用广泛的B-树的变形。

  • 每个分支结点至多有m棵子树。
  • 根结点或者没有子树,或者至少有两棵子树。
  • 除根结点外,其他每个分支结点至少有 ⌈ m/2 ⌉ 棵子树。
  • 有n棵子树的结点有n个关键字。
  • 所有叶子结点包含全部关键字及指向相应记录的指针,而且叶子结点按关键字大小顺序链接(可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录)。
  • 所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引的索引块)中最大关键字及指向子结点的指针。

哈希表

哈希函数:理想的情况是希望不经过任何比较,一次存取便能得到所查记录,为此,需在记录的存储位置和它的关键字之间建立一个确定的对应关系f(key),由此,不需进行比较便可直接取得所查记录,我们称这个对应关系f(key)为哈希(Hash)函数 或者散列函数 。

哈希表:按哈希函数思想建立的表为哈希表(散列表)。

同义词:可能存在这样的问题, 对于两个关键字ki 和kj(i≠j),有ki≠kj(i≠j),但h(ki)=h(kj)。把这种现象叫做发生了冲突,称ki、kj为同义词。

设计一个散列表应包括:

  • 散列表的空间范围,即确定散列函数的值域;
  • 构造合适的散列函数,使得对于所有可能的元素(记录的关键字),函数值均在散列表的地址空间范围内,且出现冲突的可能尽量小;
  • 处理冲突的方法。即当冲突出现时如何解决。

哈希函数构造方法的目标:

  1. 使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上,所谓“均匀”(uniform)是指发生冲突的可能性尽可能最少。
  2. 同时使计算过程尽可能简单以达到尽可能高的时间效率。
  3. 根据关键字的结构和分布的不同,有多种构造哈希函数的方法。

哈希函数构造方法

直接定址法:以关键字key本身或关键字加上某个数值常量c作为哈希地址的方法。即h(key)=key+c。

特性:

  • 这种哈希函数计算简单,并且不可能有冲突发生。
  • 当关键字的分布基本连续时,可用直接定址法的哈希函数;否则,若关键字分布不连续将造成内存单元的大量浪费。

除留余数法:用关键字key除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(key)为:h(key)=key mod p (mod为求余运算,p≤m),p最好是质数(素数)。

数字分析法:提取关键字中取值较均匀的数字位作为哈希地址的方法。

特性:适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。

处理冲突的方法

发生冲突的三个因素:

  • 与装填因子有关。所谓装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值,即α=n/m。α越小,冲突的可能性就越小; 但α越小,存储空间的利用率就越低。
  • 与所采用的哈希函数有关。
  • 与解决冲突的方法有关。处理冲突就是为发生冲突的关键字的记录找到另一个“空”的哈希地址。

开放定址法:当冲突发生时,形成某个探测序列;按此序列逐个探测散列表中的其他地址,直到找到给定的关键字或一个空地址(开放的地址)为止,将发生冲突的记录放到该地址中。

散列地址的计算公式是:Hi(key)=(H(key)+di) MOD m,i=1, 2, …, k(k<=m-1)

  • H(key):哈希函数;
  • m:散列表长度;
  • di:第i次探测时的增量序列;
  • Hi(key) :经第i次探测后得到的散列地址。

线性探测法:从发生冲突的地址(设为d)开始,依次循环探测d的下一个地址(当到达下标为m-1的哈希表表尾时,下一个探测的地址是表首地址0),直到找到一个空闲单元为止。Hi(key)=(H(key)+di) MOD m, 其中,增量序列为:di=1, 2, 3, …, m-1。设d0=H(key),则Hi(key)=di=(di-1+1) mod m (1≤i≤m-1)

二次聚集现象:哈希函数值不相同的多个记录争夺同一个后继哈希地址。

优点 只要散列表未满,总能找到一个不冲突的散列地址;
缺点 每个产生冲突的记录被散列到离冲突最近的空地址上,从而又增加了更多的冲突机会(这种现象称为冲突的“二次聚集”)。

二次探测再散列:发生冲突时前后查找空位置。Hi(key)=(H(key)+di) MOD m, 其中,增量序列为:di=1²,-1²,2²,-2²,3²,……,±k² (k ≤ ⌊m/2⌋)。设d0=H(key), Hi(key)=di=(d0±i2) mod m (1≤i≤m-1)

优点二次探测再散列法可以避免出现堆积问题。
缺点不能探测到哈希表上的所有单元,但至少能探测到一半单元。

链地址法:将所有关键字为同义词(哈希地址相同)的记录存储在一个单链表中,并用一维数组存放链表的头指针。

特性:

  • 在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。
  • 由于单链表中可插入任意多个结点,所以此时装填因子α根据同义词的多少既可以设定为大于1,也可以设定为小于或等于1,通常取α=1。
平均查找长度ASL
解决冲突的方法成功的查找不成功的查找
线性探测法½(1+1/1 -α)½(1+1/(1 -α)2)
平方探测法-1/α loge(1 – α) 1/1 – α
链地址法 1+α/2 α + e ≈ α

最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。