符号表

介绍

符号表是一种键值对的数据结构，可以快速查找
分为有序和无序两种。
有序的可以实现min,max,根据键的大小来实现的操作。所以需要实现Compareable接口。

链表实现无序符号表

import javax.xml.soap.Node;

public class ListUnorderedST<Key,Value> implements UnorderedST<Key,Value> {
    private Node first;
    private class Node{
        Key key;
        Value value;
        Node next;
        Node(Key key,Value value,Node next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }
    @Override
    public int size() {
        int cnt=0;
        Node cur=first;
        while (cur!=null){
            cnt++;
            cur=cur.next;
        }
        return cnt;
    }

    @Override
    public Value get(Key key) {
        Node cur=first;
        while (cur!=null){
            if(cur.key.equals(key)){
                return cur.value;
            }
            cur=cur.next;
        }
        return null;
    }

    @Override
    public void put(Key key, Value value) {
        Node cur=first;
        //如果已经存在key，覆盖掉，不存在加到头上。利用头插法。
        while(cur!=null){
            if(cur.key.equals(key)){
                cur.value=value;
                return;
            }
            cur=cur.next;
        }
        first=new Node(key,value,first);
    }

    @Override
    public void delete(Key key) {
        if(first==null){
            return;
        }
        if(first.key.equals(key)){
            first=first.next;
        }
        Node pre=first,cur=first.next;
        while (cur!=null){
            if(cur.key.equals(key)){
                pre.next=cur.next;
                return;
            }
            pre=pre.next;
            cur=cur.next;
        }
    }
}

二分查找实现有序符号表

使用一个平行数组，keys,values,一个存储键，一个存储值
rank方法是二分查找，当键在表中可以找到，不在表中可以知道在哪添加
二分查找最多需要log（N)+1，查找是对数级别，添加是线性级别。

import javafx.scene.shape.VLineTo;

import java.util.ArrayList;
import java.util.List;

public class BinarySearchOrderedST<Key extends Comparable<Key>,Value> implements OrderedST<Key,Value> {
    private Key[] keys;
    private Value[] values;
    private int N=0;
    public BinarySearchOrderedST(int capacity){
        keys=(Key[]) new Comparable[capacity];
        values=(Value[]) new Object[capacity];
    }
    @Override
    public int size() {
        return N;
    }

    @Override
    public Value get(Key key) {
        int index=rank(key);
        if(index<N&&keys[index].compareTo(key)==0){
            return values[index];
        }
        return null;
    }

    @Override
    public void put(Key key, Value value) {
        int index=rank(key);
        //若存在则更新
        if(index<N&&keys[index].compareTo(key)==0){
            values[index]=value;
        }
        //否则插入元素，需要先将插入位置之后的元素都向后移动一个单位
        for(int j=N;j>index;j--){
            keys[j]=keys[j-1];
            values[j]=values[j-1];
        }
        keys[index]=key;
        values[index]=value;
        N++;
    }
    @Override
    public Key min() {
        return keys[0];
    }

    @Override
    public Key max() {
        return keys[N-1];
    }

    @Override
    public int rank(Key key) {
        int l=0;
        int h=N-1;
        while (l<=h){
            int m=(l+h)/2;
            int cmp=key.compareTo(keys[m]);
            if(cmp==0){
                return m;
            }
            else if(cmp>0){
                l=m+1;
            }else{
                h=m-1;
            }
        }
        return l;
    }

    @Override
    public List<Key> keys(Key l, Key h) {
        int index=rank(l);
        List<Key> list=new ArrayList<>();
        while (keys[index].compareTo(h)<=0){
            list.add(keys[index]);
            index++;
        }
        return list;
    }
}