订阅专栏
目录
符号表API设计
符号表代码实现
有序符号表
符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。
符号表中，键具有唯—性。
符号表在实际生活中的使用场景是非常广泛的，见下表:
符号表API设计
结点类
符号表
符号表代码实现
public class SymbolTable<Key,Value> { //记录首结点 private Node head; //记录符号表中元素的个数 private int N; 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; } } //符号表中没有键为key的键值对 Node oldFirst=head.next; Node newFirst=new Node(key,value,oldFirst); head.next=newFirst; N++; } //删除key键值对 public void delete(Key key){ Node n=head; while(n.next!=null){ if(n.next.key.equals(key)){ n.next=n.next.next; N--; return; } n=n.next; } } //从符号表获取key对应的值 public Value get(Key key){ Node n=head; while(n.next!=null){ n=n.next; if(n.key.equals(key)){ return n.value; } } return null; } 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; } } } class Test{ public static void main(String[] args) { SymbolTable<Integer,String> st=new SymbolTable<Integer, String>(); st.put(1, "龍龍"); st.put(3,"龍弟"); st.put(5,"龍第"); System.out.println(st.get(1)); System.out.println(st.size()); st.delete(1); System.out.println(st.size()); } }
有序符号表
在实际生活中，我们需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来我们就实现一下有序符号表。
1.public class OrderSymbolTable<Key extends Comparable<Key>,Value> { //记录首结点 private Node head; //记录符号表中元素的个数 private int N; 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; //1.如果key大于当前结点的key，则一直寻找下一个节点 while(curr!=null&&key.compareTo(curr.key)>0){ pre=curr; curr=curr.next; } //2.如果当前结点curr的key和将要插入的key一样，则替换 if(curr!=null&&curr.key.compareTo(key)==0){ curr.value=value; return; } //3.没有找到相同的key，则把新结点插入到curr之前 Node newNode=new Node(key,value,curr); pre.next=newNode; } //删除符号表key键值对 public void delete(Key key){ Node n=head; while(n.next!=null){ if(n.next.key.equals(key)){ n.next=n.next.next; N--; return; } n=n.next; } } //从符号表获取key对应的值 public Value get(Key key){ Node n=head; while(n.next!=null){ n=n.next; if(n.key.equals(key)){ return n.value; } } return null; } 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; } } } class Test{ public static void main(String[] args) { OrderSymbolTable<Integer,String> ot=new OrderSymbolTable<>(); ot.put(1, "龍龍"); ot.put(3,"龍弟"); ot.put(5,"龍第"); ot.put(8,"龍哥"); } }
