符号表及其三种实现1：链表，有序数组

在通过第二章的方法将数据排序之后，我们常常需要进行查找操作，本章就来介绍查找的方法。我们会使用符号表这个词来表示一张抽象的表格，其实就可以把它看成键值对，而键值对就是字典，键对应单词，值对应单词的意思，发音等。

我们先列出符号表symbol table的API:

然后我们的工作就是选择适当的数据结构去实现它，你可以看到，不同的数据结构对效率的影响有多大

无序链表实现符号表

一个简单选择是链表，每个节点存储一个键值对，具体实现看代码：

class SequentialSearchST{
private:
    Node first; //链表首节点
    class Node{
        Key key;
        Value val; //泛型
        Node next;
    public:
        Node(Key key, Value, val, Node next){
            this.key = key;
            this.val = val;
            this.next = next;
        }
    };

public:
    //查找给定的键，返回相关联的值
    Value get(Key key){
        for(Node x = first; x!= NULL; x = x.next){
            if(key==x.key){
                return x.val;
            }
        }
        return NULL;
    }

    //插入给定的键，若存在则更新val
    void put(Key key, Value val){
        for(Node x = first; x!= NULL; x = x.next){
            if(key == x.key){
                x.val = val;
                return;
            }
        }
        //如果没找到，就头插该节点
        first = new Node(key, val, first);
    }
};

有一个很好的地方在于，put没找到值插入时很方便，直接头插，但无论是put还是get，都需要遍历整个链表，都是O(n)的复杂度，不够快，

有序数组实现符号表

它使用的数据结构是一对平行的数据，一个存储键一个存储值（这种技巧在很多算法题也经常可以用）
因为我们一直保持键的有序性，所以在接下来的代码中，你可以看到我们多次利用rank函数，它返回表中小于给定键的键的数量

class BinarySearchST
{
    vector<Key> keys;
    vector<value> val;
    int N;

public:
    int size(){ return N; }

    //后面实现，先假设它实现了
    int rank(Key key);

    Value get(Key key){
        if(isEmpty()) return NULL;
        int i = rank(key);
        if(i<N && keys[i] == key) return vals[i]; //找到了
        else return NULL;
    }

    void put(Key key, Value val){
        int i = rank(key);
        //找到就更新val
        if(i<N && keys[i] == key) {vals[i]=val; return;}
        //如果没找到就要插入，插入的话就要让i-N的元素后移来腾位置
        for(int j=N; j>i; j--){
            keys[i] = keys[i-1];
            vals[j] = vals[j-1];
        }
        keys[i] = key; vals[i] = val;
        N++;

    }
};
//就是个二分查找
int BinarySearchST::rank(Key key){
    int lo = 0, hi = N-1;
    while(lo<=hi){
        int mid = lo + (hi-lo)/2;
        if(key<keys[mid]) hi= mid-1;
        else if(key>keys[mid]) lo = mid+1;
        else return mid;
    }
    return lo;
}
//问一个小问题，如果查找的元素不在符号表中，返回的数字还是小于该键的数量吗？
//答案：是的，不清楚的可以看下图

这个数据结构通过维持键数组的有序性，再通过二分查找，使得get复杂度下降到O(logN)，但是还有一点不好，就是插入的时候要腾位置，复杂度还是O(logN)