数据结构与算法（五）符号表

　　符号表定义
　　符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。
　　符号表中，键具有唯一性。符号表在实际生活中的使用场景是非常广泛的，见下表：
　　应用
　　查找目的
　　键
　　值
　　字典
　　找出单词的释义
　　单词
　　释义
　　图书索引
　　找出某个术语相关的页码
　　术语
　　一串页码
　　网络搜索
　　找出某个关键字对应的网页
　　关键字
　　网页名称符号表实现结点类设计
　　类名
　　NodeK，V
　　构造方法
　　Node（Kkey，Vvalue，NodeK，Vnext）：创建Node对象
　　成员变量privateKkey：存储键
　　privateVvalue：存储值
　　privateNodeK，Vnext：存储下一个结点结点类代码实现AllArgsConstructorNoArgsConstructorprivatestaticclassNodeK，V｛键publicKkey；值publicVvalue；下一个结点publicNodeK，Vnext；｝符号表设计
　　类名
　　SymbolTableK，V
　　成员方法publicVget（Kkey）：根据键key，找对应的值
　　publicvoidput（Kkey，Vvalue）：向符号表中插入一个键值对
　　publicvoiddelete（Kkey）：删除键为key的键值对
　　publicintsize（）：获取符号表的大小
　　成员变量privateNodehead：记录首结点
　　privateintn：记录符号表中键值对的个数符号表代码实现publicclassSymbolTableK，V｛privatefinalNodeK，Vhead；privateintn；publicSymbolTable（）｛this。headnewNode（）；this。n0；｝根据键key，找对应的值publicVget（Kkey）｛符号表中存在key，找到keyvarnodehead；while（node。next！null）｛nodenode。next；if（Objects。equals（key，node。key））｛returnnode。value；｝｝returnnull；｝publicvoidput（Kkey，Vvalue）｛符号表中存在key，找到key替换值varnodehead；while（node。next！null）｛nodenode。next；if（Objects。equals（key，node。key））｛node。valuevalue；return；｝｝不存在，新建结点varoldFirsthead。next；head。nextnewNode（key，value，oldFirst）；n；｝publicvoiddelete（Kkey）｛符号表中存在key，找到key删除之varnodehead；while（node。next！null）｛if（Objects。equals（key，node。next。key））｛node。nextnode。next。next；n；return；｝nodenode。next；｝｝publicintsize（）｛returnn；｝AllArgsConstructorNoArgsConstructorprivatestaticclassNodeK，V｛键publicKkey；值publicVvalue；下一个结点publicNodeK，Vnext；｝｝有序符号表实现
　　刚才实现的符号表，我们可以称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活中，有时候我们需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来我们就实现一下有序符号表。泛型K实现Comparable接口publicclassOrderedSymbolTableKextendsComparableK，V｛。。。｝修改put方法，使插入的元素K有序publicvoidput（Kkey，Vvalue）｛varcurrenthead。next；记录当前结点varprehead；记录上一个结点while（current！nullkey。compareTo（current。key）0）｛precurrent；currentcurrent。next；｝如果key和当前节点一致，修改if（current！nullkey。compareTo（current。key）0）｛current。valuevalue；return；｝没有找到相同的key，把新结点插入到curr之前pre。nextnewNode（key，value，current）；n；｝
　　测试结果正确