欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序查找和二分查找表

程序员文章站 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));
	}
	
}

上一篇: 二分答案模板

下一篇: 顺序查找