4.6.1、符号表的定义

符号表（Symbol Table）是一个非常常见的数据结构，在现实生活中应用很多。它是一个“键”—“值”对应的结构。在符号表中，存储的是键值对。通过输入键，查询对应的值。

这个基础的数据结构，在现实生活中使用的特别多，比如字典。

4.6.2、符号表的API设计

结点类：

符号表：

4.6.3、符号表的设计

实现类：

package cn.test.algorithm.datastruct;

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 next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable() {
        head = new Node(null, null, null);
        N = 0;
    }

    public int size() {
        return N;
    }

    public void put(Key key, Value value) {
        //符号表中已经存在键为key的键值对，只需要替换
        Node n = head;
        while (n.next != null) {
            n = n.next;
            if (n.key.equals(key)) {
                n.value = value;
                return;
            }
        }

        //如果不存在，就需要创建新的结点
        Node oldFirst = head.next;//获取第一个结点
        Node newNode = new Node(key, value, oldFirst);
        head.next = newNode;
        N++;
    }

    public Value delete(Key key) {
        //首先需要找到key的结点，然后将结点删除掉
        Node n = head;
        while (n.next != null) {
            n = n.next;
            if (n.key.equals(key)) {
                N--;
                n.next = n.next.next;
                return n.value;
            }
        }
        return null;
    }

    public Value get(Key key) {
        //首先需要找到key的结点，然后将结点删除掉
        Node n = head;
        while (n.next != null) {
            n = n.next;
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.SymbolTable;

public class SymbolTableTest {
    public static void main(String[] args) {
        SymbolTable<String, String> tables = new SymbolTable<>();
        tables.put("zhangsan", "张三");
        tables.put("lisi", "李四");
        tables.put("wangwu", "王五");
        System.out.println("----------------------------------------");
        System.out.println("符号表元素个数:" + tables.size());
        System.out.println(tables.get("zhangsan"));
        System.out.println(tables.get("wangwu"));

        System.out.println("----------------------------------------");
        System.out.println(tables.delete("lisi"));
        System.out.println("符号表元素个数:" + tables.size());

        System.out.println("----------------------------------------");
        tables.put("wangwu", "新王五");
        System.out.println(tables.get("wangwu"));
    }
}

测试结果：

----------------------------------------
符号表元素个数:3
张三
王五
----------------------------------------
李四
符号表元素个数:2
----------------------------------------
新王五

4.6.4、有序符号表的设计

上面我们实现的符号表是没有顺序的，那么如果要实现有序的符号表应该如何做呢？

• key必须要能进行比较，所以需要继承Comparable
• 插入的时候需要进行比较

实现类:

package cn.test.algorithm.datastruct;

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 next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable() {
        head = new Node(null, null, null);
        N = 0;
    }

    public int size() {
        return N;
    }

    public void put(Key key, Value value) {
        //定义两个结点变量，分别记录当前结点和当前结点的上一个结点

        Node curr = head.next;
        Node pre = head;

        while (curr != null && key.compareTo(curr.key) > 0) {
            //编号当前结点
            pre = curr;
            curr = curr.next;
        }

        //如果当前结点curr与要插入的key一样
        if (curr != null && key.compareTo(curr.key) == 0) {
            curr.value = value;
            return;
        }

        //如果当前结点curr与要插入key不一样，把当前结点插入到curr之前
        Node newNode = new Node(key, value, curr);
        pre.next = newNode;

        N++;
    }

    public Value delete(Key key) {
        //首先需要找到key的结点，然后将结点删除掉
        Node n = head;
        while (n.next != null) {
            n = n.next;
            if (n.key.equals(key)) {
                N--;
                n.next = n.next.next;
                return n.value;
            }
        }
        return null;
    }

    public Value get(Key key) {
        //首先需要找到key的结点，然后将结点删除掉
        Node n = head;
        while (n.next != null) {
            n = n.next;
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }
}

测试类:

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.OrderSymbolTable;

public class OrderSymbolTableTest {
    public static void main(String[] args) {
        OrderSymbolTable<Integer, String> tables = new OrderSymbolTable<>();
        tables.put(1, "张三");
        tables.put(2, "李四");
        tables.put(5, "王五");
        tables.put(3, "赵六");
        tables.put(4, "王琦");
    }
}

通过断点查看结果。