符号表最主要的目的是将一个键和一个值联系起来,通过查找键的方式找到对应的值。其中键具有唯一性。
如座位号、图书编号等,具有一一对应的关系。
public class SymbolTable<Key, Value> { private Node head; // 首节点 private int N; // 长度 public SymbolTable(){ head = new Node<>(); } private class Node<Key, Value>{ public Key key; // 键 public Value value; // 值 public Node next; // 下指针 public Node(){} public Node(Key key, Value value){ this.key = key; this.value = value; } } /** * 根据键,返回对应值 * @param key 键 * @return 值 */ public Value get(Key key){ Node tmp = this.head; while (tmp.next != null && !tmp.next.key.equals(key)) tmp = tmp.next; return tmp.next == null ? null : (Value)tmp.next.value; } /** * 向符号表中插入一个键值对 * 注意:键具有唯一性!!! 如果插入的键key已存在则覆盖值value * @param key 键 * @param val 值 */ public void put(Key key, Value val){ Node tmp = this.head; while(tmp.next != null && !tmp.next.key.equals(key)){ tmp = tmp.next; } if(tmp.next != null && tmp.next.key.equals(key)){ tmp.next.value = val; return; } Node<Key, Value> newNode = new Node<>(key, val); newNode.next = tmp.next; tmp.next = newNode; this.N++; } /** * 删除指定键的键值对 不存在不删除 * @param key */ public void delete(Key key){ Node tmp = this.head; while (tmp.next != null && !tmp.next.key.equals(key)) tmp = tmp.next; if(tmp.next == null) return; if(tmp.next.next != null) tmp.next = tmp.next.next; else tmp.next = null; this.N--; } public int size(){ return this.N; } public boolean isEmpty(){ return this.N == 0; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); Node tmp = this.head; while (tmp.next != null){ tmp = tmp.next; stringBuilder.append("key: ").append(tmp.key).append(" value: ").append(tmp.value).append("\n"); } return stringBuilder.toString(); } }
测试:
public class SymbolTableTest { public static void main(String[] args) { //创建符号表对象 SymbolTable<Integer, String> symbolTable = new SymbolTable<>(); //测试put方法(插入,替换) symbolTable.put(1,"乔峰"); symbolTable.put(2,"虚竹"); symbolTable.put(3,"段誉"); System.out.println("插入完毕后,元素的个数为:" + symbolTable.size()); System.out.println(symbolTable); symbolTable.put(2, "慕容复"); System.out.println("替换完毕后的元素的个数为:" + symbolTable.size()); System.out.println(symbolTable); //测试get方法 System.out.println("替换完毕后,键2对应的值为:" + symbolTable.get(0)); System.out.println(symbolTable); //测试删除方法 symbolTable.delete(2); System.out.println("删除完毕后,元素的个数:" + symbolTable.size()); System.out.println(symbolTable); } }
package com.jsoft.work; public class OrderSymbolTable<Key, Value> { private Node head; // 首节点 private int N; // 长度 public OrderSymbolTable(){ this.head = new Node<>(); } private class Node<Key, Value>{ public Key key; // 键 public Value value; // 值 public Node next; // 下指针 public Node(){} public Node(Key key, Value value){ this.key = key; this.value = value; } } /** * 根据键,返回对应值 * @param key 键 * @return 值 */ public Value get(Key key){ Node tmp = this.head; while (tmp.next != null && !tmp.next.key.equals(key)) tmp = tmp.next; return tmp.next == null ? null : (Value) tmp.next.value; } /** * 向符号表中按照键的升序插入一个键值对 * 注意:键具有唯一性!!! 如果插入的键key已存在则覆盖值value * @param key 键 * @param val 值 */ public void put(Key key, Value val){ Node tmp = this.head; while (tmp.next != null && String.valueOf(tmp.next.key).compareTo(String.valueOf(key)) < 0) tmp = tmp.next; if(tmp.next != null && tmp.next.key.equals(key)){ tmp.next.value = val; return; } Node<Key, Value> newNode = new Node<>(key, val); newNode.next = tmp.next; tmp.next = newNode; this.N++; } /** * 删除指定键的键值对 不存在不删除 * @param key */ public void delete(Key key){ Node tmp = this.head; while (tmp.next != null && !tmp.next.key.equals(key)) tmp = tmp.next; if(tmp.next == null) return; if(tmp.next.next != null) tmp.next = tmp.next.next; else tmp.next = null; this.N--; } public int getN() { return this.N; } public boolean isEmpty(){ return this.N == 0; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); Node tmp = this.head; while (tmp.next != null){ tmp = tmp.next; stringBuilder.append("key: ").append(tmp.key).append(" value: ").append(tmp.value).append("\n"); } return stringBuilder.toString(); } }
测试:
public class OrderSymbolTableTest { public static void main(String[] args) { //创建有序符号表对象 OrderSymbolTable<Integer, String> table = new OrderSymbolTable<>(); table.put(1,"张三"); table.put(2,"李四"); table.put(4,"赵六"); table.put(7,"田七"); table.put(3,"王五"); System.out.println(table); } }