浅谈算法和数据结构 六 符号表及其基本实现

前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。

在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。

一符号表

在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，每一个元素都有一个key和value，我们可以往里面添加key，value键值对，也可以根据key来查找value。在现实的生活中，我们经常会遇到各种需要根据key来查找value的情况，比如DNS根据域名查找IP地址，图书馆根据索引号查找图书等等：

为了实现这一功能，我们定义一个抽象数据结构，然后选用合适的数据结构来实现：

public class ST<Key, Value>

二实现

1 使用无序链表实现查找表

查找表的实现关键在于数据结构的选择，最简单的一种实现是使用无序链表来实现，每一个节点记录key值，value值以及指向下一个记录的对象。

如图，当我们往链表中插入元素的时候，从表头开始查找，如果找到，则更新value，否则，在表头插入新的节点元素。