静态查找表

Share

静态查找表：仅做查询和检索操作的查找表

假设静态查找结构为

1
2
3
4
5
6
typedef struct {
	elemType *elem;
	//数据元素存储空间基址，建表时按数据长度分配，0号单元留空
	int length;
	//表的长度
}SSTable;

数据元素的定义为

1
2
3
4
typedef struct {
	keyType key;	//关键字域
	...		//其他属性域
}elemType, tElemType;

顺序查找表

以顺序表或者是线性链表表示静态查找表

1
2
3
4
5
6
7
8
9
10
11
12
13
//顺序表的普通查找
int location(SqList L, elemType &e, Status(*compare)(elemType, elemType)) {
	i = 1;
	p = L.elem;
	while (i <= L.length && !(*compare)(*p++, e)) {
		i++;
	}
	if (i <= L.length) {
		return i;
	}else {
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
//添加哨兵的顺序表查找
int searchSeq(SSTable ST, keyType kval) {
	//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
	//设置哨兵
	ST.elem[0].key = kval;
	//从后往前找
	for (i = ST.length; ST.elem[i].key != kval; i--);
	//找不到时i为0
	return i;
}

分析顺序查找的时间性能

定义：查找算法的平均查找长度(average search length)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值

其中，n为表长，Pi为查找表中第i个记录的概率；Ci为找到该记录时，曾和给定值比较过的关键字的个数

对于顺序表来说，Ci = n -i + 1

在等概率查找的情况下，Pi = 1/n

在不等概率查找的情况下，ASLss取极小值。

若查找概率无法事先确定，则查找过程采取的改进方法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上

所以可以推出：

有序查找表

上诉顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较长的查找表

若以有序表表示静态查找表，查找过程可以基于折半进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int searchBin(SSTable ST, keyType kval) {
	//置区间初值
	low = 1;
	high = ST.length;
	while (low <= high) {
		mid = (low + high) / 2;
		if (kval == ST.elem[mid].key) {
			//找到待查元素
			return mid;
		}else if (kval < ST.elem[mid].key) {
			//继续在前半区间进行查找
			high = mid - 1;
		} else {
			//继续在后半区间进行查找
			low = mid + 1;
		}
	}
	//若顺序表中不存在待查找元素，则返回0
	return 0;
}

分析折半查找的时间性能

ASL=N+1/N log2(N+1)-1

在n趋于无穷大时,折半查找的ASL=((n+1)log2(n+1))/n - 1,当n大于50时,ASL约等于log2(n+1)-1

索引顺序表

在建立顺序表的同时，建立一个索引

索引顺序表 = 索引 + 顺序表

索引顺序表的查找过程：

  • 有索引确定记录所在区间
  • 在顺序表的某个空间内进行查找
  • 可见，索引顺序表查找的过程也是一个缩小区间的过程

注意：索引可以根据查找表的特点来构造

索引顺序表的平均查找长度 = 查找索引的平均查找长度 + 查找顺序表的平均查找长度

几种查找表的特性