数据结构：符号表

「爱情、让人受尽委屈。」 2023-01-15 11:29 38阅读 0赞

### 目录 ###

*  第一章 无序符号表介绍
 *  第二章 无序符号表实现
 *   *  2.1、基本结构
     *  2.2、添加替换
     *  2.3、删除方法
     *  2.4、获取方法
     *  2.5、获取键集合
     *  2.6、获取值集合
     *  2.7、代码测试
 *  第三章 有序符号表介绍
 *  第四章 有序符号表实现
 *   *  4.1、基本结构
     *  4.2、添加替换
     *  4.3、删除方法
     *  4.4、获取方法
     *  4.5、获取键集合
     *  4.6、获取值集合
     *  4.7、代码测试

--------------------

> 项目地址：https://gitee.com/caochenlei/data-structures

# 第一章 无序符号表介绍 #

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。符号表中，键具有唯一性。

![7dc0c1e8584dc12313b71a69965daa52.png][]

# 第二章 无序符号表实现 #

## 2.1、基本结构 ##

public class SymbolTable<Key, Value> { 
        private class Node {     //结点类
            public Key key;     //存储键
            public Value value; //存储值
            public Node next;   //下一个
    
            public Node(Key key, Value value) { 
                this.key = key;
                this.value = value;
            }
        }
    
        private Node head;      //记录头结点
        private int size;       //键值对个数
    
        public SymbolTable() { 
            this.head = new Node(null, null);
            this.size = 0;
        }
    
        //获取符号表键值个数
        public int size() { 
            return size;
        }
    
        //判断符号表是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //接下来的方法写在这
    }

## 2.2、添加替换 ##

//向符号表插入键值对
    public void put(Key key, Value value) { 
        //符号表中已经存在了键为key的键值对，那么只需要找到该结点，然后替换值为value即可。
        Node n = head;
        while ((n = n.next) != null) { 
            if (n.key.equals(key)) { 
                n.value = value;
                return;
            }
        }
        //如果符号表中不存在键为key的键值对，需要创建新的结点，把新结点插入到链表的头部即可。
        Node newFirst = new Node(key, value);
        Node oldFirst = head.next;
        head.next = newFirst;
        newFirst.next = oldFirst;
        size++;
    }

## 2.3、删除方法 ##

//删除符号表中键为key的键值对
    public void delete(Key key) { 
        Node n = head;
        while (n.next != null) { 
            //判断n结点的下一个结点的键是否为key，如果是，就删除该结点
            if (n.next.key.equals(key)) { 
                n.next = n.next.next;
                size--;
                return;
            }
            //判断n结点的下一个结点的键是否为key，如果否，就继续向后找
            else { 
                n = n.next;
            }
        }
    }

## 2.4、获取方法 ##

//获取符号表中键为key的value
    public Value get(Key key) { 
        Node n = head;
        while ((n = n.next) != null) { 
            if (n.key.equals(key)) { 
                return n.value;
            }
        }
        return null;
    }

## 2.5、获取键集合 ##

//获取符号表中所有key的集合
    public Set<Key> keySet() { 
        Set<Key> keySet = new HashSet<>();
        Node n = head;
        while ((n = n.next) != null) { 
            keySet.add(n.key);
        }
        return keySet;
    }

## 2.6、获取值集合 ##

//获取符号表中所有value的集合
    public Set<Value> valueSet() { 
        Set<Value> valueSet = new HashSet<>();
        Node n = head;
        while ((n = n.next) != null) { 
            valueSet.add(n.value);
        }
        return valueSet;
    }

## 2.7、代码测试 ##

public class SymbolTableTest { 
        public static void main(String[] args) { 
            SymbolTable<Integer, String> symbolTable = new SymbolTable<>();
    
            symbolTable.put(1, "刘备");
            symbolTable.put(3, "关羽");
            symbolTable.put(2, "张飞");
    
            System.out.println(symbolTable.size());
            System.out.println(symbolTable.isEmpty());
            System.out.println(symbolTable.keySet());
            System.out.println(symbolTable.valueSet());
            for (Integer key : symbolTable.keySet()) { 
                System.out.println(key + "：" + symbolTable.get(key));
            }
            for (Integer key : symbolTable.keySet()) { 
                symbolTable.delete(key);
            }
            System.out.println(symbolTable.size());
            System.out.println(symbolTable.isEmpty());
            System.out.println(symbolTable.keySet());
            System.out.println(symbolTable.valueSet());
        }
    }

3
    false
    [1, 2, 3]
    [关羽, 张飞, 刘备]
    1：刘备
    2：张飞
    3：关羽
    0
    true
    []
    []

![e2ea55677410ab565b5f65045049a7c0.png][]

# 第三章 有序符号表介绍 #

刚才实现的符号表，我们可以称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活中，有时候我们需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来我们就实现一下有序符号表。符号表中，键具有唯一性。

![7dc0c1e8584dc12313b71a69965daa52.png][]

# 第四章 有序符号表实现 #

## 4.1、基本结构 ##

public class OrderSymbolTable<Key extends Comparable<Key>, Value> { 
        private class Node {     //结点类
            public Key key;     //存储键
            public Value value; //存储值
            public Node next;   //下一个
    
            public Node(Key key, Value value) { 
                this.key = key;
                this.value = value;
            }
        }
    
        private Node head;      //记录头结点
        private int size;       //键值对个数
    
        public OrderSymbolTable() { 
            this.head = new Node(null, null);
            this.size = 0;
        }
    
        //获取符号表键值个数
        public int size() { 
            return size;
        }
    
        //判断符号表是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //接下来的代码写在这
    }

## 4.2、添加替换 ##

//向符号表插入键值对
    public void put(Key key, Value value) { 
        //定义两个Node变量，分别记录当前结点和当前结点的上一个结点
        Node prev = head;
        Node curr = head.next;
        while (curr != null && key.compareTo(curr.key) > 0) { 
            prev = curr;
            curr = curr.next;
        }
        //如果当前结点curr的键和要插入的key一样，则直接替换value
        if (curr != null && key.compareTo(curr.key) == 0) { 
            curr.value = value;
        }
        //如果当前结点curr的键和要插入的key不一样，插入curr之前
        else { 
            Node newNode = new Node(key, value);
            prev.next = newNode;
            newNode.next = curr;
            size++;
        }
    }

## 4.3、删除方法 ##

## 4.4、获取方法 ##

## 4.5、获取键集合 ##

## 4.6、获取值集合 ##

## 4.7、代码测试 ##

public class OrderSymbolTableTest { 
        public static void main(String[] args) { 
            OrderSymbolTable<Integer, String> orderSymbolTable = new OrderSymbolTable<>();
    
            orderSymbolTable.put(1, "刘备");
            orderSymbolTable.put(3, "关羽");
            orderSymbolTable.put(2, "张飞");
    
            System.out.println(orderSymbolTable.size());
            System.out.println(orderSymbolTable.isEmpty());
            System.out.println(orderSymbolTable.keySet());
            System.out.println(orderSymbolTable.valueSet());
            for (Integer key : orderSymbolTable.keySet()) { 
                System.out.println(key + "：" + orderSymbolTable.get(key));
            }
            for (Integer key : orderSymbolTable.keySet()) { 
                orderSymbolTable.delete(key);
            }
            System.out.println(orderSymbolTable.size());
            System.out.println(orderSymbolTable.isEmpty());
            System.out.println(orderSymbolTable.keySet());
            System.out.println(orderSymbolTable.valueSet());
        }
    }

3
    false
    [1, 2, 3]
    [关羽, 张飞, 刘备]
    1：刘备
    2：张飞
    3：关羽
    0
    true
    []
    []

![32a0420d40797f649d819974137dd636.png][]

[7dc0c1e8584dc12313b71a69965daa52.png]: /images/20221022/8beaba26713e4a37b7d4a2d77a2aa2fc.png
[e2ea55677410ab565b5f65045049a7c0.png]: /images/20221022/08ba09b97d094e1190c7cac99a5c8490.png
[32a0420d40797f649d819974137dd636.png]: /images/20221022/496440fcdcc941c699b0c0f0a63aa622.png