（八）查找

2017-06-20

查找

　静态查找表 查找只进行查询和检索操作
　动态查找表 查找除了上述两种操作还包括插入和删除

　平均查找长度
　　ASL=∑（i=1.n）PiCi
　　Pi为查找表第i个记录的概率
　　Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数

　顺序查找 ASL=（n+1）/2
　折半查找
　

　int Search_Bin(SSTable ST,KeyType key){
　//在有序表ST中折半查找
　　　int low=0,high=ST.length-1;
　　　while(low<=high){
　　　　int mid=(low+high)/2;
　　　　if(ST.elem[mid]==key) return mid;
　　　　else if(key<ST.elem[mid]) high=mid-1;
　　　　else low=mid+1;
　　　}
　　　return 0;
　}

　　用二叉判定树表示，ASL=（∑每层结点数层数）/N 假设概率相等
　　*注意：必须为有序表**

　二叉排序树
　　空树或满足如下性质的二叉树：
　　①若它的左子树非空，则左子树上左右节点的值均小于根结点的值
　　②若它的右子树非空，则右子树上所有节点的值均大于根结点的值
　　③它的左右子树也分别是二叉排序树

　　建立、插入、删除的时间复杂度O（nlog2 n）

　　删除操作：
　　①p是叶子，则直接删除p
　　②p只有一个孩子child，只需将child和p的双亲直接连接就可删去p
　　③p有两个孩子，则先将p结点的中序后继结点的数据接到p，删除中序后继结点

代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW_ -2

typedef int Status;
typedef int ElemType;
typedef int KeyType;

typedef struct{
	ElemType *elem;
	int length;
}SSTable;

int Search_Seq(SSTable ST,KeyType key){
	//顺序表ST中查找关键字等于key的数据元素
	ST.elem[0] = key;
	int i;
	for (i = ST.length - 1; ST.elem[i] != key&&i >= 0; --i);
	return i + 1;  //找不到时为0
}

int Search_Bin(SSTable ST,KeyType key){
	//在有序表ST中折半查找
	int low = 0, high = ST.length - 1;
	while (low <= high){
		int mid = (low + high) / 2;
		if (ST.elem[mid] == key) return mid;
		else if (key < ST.elem[mid]) high = mid - 1;
		else low = mid + 1;
	}
	return 0;
}