顺序查找和二分查找表
程序员文章站
2024-03-17 17:14:46
...
顺序查找表
/**
* 基于链表的顺序查询的符号表,支持put/get/delete操作
*
* @author XY
* @param <Key>
* @param <Value>
*/
public class LinkedListST<Key, Value> {
class Node {
private Key key;
private Value value;
private Node next;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
}
/******* 内部类结束 *********/
private Node root;
private StringBuffer sb;
public void put(Key key, Value value) {// 插入
root = put(root, key, value);
}
private Node put(Node node, Key key, Value value) {
if (node == null)
return new Node(key, value);
if (node.key.equals(key))
node.value = value;
else
node.next = put(node.next, key, value);
return node;
}
public Value get(Key key) {// 查找
return get(root, key);
}
private Value get(Node node, Key key) {
if (node == null)
return null;
if (node.key.equals(key))
return node.value;
return get(node.next, key);
}
public void delete(Key key) {// 删除
root = delete(root, key);
}
private Node delete(Node node, Key key) {
if (node == null)
return null;
if (node.key.equals(key)) {
return node.next;
} else
node.next = delete(node.next, key);
return node;
}
public void show() {
sb = new StringBuffer();
show(root);
System.out.println(sb);
}
private void show(Node node) {
if (node == null)
return;
sb.append(node.key + ":" + node.value + " ");
show(node.next);
}
public static void main(String[] args) {
LinkedListST<Integer, String> st = new LinkedListST<Integer, String>();
st.put(3, "lm");
st.put(4, "sgt");
st.put(2, "zx");
st.put(1, "sq");
st.show();
System.out.println(st.get(2));
st.delete(2);
st.show();
st.put(2, "xzm");
st.show();
}
}
二分查找表
package second;
/**
* 基于有序数组的二分查找的符号表设计
* @author XY
*
*/
@SuppressWarnings("unchecked")
public class BinaryST<Key extends Comparable<Key>,Value> {
private Key[] keys;
private Value[] values;
private int N;
private final int default_size=10;
private int size;
public BinaryST(){
this.size=default_size;
N=0;
keys=(Key[])new Comparable[this.size];
values=(Value[])new Object[this.size];
}
public void put(Key key,Value value){
if(N<size){
int k=rank(key);
if(k<N && keys[k].compareTo(key)==0) {values[k]=value;}
else{
for (int i = N; i >k; i--) {
keys[i]=keys[i-1];
values[i]=values[i-1];
}
keys[k]=key;
values[k]=value;
}
N++;
}
}
public Value get(Key key){
if(rank(key)<N && keys[rank(key)].compareTo(key)==0)
return values[rank(key)];
return null;
}
public int rank(Key key){
int lo=0,hi=N-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(keys[mid].compareTo(key)<0) lo=mid+1;
else if(keys[mid].compareTo(key)>0) hi=mid-1;
else return mid;
}
return lo;
}
public int size(){return N;}
public int size(Key key1,Key key2){
if(key1.compareTo(key2)==0) return 0;
else if(key1.compareTo(key2)>0){
Key temp=key1;key1=key2;key2=temp;
}
if(rank(key2)==N) return rank(key2)-rank(key1);
return rank(key2)-rank(key1)+1;
}
public Key ceiling(Key key){
int temp=rank(key);
return temp<N?keys[rank(key)]:null;
}
public Key floor(Key key){
int temp=rank(key);
Key res= get(key)==null?keys[rank(key)-1]:key;
return res;
}
public Key[] keys(){
Key[] temp=(Key[])new Comparable[N-1];
for (int i = 0; i < temp.length; i++) {
temp[i]=keys[i];
}
return temp;
}
public void show(){
StringBuffer sb=new StringBuffer();
for (int i = 0; i < N; i++) {
sb.append(keys[i]+":"+values[i]+" ");
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
BinaryST<Integer, String> st=new BinaryST<Integer, String>();
st.put(2, "sgt");
st.put(8, "lm");
st.put(4, "cn");
st.put(5, "rn");
st.show();
System.out.println(st.floor(4));
}
}