符号表最主要的目的就是将一个键和一个值联系起来,符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据,我们可以根据键来查找对应的值。
符号表中,键具有唯一性。 符号表在实际生活中的使用场景是非常广泛的,见下表:
应用 | 查找目的 | 键 | 值 |
字典 | 找出单词的释义 | 单词 | 释义 |
图书索引 | 找出某个术语相关的页码 | 术语 | 一串页码 |
网络搜索 | 找出某个关键字对应的网页 | 关键字 | 网页名称 |
类名 | Node |
构造方法 | Node(K key, V value, Node |
成员变量 | private K key:存储键 private V value:存储值 private Node |
@AllArgsConstructor
@NoArgsConstructor
private static class Node {
//键
public K key;
//值
public V value;
//下一个结点
public Node next;
}
类名 | SymbolTable |
成员方法 | public V get(K key):根据键key,找对应的值 public void put(K key, V value):向符号表中插入一个键值对 public void delete(K key):删除键为key的键值对 public int size():获取符号表的大小 |
成员变量 | private Node head:记录首结点 private int n:记录符号表中键值对的个数 |
public class SymbolTable {
private final Node head;
private int n;
public SymbolTable() {
this.head = new Node<>();
this.n = 0;
}
/**
* 根据键key,找对应的值
*/
public V get(K key) {
// 符号表中存在key,找到key
var node = head;
while (node.next != null) {
node = node.next;
if (Objects.equals(key, node.key)) {
return node.value;
}
}
return null;
}
public void put(K key, V value) {
// 符号表中存在key,找到key替换值
var node = head;
while (node.next != null) {
node = node.next;
if (Objects.equals(key, node.key)) {
node.value = value;
return;
}
}
// 不存在,新建结点
var oldFirst = head.next;
head.next = new Node<>(key, value, oldFirst);
n++;
}
public void delete(K key) {
// 符号表中存在key,找到key删除之
var node = head;
while (node.next != null) {
if (Objects.equals(key, node.next.key)) {
node.next = node.next.next;
n--;
return;
}
node = node.next;
}
}
public int size() {
return n;
}
@AllArgsConstructor
@NoArgsConstructor
private static class Node {
//键
public K key;
//值
public V value;
//下一个结点
public Node next;
}
}
刚才实现的符号表,我们可以称之为无序符号表,因为在插入的时候,并没有考虑键值对的顺序,而在实际生活中,有时候我们需要根据键的大小进行排序,插入数据时要考虑顺序,那么接下来我们就实现一下有序符号表。
public class OrderedSymbolTable, V> {
// ...
}
public void put(K key, V value) {
var current = head.next; // 记录当前结点
var pre = head; // 记录上一个结点
while (current != null && key.compareTo(current.key) > 0) {
pre = current;
current = current.next;
}
// 如果key和当前节点一致,修改
if (current != null && key.compareTo(current.key) == 0) {
current.value = value;
return;
}
// 没有找到相同的key,把新结点插入到curr之前
pre.next = new Node<>(key, value, current);
n++;
}
测试结果正确
页面更新:2024-04-25
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号