1.知识储备
2.构建API：
3.代码实现：
package Symbol; import java.util.Iterator; public class symbolTable,value> implements Iterable { //头节点 private Node head; //记录符号表中元素个数 private int N; //构造方法，初始化符号表 public symbolTable() { // TODO Auto-generated constructor stub this.head=new Node(null,null,null); this.N=0; } //节点类 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 int size(){ return N; } //根据key值查找对应的值 public value get(key key){ //找到key所对应的节点 Node n=head; while(n.next!=null){ if(n.next.key.equals(key)){ return n.next.value; } //变换n的值 n=n.next; } return null; } //向符号表中插入一个键值对 public void insert(key key,value value){ //两种情况 //1.如果符号表中已经存在键为key键值对，那么只需要找到该节点，替换值为value即可 //创建一个节点记录当前节点 Node n=head; while(n.next!=null){ //n往下走，遍历 n=n.next; //判断n节点的键是否等于key，如果是，则替换value即可 if(n.key.equals(key)){ n.value=value; return; //退出即可 } } //2.如果符号表中不存在键为key的键值对，只需要创建新的节点，保存要插入的键值对，让head.next=新节点即可，元素个数+1 Node newNode=new Node(key, value, null); Node oldFirst=head.next; newNode.next=oldFirst; head.next=newNode; N++; } //有序符号表 //要实现有序插入，需要泛型key基础comparable接口，利用里面的compareTo方法进行key的比较，从而找到合适的位置进行插入 public void orderInsert(key key,value value){ //定义两个节点，分别记录当前节点和当前节点的上一个节点 Node curr=head.next; Node pre=head; //开始遍历，如果当前节点不为空，且key比当前节点的键要小，那么就继续往后找，直到找到键比key小的节点为止 while(curr!=null && key.compareTo(curr.key)<0){ //变换currencies和pre即可 pre=curr; curr=curr.next; } //如果当前节点的键和要插入的key一样，则进行value替换 if(curr!=null && key.compareTo(curr.key)==0){ curr.value=value; return; } //如果当前节点的键和要插入的key不一样，则把新节点插入到curr之前即可 Node newNode= new Node(key,value,curr); pre.next=newNode; N++; //元素个数+1 } //删除键为key的键值对 public void delete(key key){ //找到键为key的键值对，把该节点从链表中删除 //创建节点n记录当前节点 Node n=head; while(n.next!=null){ //判断n节点的下一个节点是否为key，是的话就删除即可 if(n.next.key.equals(key)){ n.next=n.next.next; N--; return; } //变换n的值 n=n.next; } } @Override public Iterator iterator() { // TODO Auto-generated method stub return new SIterator(); } private class SIterator implements Iterator{ private Node n; public SIterator() { // TODO Auto-generated constructor stub this.n=head; } @Override public boolean hasNext() { // TODO Auto-generated method stub return n.next!=null; } @Override public Object next() { // TODO Auto-generated method stub n=n.next; Integer keys=(Integer) n.key; String values=(String)n.value; String result="["+keys+"-"+values+"]"; return result; } } }
4.测试案例1：
package Symbol;
public class symbolTableTest {
public static void main(String[] args) {
//创建一个符号表
symbolTable tab1 =new symbolTable();
//插入元素
tab1.insert(1, "蝙蝠侠");
tab1.insert(2, "钢铁侠");
tab1.insert(3, "蜘蛛侠");
tab1.insert(4, "雷神");
tab1.insert(5, "美国队长");
//遍历
for(String str:tab1){
System.out.print(str+"->");
}
System.out.println("n---------------------------------------------");
//查找元素
System.out.println(tab1.get(2));
//获取大小
System.out.println(tab1.size());
//删除元素
tab1.delete(1);
//遍历
for(String str:tab1){
System.out.print(str+"->");
}
System.out.println("n---------------------------------------------");
//获取大小
System.out.println(tab1.size());
}
}
结果：
6.测试案例2：
package Symbol;
public class OrderSymbolTableTest {
public static void main(String[] args) {
symbolTable tab =new symbolTable();
tab.insert(1,"蜘蛛侠");
tab.insert(3,"蝙蝠侠");
tab.insert(4,"钢铁侠");
tab.orderInsert(2,"绿巨人");
tab.insert(6, "超人");
tab.orderInsert(5,"美国队长");
for(String str:tab){
System.out.print(str+"-->");
}
System.out.println();
}
}
结果：
