初始数据结构之符号表

• 结构

键值对，仅此而已，一个key一个value组成，下边演示的是通过链表形式实现的符号表。并且符号表要求key唯一。

• 自己实现符号表抽象类

public abstract class SymbolTable {

    // 头部节点
    protected Node headNode;
    // 符号表元素个数
    protected int size;

    public SymbolTable() {
        this.headNode = new Node<>(null, null, null);
        this.size = 0;
    }

    
    public int size() {
        return this.size;
    }

    
    public V get(K key) {
        Node temp = this.headNode;
        while (temp.next != null) {
            temp = temp.next;
            if (temp.key.equals(key)) {
                return temp.value;
            }
        }
        return null;
    }

    
    public abstract void put(K key, V value);

    
    public void delete(K key) {
        Node preNode = this.headNode;
        Node currentNode;
        while (preNode.next != null) {
            currentNode = preNode.next;
            if (currentNode.key.equals(key)) {
                preNode.next = currentNode.next;
                this.size --;
                return ;
            }
            preNode = currentNode;
        }
    }


    
    class Node {
        K key;
        V value;
        Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

• 特点

元素的插入没有顺序，通常新增元素为直接插入在头节点之后。

• 自己实现无序符号表

public class NormalSymbolTable extends SymbolTable {

    
    public void put(K key, V value) {
        Node temp = this.headNode;
        // 确定key的唯一性，key存在就进行值的替换
        while (temp.next != null) {
            temp = temp.next;
            if (temp.key.equals(key)) {
                temp.value = value;
                return ;
            }
        }
        // key不存在，就从头部新增一个节点
        temp = this.headNode.next;
        Node currentNode = new Node(key, value, temp);
        this.headNode.next = currentNode;
        this.size ++;
    }
}

• 特点

元素插入时是按照key的顺序进行放置的。

• 自己实现有序符号表

public class OrderSymbolTable, V> extends SymbolTable{

    
    @Override
    public void put(K key, V value) {
        Node preNode = this.headNode;
        Node currentNode = this.headNode.next;
        while (currentNode != null) {
            if (key.compareTo(currentNode.key) < 0) break;
            if (currentNode.key.equals(key)) {
                currentNode.value = value;
                return;
            }
            preNode = currentNode;
            currentNode = currentNode.next;
        }
        Node newNode = new Node(key, value, currentNode);
        preNode.next = newNode;
        this.size ++;
    }
}