常见查找

简单查找:

 

     顺序查找:

     从线性表的一端开始,依次将每个记录的关键字与给定值进行比较,若某个记录的关键字等于给定值,表示查找成功,返回记录序号;若将线性表中所有记录都比较完,扔未找到关键字与给定值相等的记录,则表示查找失败,返回 一个失败值.

public class QuerySearch {
	public static int[] Data = { 65, 21, 92, 11, 55, 42, 89, 8, 5, 9, 81, 33, 28, 89, 90, 28, 122, 76, 30, 7 };

	public static int COUNT = 1;

	public static void main(String args[]) {
		int key = 21;
		if (Linear_Search(key)) {
			System.out.println();
			System.out.println("Search Time = " + COUNT);
		} else {
			System.out.println();
			System.out.println("No Found");
		}
	}

	public static boolean Linear_Search(int key) {
		int i;
		for (i = 0; i < 20; i++) {
			System.out.print("[" + (int) Data[i] + "]");
			if ((int) key == (int) Data[i])
				return true;
			COUNT++;
		}
		return false;
	}
}

 

 

     折半查找:

 

     又称为二分查找.这种查找方法要求查找表的数据是线性结构保存,并且还要求查找表中的数据是按关键字的由小到大有序排列.

public class BinarySearch {

	public static void main(String[] args) {
		int[] is = { 1, 4, 7, 12, 23, 34, 45, 78 };
		int index = binarySearch(is, 1);
		if (index < 0) {
			System.out.println("没有当前值存在");
			return;
		}
		System.out.println(index);
	}

	public static int binarySearch(int[] is, int key) {
		int low = 0, high = 0, mid = 0;
		high = is.length;
		while (high >= low) {
			mid = (high + low) / 2;
			if (is[mid] == key) {
				return mid;
			} else if (is[mid] > key) {
				high = mid - 1;
			} else if (is[mid] < key) {
				low = mid + 1;
			}
		}
		return -1;
	}

}

 

 

 

 

     二叉排序树:

 

     二叉排序树或者是一棵空树,或者是一棵具有以下性质的二叉树:

     (1)若它有左子树,则左子树上的所有结点都小于根结点数据.

     (2)若它有右子树,则右子树上的所有结点都大于根结点数据.

     (3)左右子树各是一棵二叉排序树.

 

 二叉排序树删除节点(有左右子树)

 

删除无右子树节点

 删除无左右子树

 

 

     索引查找:

     对大量数据进行查找时块,索引要多占用空间,更新时不仅要更新主表,也要更新索引表.

 

     1.在索引表中进行查找.

     查找过程如下:

     (1)首先根据给定的关键字key,按定义的函数计算出索引值index1,在索引表上查找出索引值等于index1的索引项,以确定对应子表在主表中的开始位置和长度.

     (2)接着根据从索引表中获取的开始序号start,在主表指定的位置(即子表的开始处)顺序查找关键字key.

 

     2.向主表中插入数据.

     在线性表的索引存储结构上进行插入删除运算的算法,与查找算法类似.其具体过程如下:

     (1)根据待插入的元素的值查找索引表,确定出对应的子表.

     (2)接着,根据待插入元素的关键字,在该子表中做插入元素的操作.

     (2)插入完成后,修改索引表中相应子表的长度.

 

 

     哈希表:

 

     哈希表的基本思想是:以线性表中每个元素的关键字key为自变量,通过一定的函数关系h(key)计算出函数的值,把这个值作为数组的下标,将元素存入对应的数组元素中. 

     函数h(key)称为哈希函数,函数的值称为哈希地址.

     缺点1:可能浪费空间

     缺点2:可能发生冲突

 

     常用的构造哈希函数的方法:

    >直接定址法(关键字本身或者关键字加上某一个常数直接作为地址,一般要求关键字连续不重复)

    >除法取余法(一般除数选择奇数或者素数)

    >数字分析法(对关键字的某些部分进行分析)

    >平方取中法(平方取中)

    >折叠法(用关键字拆分成长度相等的几段再相加)

    可以根据数据特点自己构造适合的哈希函数

 

     处理冲突的方法:

    >开放地址法.

 

    >链接法.