data structure

1. 顺序查找

顺序查找又称线性查找,主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。

1.1 一般线性表的顺序查找

从线性表的一端开始,逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件,则查找成功,返回该元素在线性表中的位置;若已经查找到表的另一端,但没有查找到符合条件的元素,则返回查找失败的信息。

伪代码如下,主要说明其中引入的 “哨兵” 的作用。

struct SSTable {  // 查找表的数据结构 
	int *elem;    // 元素存储空间基址,建表时按实际长度分配,0 号单位留空
	int TableLen; // 表的长度 
};

int Search_Seq(SSTable ST, int key) {
	// 在顺序表 ST 中顺序查找关键字为 key 的元素。 
	ST.elem[0] = key;   // "哨兵" 
	for(int i = ST.TableLen; ST.elem[i] != key; --i);  
	return i;  // 若表中不存在关键字为 key 的元素,将查找到 i 为 0 时退出 for 循环 
} 

在上述算法中,将 ST.elem[0] 称为 “哨兵”。引入它的目的是使得 Search_Seq 内的循环不必判断数组是否会越界,因为满足 i==0 时,循环一定会跳出。需要说明的是,在程序中引入 “哨兵” 并不是这个算法独有的,引入 “哨兵” 可以避免很多不必要的判断语句,从而提高程序效率。

对于有 n 歌元素的表,给定值 key 与表中第 i 个元素的关键字相等,即定位第 i 个元素时,需进行 n-i+1 次关键字的比较,即 Ci=n-i+1 。查找成功时,顺序查找的平均长度为

ASL成功=ΣPi(n-i+1)

当每个元素的查找概率相等,即 Pi=1/n 时,有

ASL成功=ΣPi(n-i+1)=(n+1)/2

查找不成功时,与表中各关键字的比较次数显然是 n+1 次,从而顺序查找不成功的平均查找长度为

ASL不成功=n+1

通常,查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率,则应先对记录的查找概率进行排序,使表中记录按查找概率由小至大排列。

综上所述,顺序查找的缺点是当 n 较大时,平均查找长度较大,效率低;优点是对数据元素的存储没有要求,顺序存储或链式存储皆可。对表中记录的有序性也没有要求,无论记录是否按关键码有序,均可应用。同时还需注意,对线性的链表只能进行顺序查找。

1.2 有序表的顺序查找

若在查找之前就已经知道表是关键字有序的,则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息,从而降低顺序查找失败的平均查找长度。

假设表 L 是按关键字从小到大排列的,查找的顺序是从前往后,待查找元素的关键字为 key,当查找到第 i 个元素时,发现第 i 个元素对应的关键字小于 key,但第 i+1 个元素对应的关键字大于 key,这时就可返回查找失败的信息,因为第 i 个元素之后的元素的关键字均大于 key,所以表中不存在关键字为 key 的元素。

在有序表的顺序查找中,查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时,查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点,实际上是不存在的,所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为

ASL不成功=Σqj(lj-1)=(1+2+...+n+n)/(n+1)= n/2+n/(n+1)

式中,qj 是到达第 j 个失败结点的概率,在相等查找概率的情形下,它为 1/(n+1) ;lj 是第 j 个失败结点所在的层数。当 n=6 时,ASL不成功=6/2+6/7=3.86 ,比一般的顺序查找算法好一些。

注意:有序表的顺序查找和后面的折半查找的思想是不一样的,且有序表的顺序查找中的线性表可以是链式存储结构。

2. 折半查找

折半查找又称二分查找,它仅适用于有序的顺序表。基本思路是:首先将给定值 key 与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素之外的前半部分或后半部分(例如,在查找表升序排列时,若给定值 key 大于中间元素的关键字,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续同样的查找,如此重复,直到找到为止,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。算法如下:

int Binary_Search(SeqList L, int key) {
	// 在有序表 L 中查找关键字 key 的元素,若存在则返回其位置,不存在则返回 -1
	int low=0, high = L.TableLen-1, mid;
	while(low <= high) {
		mid = (low + high) /2;   // 取中间位置
		if(L.elem[mid] == key) 
			return mid;          // 查找成功则返回所在位置
		else if(L.elem[mid] > key)
			high = mid -1;      // 从前半部分继续查找
		else 
			low = mid + 1;    // 从后半部分继续查找 
	} 
	return -1; 
}

折半查找的过程可用判定树(二叉树)来描述 。树中每个非叶子结点表示一个记录,结点中的值为该记录的关键字;树中的叶子结点都是方形的,它表示查找不成功的情况。从判定树可用看出,查找成功时的查找长度为从根结点到目的结点的路径上的结点数,而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数;每个结点值均大于其左子结点值,且均小于其右子结点值。若有序序列有 n 个元素,则对应的判定树有 n 个非叶结点和 n+1 个叶结点。

由上述分析可知,用折半查找法查找给定值的比较次数最多不超过树的高度。在等概率查找时,查找成功的平均查找长度为

ASL=1/nΣli=1/n(1×1+2×2+...+h×2^(h-1))=(n+1)/n·log2(n+1)-1≈log2(n+1)-1

式中,h 是树的高度,并且元素个数为 n 时树高 h=log2(n+1)向上取整 。所以,折半查找的时间复杂度为 O(log2n) ,平均情况下比顺序查找的效率高。

查找不成功的概率为所有叶子的路径长度的求和平均。

因为折半查找需要方便地定位查找区域,所以适合折半查找的存储结构必须具有随机存取的特性。因此,该查找法仅适合于线性表的顺序存储结构,不适合于链式存储结构,且要求要素按关键字有序排列。

3. 方块查找

分块查找又称索引顺序查找,它吸取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找。

分块查找的基本思想:将查找表分为若干子块,块内的元素可以无序,但块之间是有序的,即第一个块中的最大关键字小于第二个块中的所有记录的关键字,第二个块中的最大关键字小于第三个块中的所有记录的关键字,以此类推。再建立一个索引表,索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址,索引表按关键字有序排列。

分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块,可以顺序查找或折半查找索引表;第二步是在块内顺序查找。块间查找从本快的开始地址到下一个块的开始地址之前。

分块查找的平均查找长度为所有查找和块内查找的平均长度之和。设索引查找和块内查找的平均长度分别为 Li,Ls,则分块查找的平均查找长度为

ASL=Li+Ls

将长度为 n 的查找表均匀地分布为 b 块,每块有 s 个记录,在等概率情况下,若在块内和索引表中均采用顺序查找,则平均查找长度为

ASL=Li+Ls=(b+1)/2+(s+1)/2=(s^2+2s+n)/(2s)

此时,若 s=sqrt(n) ,则平均查找长度取最小值 sqrt(n)+1 ;若对索引表采用折半查找时,则平均查找长度为

ASL=Li+Ls=log2(b+1)向上取整+(s+1)/2