符号表

符号表最主要的目的就是将一个键和一个值联系起来,符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据,我们可以根据键来查找对应的值

符号表中,键具有唯一性

符号表在实际生活中的场景使用非常广泛,例:

应用查找目的
字典找出单词的释义单词释义
图书索引找出某个术语相关的页码术语页码
网络搜索找出某个关键字对应的网页关键字网页名称

符号表API设计

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

代码实现

SymbolTable
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() {
    //初始化头结点
    this.head = new Node(null, null, null);
    this.N = 0;
  }

  /**
   * 获取符号表中键值对的个数
   */
  public int size() {
    return N;
  }

  /**
   * 往符号表中插入键值对
   */
  public void put(Key key, Value value) {
    //情况1:如果符号表中已经存在键为key的键值对,那么只需要找到该节点,修改key相对应的value即可,但是此情况,元素个数N是不需要+1的
    Node n = head;
    while (n.next != null) {
      n = n.next;
      if (n.key == key) {
        n.value = value;
        return;
      }
    }
    //情况2:如果符号表中不存在键为key的键值对,则需要创建新的节点,保存要插入的键值对,使用头插法,将head指向新插入的键值对即可
    Node newNode = new Node(key, value, null);
    newNode.next = head.next;
    head.next = newNode;
    //元素个数+1
    this.N++;
  }

  /**
   * 删除符号表中键为key的键值对
   */
  public void delete(Key key) {
    //找到键为key的键值对,把该节点从链表中删除
    Node n = head;
    while (n.next != null) {
      //判断n节点的下一个节点是否为key,如果是,则直接删除
      if (n.next.key == key) {
        n.next = n.next.next;
        //元素个数-1
        this.N--;
        return;
      }
      //继续往后找
      n = n.next;
    }
  }

  /**
   * 从符号表中获取key对应的值
   */
  public Value get(Key key) {
    //找到key所在的节点
    Node n = head;
    while (n.next != null) {
      if (n.next.key == key) {
        return n.next.value;
      }
      //继续往后找
      n = n.next;
    }
    return null;
  }
}
SymbolTableTest
public static void main(String[] args) {
    //创建符号表对象
    SymbolTable<Integer, String> symboltable = new SymbolTable<>();
    //测试put方法,1个是插入,1个是替换
    symboltable.put(1, "自由高达");
    symboltable.put(2, "正义高达");
    symboltable.put(3, "扎古");
    System.out.println("插入完毕后,元素的个数为:" + symboltable.size());
    //测试get方法
    System.out.println("没替换前的2号键为:" + symboltable.get(2));
    symboltable.put(2, "菲尼克斯3号机");
    System.out.println("替换后的2号键为:" + symboltable.get(2));
    //测试delete方法
    symboltable.delete(3);
    System.out.println("删除3号键后,元素的个数为:" + symboltable.size());
  }

有序符号表

刚才实现的符号表,我们可以称之为无序符号表,因为在插入的时候,并没有考虑键值对的顺序,而在实际生活中,有时候我们需要根据键的大小进行排序,插入数据时要考虑顺序,那么我就来实现一下有序符号表

代码实现

OrderSymbolTable
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() {
    //初始化头结点
    this.head = new Node(null, null, null);
    this.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;
    }
    //如果当前节点的key键与要插入的key键的值一样,则替换
    if (curr != null && curr.key == key) {
      curr.value = value;
      return;
    }
    //如果小于curr,则插入到curr之前即可
    Node newNode = new Node(key, value, curr);
    pre.next = newNode;
    //元素个数+1
    N++;
  }

  /**
   * 删除符号表中键为key的键值对
   */
  public void delete(Key key) {
    //找到键为key的键值对,把该节点从链表中删除
    Node n = head;
    while (n.next != null) {
      //判断n节点的下一个节点是否为key,如果是,则直接删除
      if (n.next.key == key) {
        n.next = n.next.next;
        //元素个数-1
        this.N--;
        return;
      }
      //继续往后找
      n = n.next;
    }
  }

  /**
   * 从符号表中获取key对应的值
   */
  public Value get(Key key) {
    //找到key所在的节点
    Node n = head;
    while (n.next != null) {
      if (n.next.key == key) {
        return n.next.value;
      }
      //继续往后找
      n = n.next;
    }
    return null;
  }
}
OrderSymbolTableTest

使用Debug调试查看

public static void main(String[] args) {
    //创建有序符号表对象
    OrderSymbolTable<Integer, String> OrderTable = new OrderSymbolTable<>();
    OrderTable.put(1,"正义高达");
    OrderTable.put(2,"自由高达");
    OrderTable.put(4,"菲尼克斯3号机");
    OrderTable.put(8,"扎古");

    OrderTable.put(3,"队长!!!");
  }
Last modification:May 29th, 2021 at 06:51 pm