无序符号表

符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值
哈希表一般被称为散列表，而符号表一般是基于hash表去实现的，所以符号表和hash表正常情况下是不能去划等号的

但是，我的理解就是，符号表不过是一种键值对的集合罢了，最常见的符号表就是Hash表.

这篇博文的目的是带大家用前面学的链表思想手动实现一个符号表(无序符号表)

1、首先先创建一个基本的JAVA链表框架

    //首结点
    private Node head;
    //元素个数
    private int n;

    public SymbolTable() {
        head=new Node(null,null,null);
        n=0;
    }
    //Node类
    private class Node{
        //键
        private String key;
        //值
        private String value;
        //下一个结点的地址
        private Node next;

        public Node(String key, String value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

2、然后我们定义如下方法(delete、put、get):

1. delete：参数：@Param(“key”) String key
2. put：参数：String key,String value
3. get:参数：String key

下面我们依次来讲解上面三种方法的实现步骤：
get

    //根据键来找到值
    public String get(String key){
        Node node=head;
        //遍历，取出key
        while (node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                return node.value;
            }
        }
        return null;
    }

delete

    //删除键位key的键值对，并将删除的值给返回
    public String delete(String key){
        //遍历符号表，找出要删除的key
        Node node=head;
        if(node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                //说明找到key，删除下一个结点
                String value=node.next.value;
                node.next=node.next.next;
                //个数-1
                n--;
                return value;
            }
            //每次遍历，都将node的下一个结点赋值给node
        }
        return null;
    }

put

    //向符号表中插入一个键值对
    public String put(String key,String value){
        //先从符号表中查找键为key的键值对的真值表
        Node node=head;
        while (node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                //说明待插入的key已经存在了，直接替换value
                //取出旧value
                String oldValue=node.value;
                node.value=value;
                return oldValue;
            }
        }
        //循环完毕没有结束，说明key在表中不存在
        Node oldFirst=head.next;
        //创建一个新结点.头插法,每一个新的结点都在第一个元素位置
        Node newFirst=new Node(key,value,oldFirst);
        head.next=newFirst;
        //个数+1
        n++;
        return null;
    }

将上面三个无序符号表中主要的方法搞懂之后，我们就可以开始编写mian方法了：

class Test9{
    public static void main(String[] args) {
        SymbolTable table=new SymbolTable();
        table.put("1","张三");
        table.put("2","李四");
        table.put("3","王五");
        System.out.println(table.get("1"));
        System.out.println(table.get("2"));
        System.out.println(table.get("3"));
        System.out.println(table.delete("2"));
    }

}

这样我们就能够达到编写符号表的目的

整体代码:

package com.gm.table;
//无序符号表
public class SymbolTable {
    //首结点
    private Node head;
    //元素个数
    private int n;

    public SymbolTable() {
        head=new Node(null,null,null);
        n=0;
    }
    //根据键来找到值
    public String get(String key){
        Node node=head;
        //遍历，取出key
        while (node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                return node.value;
            }
        }
        return null;
    }
    //向符号表中插入一个键值对
    public String put(String key,String value){
        //先从符号表中查找键为key的键值对的真值表
        Node node=head;
        while (node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                //说明待插入的key已经存在了，直接替换value
                //取出旧value
                String oldValue=node.value;
                node.value=value;
                return oldValue;
            }
        }
        //循环完毕没有结束，说明key在表中不存在
        Node oldFirst=head.next;
        //创建一个新结点.头插法,每一个新的结点都在第一个元素位置
        Node newFirst=new Node(key,value,oldFirst);
        head.next=newFirst;
        //个数+1
        n++;
        return null;
    }
    //删除键位key的键值对，并将删除的值给返回
    public String delete(String key){
        //遍历符号表，找出要删除的key
        Node node=head;
        if(node.next!=null){
            node=node.next;
            if(node.key.equals(key)){
                //说明找到key，删除下一个结点
                String value=node.next.value;
                node.next=node.next.next;
                //个数-1
                n--;
                return value;
            }
            //每次遍历，都将node的下一个结点赋值给node
        }
        return null;
    }
    //获取符号表的大小
    public int size(){
        return n;
    }
    private class Node{
        //键
        private String key;
        //值
        private String value;
        //下一个结点的地址
        private Node next;

        public Node(String key, String value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}
class Test9{
    public static void main(String[] args) {
        SymbolTable table=new SymbolTable();
        table.put("1","张三");
        table.put("2","李四");
        table.put("3","王五");
        System.out.println(table.get("1"));
        System.out.println(table.get("2"));
        System.out.println(table.get("3"));
        System.out.println(table.delete("2"));
    }

}