Java算法-查找(符号表)

符号表

定义

定义：符号表是一种存储键值对的数据结构，支持两种操作：插入(put)，将一组新的键值对存入表中;查找(get),根据给定的键值的到对应的值。

一种有序的泛型符号表的API实现的对字符表的操作

字符表的实现

无序链表实现无序字符表

  
public class SequentialSearchST<Key, Value> {
    private int n;           // number of key-value pairs
    private Node first;      // the linked list of key-value pairs
    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;
        public Node(Key key, Value val, Node next)  {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }
    public SequentialSearchST() {}
    public int size() {
        return n;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null"); 
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key))
                return x.val;
        }
        return null;
    }
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null"); 
        if (val == null) {
            delete(key);
            return;
        }
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        }
        first = new Node(key, val, first);
        n++;
    }
    /**
     * Removes the specified key and its associated value from this symbol table     
     * (if the key is in this symbol table).    
     *
     * @param  key the key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null"); 
        first = delete(first, key);
    }
    // delete key in linked list beginning at Node x
    // warning: function call stack too large if table is large
    private Node delete(Node x, Key key) {
        if (x == null) return null;
        if (key.equals(x.key)) {
            n--;
            return x.next;
        }
        x.next = delete(x.next, key);
        return x;
    }
    /**
     * Returns all keys in the symbol table as an {@code Iterable}.
     * To iterate over all of the keys in the symbol table named {@code st},
     * use the foreach notation: {@code for (Key key : st.keys())}.
     *
     * @return all keys in the symbol table
     */
    public Iterable<Key> keys()  {
        Queue<Key> queue = new Queue<Key>();
        for (Node x = first; x != null; x = x.next)
            queue.enqueue(x.key);
        return queue;
    }

基于链表的实现及顺序查找是非常低效的
向一个空表中插入N个不同的键需要~N*N/2次比较

基于有序数组的二分查找实现有序字符表

public class BinarySearchST<Key extends Comparable<Key>,Value> {
	private Key[] keys;
	private Value[] vals;
	private int N=0;
	//构造方法，初始化
	public BinarySearchST(int capacity){
		keys=(Key[]) new Comparable[capacity];
		vals=(Value[]) new Object[capacity];
	}
	public int size(){
		return N;
	}
	public boolean isEmpty(){
		return N==0;
	}
	public boolean contains(Key key){
		if(key==null){
			throw new IllegalArgumentException("argument to contains() is null");
		}
		return get(key)!=null;
	}
	//二分查找
	//迭代法
	private int rank(Key key){
		int lo=0;
		int hi=N-1;
		while(lo<=hi){
			int mid=lo+(hi-lo)/2;
			int cmp=keys[mid].compareTo(key);
			if(cmp>0){
				hi=mid-1;
			}else if(cmp<0){
				lo=mid+1;
			}else{
				return mid;
			}
		}
		return lo;
	}	
/*	递归法实现二分查找
	public int rank(Key key,int lo,int hi){
		  if(hi<lo){
			  return lo;
		  }
		  int mid=lo+(hi-lo)/2;
		  int cmd=keys[mid].compareTo(key);
		  if(cmd>0){
			  return rank(key,lo,mid-1);
		  }else(cmd<0){
			  return rank(key,mid+1,hi);
		  }else{
			  return mid;
		  }
	  }*/
	public Value get(Key key){
		if(key==null){
			throw new IllegalArgumentException("argument to get() is null");
		}
		if(isEmpty()){
			return null;
		}
		int i=rank(key);
		if(i<N && keys[i].compareTo(key)==0){
			return vals[i];
		}else{
			return null;
		}	
	}	
	public void put(Key key,Value val){
		if(key==null){
			throw new IllegalArgumentException("argument to put() is null");
		}
		if(val==null){
			delete(key);
			return;
		}
		int i=rank(key);
		if(i<N && keys[i].compareTo(key)==0){
			vals[i]=val;
			return;
		}
		for(int j=N;j>i;j--){
			keys[j]=keys[j-1];
			vals[j]=vals[j-1];
		}
		keys[i]=key;
		vals[i]=val;
		N++;
	}
	public void delete(Key key){
		if(key==null){
			throw new IllegalArgumentException("argument to delete() is null");
		}
		if(isEmpty()){
			return;
		}
		int i=rank(key);
		if(i==N || keys[i].compareTo(key)!=0){
			return;
		}
		for(int j=i;j<N-1;j++){
			keys[j]=keys[j+1];
			vals[j]=vals[j+1];
		}
		N--;
		keys[N]=null;
		vals[N]=null;		
	}
	public Key min(){
		return keys[0];
	}
	public Key max(){
		return keys[N-1];
	}
	public Key select(int k){
		return keys[k];
	}
	public Key ceiling(Key key){
		int i=rank(key);
		return keys[i];
	}
	public Key floor(Key key){
        if (key == null) throw new IllegalArgumentException("argument to floor() is null"); 
        int i = rank(key);
        if (i < N && key.compareTo(keys[i]) == 0) {
        	return keys[i];
        }else{
        	return keys[i-1];
        }
	}
	public Iterable<Key> keys(Key lo,Key hi){
		Queue<Key> queue=new Queue<Key>();
		for(int i=rank(lo);i<rank(hi);i++){
			queue.enqueue(keys[i]);
		}
		if(contains(keys[rank(hi)])){
			queue.enqueue(keys[rank(hi)]);
		}
		return queue;
	}
}  

算法分析：

有序数组二分查找的各个操作的成本:

BinarySearchST的算法实现了最优的查找效率~lgN，但是插入操作很慢~N，无法保证高效的查找和插入操作。