【代码】符号表

发表于 更新于 阅读次数：

前言

符号表的Java版实现

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package com;

public class SymbolTable<Key, Value> {

    public Node head;
    public int symbolTableLength;

    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 SymbolTable() {
        head = new Node(null, null, null);
        symbolTableLength = 0;
    }

    /**
     * 获取符号表所有元素的个数
     * @return
     */
    public int size() {
        return symbolTableLength;
    }

    /**
     * 根据Key，获取Value
     * @param key
     * @return
     */
    public Value get(Key key) {
        // 找到key结点
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        // 没找到的话
        return null;
    }

    /**
     * 插入一个新结点
     *  如果存在key，就直接修改value
     *  如果不存在key，就添加一个键值对
     * @param key
     * @param value
     */
    public void put(Key key, Value value) {
        // 设置一个开关
        boolean flag = true;
        // 查找key是否存在
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            if (n.key.equals(key)) {
                n.value = value;
                flag = false;
                break;
            }
        }
        if (flag) {
            // 找到最后一个结点
            Node nLast = head;
            while (nLast.next!=null) {
                nLast = nLast.next;
            }
            // 创建一个新结点
            Node node = new Node(key, value, null);
            // 把最后一个结点的下一个结点设置为新结点
            nLast.next = node;
        }
        // 长度自增
        symbolTableLength++;
    }

    public boolean delete(Key key) {
        // 前驱元素
        Node nLeft = null;
        // 找到key结点
        Node n = head;
        while (n.next!=null) {
            nLeft = n;
            n = n.next;
            if (n.key.equals(key)) {
                // 如果后驱元素不为空，设置前驱元素的后一个元素为后驱元素
                if (n.next!=null) {
                    nLeft.next = n.next;
                }
                // 如果后驱元素为空，设置前驱元素的后一个元素为空
                else {
                    nLeft.next = null;
                }
                // 长度自减
                symbolTableLength--;
                return true;
            }
        }
        return false;
    }

    public String toString() {
        String str = "{";
        Node n = head;
        while (n.next!=null) {
            n = n.next;
            str += n.key + ":" + n.value + ", ";
        }
        str += "}";
        return str;
    }

}

完成

参考文献

哔哩哔哩——黑马程序员