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

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

我们先列出符号表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 keys;

vector 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

else return NULL;

}

void put(Key key, Value val){

int i = rank(key);

//找到就更新val

if(i

//如果没找到就要插入，插入的话就要让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

else if(key>keys[mid]) lo = mid+1;

else return mid;

}

return lo;

}

//问一个小问题，如果查找的元素不在符号表中，返回的数字还是小于该键的数量吗？

//答案：是的，不清楚的可以看下图

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