符号表(Symbol Table)

xiaohai 2021-07-24 16:15:25 3626人围观 标签: 算法 
简介符号表(Symbol Table)是一个非常常见的数据结构,在现实生活中应用很多。它是一个“键”—“值”对应的结构。在符号表中,存储的是键值对。通过输入键,查询对应的值。

4.6.1、符号表的定义

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

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

图片alt

4.6.2、符号表的API设计

结点类

类名 Node
构造方法 Node(Key key,Value value,Node next):创建Node对象
成员变量 public Key key:存储键
public Value value:存储值
public Node next:存储下一个结点

符号表

类名 SymbolTable
构造方法 SymbolTable():创建SymbolTable对象
成员变量 private Node head:记录首结点
private int N:记录符号表中键值对的个数
成员方法 public Value get(Key key):根据Key找到对应的值
public void put(Key key,Value value):向符号表插入一个键值对
public void delete(Key key):删除键为key的值
public int size():获取符号表大小

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, "王琦");
    }
}

通过断点查看结果。