算法练习_简单符号表

概念

符号表是一种存储键值对的数据结构，主要目的是将一个键和一个值联系起来，能够将一对键值对插入符号表，并希望之后能够从符号表的所有键值对中查找一个键并返回响应的值。支持两种基本操作：

• 插入(put)：将一组新的键值对存入表中。
• 查找(get)：根据给定的键返回相应的值。

API

代码实现

数组实现：

public class ST<K, V> {
    List<Object> keys;
    List<Object> vals;
    int size;

    ST() {
        this.keys = new ArrayList<>();
        this.vals = new ArrayList<>();
        this.size = 0;
    }

    void put(K key, V val) {
        if (key == null) {
            return;
        }
        boolean b = false;
        for (int i = 0; i < keys.size(); i++) {
            if (keys.get(i).equals(key)) {
                vals.set(i, val);
                b = true;
            }
        }

        if (!b) {
            size++;
            keys.add(key);
            vals.add(val);
        }
    }

    V get(K key) {
        if (key == null) {
            return null;
        }
        for (int i = 0; i < keys.size(); i++) {
            if (keys.get(i).equals(key)) {
                return (V) vals.get(i);
            }
        }
        return null;
    }

    void delete(K key) {
        if (key == null) {
            return;
        }
        for (int i = 0; i < keys.size(); i++) {
            if (keys.get(i).equals(key)) {
                keys.remove(i);
                vals.remove(i);
                size--;
            }
        }
    }

    boolean contains(K key) {
        for (Object key1 : keys) {
            if (key1.equals(key)) {
                return true;
            }
        }
        return false;
    }

    boolean isEmpty() {
        return size == 0;
    }

    int size() {
        return size;
    }

    Iterable<K> keys() {
        return (Iterable<K>) keys;
    }
}

链表实现：

public class SequentialSearchST<K extends Comparable<K>, V> {
    private Node first;

    void put(K key, V value) {
        if (key == null) {
            return;
        }
        if (first == null) {
            first = new Node(key, value);
            return;
        }
        Node temp = first;
        while (temp.next != null) {
            if (temp.key.compareTo(key) == 0) {
                temp.value = value;
                return;
            }
            temp = temp.next;
        }
        if (temp.key.compareTo(key) == 0) {
            temp.value = value;
            return;
        }
        temp.next = new Node(key, value);
    }

    V get(K key) {
        if (key == null) {
            return null;
        }

        if (first == null) {
            return null;
        }

        Node temp = first;
        while (temp.next != null) {
            if (temp.key.compareTo(key) == 0) {
                return temp.value;
            }
            temp = temp.next;
        }
        if (temp.key.compareTo(key) == 0) {
            return temp.value;
        }
        return null;
    }

    void delete(K key) {
        if (key == null) {
            return;
        }
        if (key.equals(first.key)) {
            first = first.next;
            return;
        }

        Node temp = first;
        Node pre = null;
        while (temp.next != null) {
            if (temp.key.compareTo(key) == 0) {
                pre.next = temp.next;
                return;
            }
            pre = temp;
            temp = temp.next;
        }

        if (temp.key.compareTo(key) == 0) {
            pre.next = null;
        }
    }

    class Node {
        K key;
        V value;
        Node next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}