【数据结构】八、查找

一、基本概念

静态查找：只查找，不改变集合内数据元素

动态查找：有则输出元素，无则添加元素

二、静态查找表

2.1顺序查找

在线性表、链表、树中依次查找

2.2折半查找（二分查找）

在有序的线性表中，每次都与中间位置元素进行比较，根据大小向左或向右缩小查找区域

#include<stdio.h>
#include<stdlib.h>

//void search(int l[], int low, int high, int value)  //二分查找递归版
//{
//	if (high < low)
//		return;
//	int mid = (low + high) / 2;
//	if (l[mid] == value)
//	{
//		printf("第%d个", mid+1);
//		return;
//	}
//	if (l[mid] < value)
//		search(l, mid, high, value);
//	else
//		search(l, low, mid, value);
//}

int search2(int* l, int n, int target)   //二分查找非递归版
{
	int low = 0, high = n - 1, mid;
	while (low <= high)   //相等时还可以比较一次
	{
		mid = (low + high) / 2;
		if (target == l[mid])
			return mid;
		else if (target < l[mid])
			high = mid - 1;
		else
			low = mid + 1;
	}
	return -1;    //不能return0
}

int main() {
	int l[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//search(l, 0, 9, 9);
	printf("%d", search2(l, 10, 3));
}

折半查找的ASL

第一趟能比较一个元素，第二趟能比较两个元素，第三趟能比较三个元素……

总共查找次数为1*1 + 2*2 + 3*4 + 4*8+……当比较过的总元素等于表中关键字个数位置

ASL=总次数/总个数

具有12个关键字的有序表,折半查找的平均查找长度( )

答案：（1*1 + 2*2 + 3*4 + 4*5）/ 12 = 3.1 （最好写成小数形式）

在有序线性表a[20]上进行折半查找，则平均查找长度为（）

答案：3.7

（多选题）使用折半查找算法时，要求被查文件（）

Ａ．采用链式存贮结构Ｂ．记录的长度≤12 Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序

答案：CD

折半查找失败的平均查找长度

构建二分查找树

第一次找到(1+12)/2=6，6就为第一个节点。如果向左，(1+5)/2=3为左孩子。如果向右，(7+12)/2=9为右孩子，如此把节点都放入树中。

补上所有空节点(图中绿色方块)，这就是查找失败的位置。

失败的平均次数=求和(根节点到失败节点经过的边数)/失败节点个数

具有12 个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的平均查找长度依次为( )

答案： 37/12,49/13

2.3分块查找

让数据分成若干子表，子表内不必有序，但要求每个子表中的数据元素值都比后一块中的数值小。然后将各子表中的最大（或最小）关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

特点：块间有序，块内无序

查找：块间折半，块内线性

三、二叉排序树

定义：左子树的所有结点均小于根的值，右子树的所有结点均大于根的值；它的左右子树也分别为二叉排序树。

分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是（）

A.100,80, 90, 60, 120,110,130

B.100,120,110,130,80, 60, 90

C.100,60, 80, 90, 120,110,130

D.100,80, 60, 90, 120,130,110

答案：C 按照左小右大进行插入

查找：与节点比大小，往左右走；当查不到时，新建节点

node* newnode(int v) {    //新建节点，返回地址
	node* newnode = (node*)malloc(sizeof(node));
	if (!newnode) return NULL;
	newnode->data = v;
	newnode->lchild = NULL;
	newnode->rchild = NULL;
	return newnode;
}

void insert(pnode& root, int value) {  //递归寻找，定位到值该在的位置
	if (root == NULL) {
		root = newnode(value);
		return;
	}
	if (root->data > value)
		insert(root->lchild, value);
	else
		insert(root->rchild, value);
}

删除节点：

节点是叶子：直接删

节点一个孩子：删掉节点，把孩子接上去

节点两个孩子：用左子树最大值或右子树最小值覆盖该节点，然后删去左子树最大值或右子树最小值

四、平衡二叉树

每个节点有一个平衡因子，它等于左子树高度 - 右子树高度

任一结点的平衡因子只能取：-1、0 或 1的树为平衡二叉树

4.1平衡旋转

插入节点导致不平衡，要进行旋转

无论哪种情况，都从最下层不平衡节点开始处理

LL型：从不平衡点开始，沿着失衡路径的下一个节点要变为新的根节点，他的孩子和父亲变为左右节点

RR型：同LL

LR型：新节点先不插入。不平衡节点的下二层节点要变为新的根，他的上面两代节点做他的左右孩子，其他节点照抄，再插入新节点

RL型：同LR

五、哈希表

哈希表是散列存储结构，由关键码的值决定数据的存储地址。查找效率O(1)，与元素个数无关

冲突：由于hash函数自身存在的问题，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。

装填（载）因子：a=n/m ，其中n 为关键字个数，m为表长。装填（载）因子是表示Hsah表中元素的填满的程度。若:装载因子越大，填满的元素越多，好处是,空间利用率高了，但:冲突的机会加大了。反之，装载因子越小，填满的元素越少，冲突的机会减小了，但空间浪费多了。冲突的机会越大，则查找的成本越高，反之查找时间越小。