顺序查找和二分查找表

顺序查找表

/**
 * 基于链表的顺序查询的符号表，支持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));
	}
	
}