数据结构（四）：符号表
一、 符号表概述
符号表是存储键及对应值的数据结构，符号表中存储的元素由键，值和指向下一个值的指针域组成，可通过键查找到对应的值。
符号表中，键必须是唯一的，而值可以不唯一。
日常生活中，根据关键字百度查找资料，根据目录查找书籍内容，都是符号表使用的体现。
二、 符号表的构造
|
public class Node<Key, Value> { // 符号表key public Key key; // 符号表value public Value value; // 指向下一个结点 public Node next; public Node(Key key, Value value, Node next) { this.key = key; this.value = value; this.next = next; } public static void main(String[] args) { Node node1 = new Node(1, "A", null); Node node2 = new Node(2, "B", null); Node node3 = new Node(3, "C", null); Node node4 = new Node(4, "D", null);
node1.next = node2; node2.next = node3; node3.next = node4; } } |
三、 无序符号表
|
public class SymbolTable<Key,Value> {
//声明头结点 public Node head;
//元素个数 public int N;
public SymbolTable() { head = new Node(null,null,null); N=0; }
/** * 符号表大小 * @return */ public int size() { return N; }
/** * 符号表是否为空 * @return */ public boolean isEmpty() { return N==0; }
/** * 根据key获取value * @param key * @return */ public Value get(Key key) { Node node = head; while(node.next!=null) { node = node.next; if(node.key.equals(key)) { return (Value) node.value; } } return null; }
/** * 根据key删除value * @param key */ public void del(Key key) { Node node = head; while(node.next!=null) { if(node.next.key.equals(key)) { node.next = node.next.next; N--; return; } node = node.next; } }
/** * 存储键值对 * @param key * @param value */ public void put(Key key,Value value) { //符号表中已经存在相同key的情况，替换value值 Node node = head; while(node.next!=null) { node = node.next; if(node.key.equals(key)) { node.value = value; return; } }
//符号表中不存在相同key的情况，新增value值 Node firstNode = head.next; Node newFirstNode = new Node(key, value, firstNode); head.next = newFirstNode;
N++; } } |
四、 有序符号表
上述的符号表，插入元素时没有根据key进行排序，是无序的。
日常使用中，会出现需要根据key进行排序的需求，实现思路是在put方法时，去遍历比较key和当前结点的key大小，当key比当前结点key大时则继续往下走，走到发现没有比key大的当前结点时
比较两个key是否相等，是则替换value，不是则新增结点，并实现连接。
|
public class OrderSymbolTable<Key extends Comparable<Key>,Value>{
//声明头结点 public Node head;
//元素个数 public int N;
public OrderSymbolTable() { head = new Node(null,null,null); N=0; }
/** * 符号表大小 * @return */ public int size() { return N; }
/** * 符号表是否为空 * @return */ public boolean isEmpty() { return N==0; }
/** * 根据key获取value * @param key * @return */ public Value get(Key key) { Node node = head; while(node.next!=null) { node = node.next; if(node.key.equals(key)) { return (Value) node.value; } } return null; }
/** * 根据key删除value * @param key */ public void del(Key key) { Node node = head; while(node.next!=null) { if(node.next.key.equals(key)) { node.next = node.next.next; N--; return; } node = node.next; } }
/** * 存储键值对 * @param key * @param value */ public void put(Key key,Value value) { Node curr = head.next; Node pre = head;
//发现比符号表中存储的key大，则继续遍历 while(curr != null && key.compareTo((Key) curr.key)>0) { pre = curr; curr = curr.next; }
//上述遍历完成后会出现两种情况 //1、出现key相等的情况 if(curr != null && key.equals((Key) curr.key)) { curr.value = value; return; }
//2、没有key相等的情况 Node newNode = new Node<Key, Value>(key, value, curr); pre.next = newNode;
N++; } } |