符号表

---

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够存储的数据元素是一个键和一个值共同组成的键值对数据，可以根据键来查找对应的值。符号表中，键具有唯一性。

符号表的API设计：

结点类：

类名	Node\
构造方法	Node(Key key, Value value, Node next)
成员变量	public Key key
	public Value value
	public Node next

符号表：

类名	SymbolTable\
构造方法	SymbolTable()
成员方法	public Vaule get(Key key)
	public void put(Key key, Value val)
	public void delete(Key key)
	public int size()
成员变量	private Node head
	private int N

public class SymbolTable<Key,Value>{
    private Node head;
    private int N;
    private class Node{
        public Key key;
        public Value value;
        public Node next;
        public Node(Key key, Value value, Node node){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    public SymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }
    
    public int size(){
        return this.N;
    }
    
    public void put(Key key, Value value){
        //符号表中已经存在建为key的键值对，那么需要找到该结点，替换value
        Node temp = head;
        while(temp.next != null){
            temp = temp.next;
            if(temp.key.equals(key)){
                temp.value = value;
                return;
            }
        }
        //如果符号表中不存在键为key的键值对，需要创建新结点，保存要插入的键值对，把新结点插入到链表头部即可
        Node newNode = new Node(key, value, null);
        Node oldFirst = head.next;
        newNode.next = oldFirst;
        head.next = newNode;
        N++;
    }
    
    public void delete(Key key){
        Node temp = head;
        while(temp.next != null){
            if(temp.next.key.equals(key)){
                temp.next = temp.next.next;
                N--;
                return;
            }
            temp = temp.next;
        }
    }
    
    public Value get(Key key){
        Node temp = head;
        while(temp.next != null){
            temp = temp.next;
            if(temp.key.equals(key)){
                return temp.value;
            }
        }
        return null;
    }
}

有序符号表：

上面实现的符号表，称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活中，有时候需要根据键的大小进行排序，插入数据时要考虑顺序。

public class OrderSymbolTable<Key extends Comparable<Key>,Value>{
    private Node head;
    private int N;
    private class Node{
        public Key key;
        public Value value;
        public Node next;
        public Node(Key key, Value value, Node node){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    public OrderSymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }
    
    public int size(){
        return this.N;
    }
    
    public void put(Key key, Value value){
        //定义Node变量，分别记录当前结点和上一结点
        Node curr = head.next;
        Node pre = head;
        while(curr != null && key.compareTo(curr.key) > 0){
            pre = curr;
            curr = curr.next;
        }
        if(curr != null && key.compareTo(key) == 0){
            curr.value = value;
            return;
        }
        Node newNode = new Node(key,value,curr);
        pre.next = newNode;
        N++;
    }
    
    public void delete(Key key){
        Node temp = head;
        while(temp.next != null){
            if(temp.next.key.equals(key)){
                temp.next = temp.next.next;
                N--;
                return;
            }
            temp = temp.next;
        }
    }
    
    public Value get(Key key){
        Node temp = head;
        while(temp.next != null){
            temp = temp.next;
            if(temp.key.equals(key)){
                return temp.value;
            }
        }
        return null;
    }
}