数据结构复习查找

查找表是由同一类型的数据元素（或记录）组成的集合。

查找表的分类：

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

2.动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除某个已存在的数据元素

关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之为“主关键字”。若此关键字能识别若干记录，则称之为“次关键字”。

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。

若查找表中存在这样的一个记录，则”查找成功“，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置。否则”查找不成功“，查找结果：给出“空记录”或“空指针”。

查找的方法取决于查找表的结构。由于查找表的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表的元素之间人为地附加某种确定的关系。也就是说，用另外一种结构来表示查找表。

查找方法评价：查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度ASL（Average Search Length，为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值）

静态查找表：

1.顺序表的查找：

查找过程：从表的一端开始，逐个进行记录的关键字与给定值的比较。

例如，有n个数，则构造一个长度为n+1的数组arr，其中arr[0]为监视哨，存放要查找的元素，剩下的1~n位存放n个数。从arr[n]开始向arr[1]查找，则比较次数：

若查找第n个元素，则比较1次（第一次就找到）；

若查找第n-1个元素，则比较2次（第一次比较之后，又比较了一次）；

若查找第i个元素，则比较(n+1-i)次；

查找失败：比较了n+1次。

int Search_Seq(int &a[], int key){
	a[0] = key;
	for(int i = n; i >= 1; --i)
		if(a[i] == key)
            return i;
    return 0;
}

对于顺序表，等概率情况下：=

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

2.有序表的查找：

顺序表的查找算法简单，但是ASL较大，不适用于表长较大的查找表。

若以有序表表示静态查找表，则查找过程可以“折半”进行。

折半查找：

查找过程：每次将待查记录所在区间减小一半。

适用条件：采用顺序存储结构的有序表。

折半查找算法的实现：

若k == mid，查找成功；

若k < mid，high = mid - 1；

若k > mid，low = mid + 1；

重复上述操作，直至条件low <= high不再满足为止。

int Search_Bin(int &a[], int k){
	int low = 1, high = n;
	while(low <= high){
		int mid = (low + high) / 2;
		if(k == a[mid]) return mid;
		else if(k > a[mid]) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

性能分析：

判定树：描述查找过程的二叉树。

由此可见，

折半查找效率比顺序查找高。
折半查找只适用于有序表，并且以顺序存储结构存储。

顺序表和有序表的比较：

	顺序表	有序表
表的特性	无序	有序
存储结构	顺序或链式	顺序
插删操作	易于进行	需要移动元素
ASL	大	小

3.索引顺序表（=索引+顺序表）

在建立顺序表的同时，建立一个索引项，包括：关键字项和指针项。索引表按关键字有序，表则为分块有序。

顺序表：

15	95	42	37	65	16

索引表：

95 0	65 3	85 6

（索引表中包含：第一块：0-2，最大关键字是95，起始是0；…）

索引顺序查找，又称分块查找。

查找过程：将表分为几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。

适用条件：分块有序表

算法实现：用数组存放待查记录，每个数据元素至少含有关键字域；建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。

查找方法比较：

	顺序	折半	分块
ASL	大	小	两者之间
表结构	无序或有序	有序	分块有序表
存储结构	顺序或链式	顺序	顺序或链式

从查找性能来看，最好情况能达到O(logn)，此时要求表有序；

从插入和删除的性能来看，最好情况能达到O(1)，此时要求存储结构是链表。

动态查找表：

特点：表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值的记录，则查找成功，否则插入关键字等于key的记录。

数据结构复习 查找