简单查找:
?
? ? ?顺序查找:
?? ? 从线性表的一端开始,依次将每个记录的关键字与给定值进行比较,若某个记录的关键字等于给定值,表示查找成功,返回记录序号;若将线性表中所有记录都比较完,扔未找到关键字与给定值相等的记录,则表示查找失败,返回 一个失败值.
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:可能发生冲突
?
? ? ?常用的构造哈希函数的方法:
? ? >直接定址法(关键字本身或者关键字加上某一个常数直接作为地址,一般要求关键字连续不重复)
? ? >除法取余法(一般除数选择奇数或者素数)
? ? >数字分析法(对关键字的某些部分进行分析)
? ? >平方取中法(平方取中)
? ? >折叠法(用关键字拆分成长度相等的几段再相加)
? ? 可以根据数据特点自己构造适合的哈希函数
?
? ? ?处理冲突的方法:
? ? >开放地址法.
?
? ? >链接法.
?
?
?
?
?
?
?
?
?
原文：http://bbllmyd.iteye.com/blog/2308760