符号表--01---概述与实现

符号表定义:符号表最主要的目的就是将一个键和一个值联系起来符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据我们可以根据键来查找对应的值。符号表中键具有唯一性。使用场景:符号表在实际生活中的使用场景是非常广泛的见下表链表实现符号表API设计:结点类符号表代码实现:publicclassSymbolTableKey,Value{//记录首结点privateNodehead;//记录符号表中元素的个数privateintN;publicSymbolTable(){this.headnewNode(null,null,null);this.N0;}//获取符号表中键值对的个数publicintsize(){returnN;}//往符号表中插入键值对publicvoidput(Keykey,Valuevalue){//符号表中已经存在了键为key的键值对那么只需要找到该结点替换值为value即可Nodenhead;while(n.next!null){//变换nnn.next;//判断n结点存储的键是否为key如果是则替换n结点的值if(n.key.equals(key)){n.valuevalue;return;}}//如果符号表中不存在键为key的键值对只需要创建新的结点保存要插入的键值对把新结点插入到链表的头部 head.next新结点即可NodenewNodenewNode(key,value,null);NodeoldFirsthead.next;newNode.nextoldFirst;head.nextnewNode;//元素个数1N;}//删除符号表中键为key的键值对publicvoiddelete(Keykey){//找到键为key的结点把该结点从链表中删除Nodenhead;while(n.next!null){//判断n结点的下一个结点的键是否为key如果是就删除该结点if(n.next.key.equals(key)){n.nextn.next.next;N--;return;}//变换nnn.next;}}//从符号表中获取key对应的值publicValueget(Keykey){//找到键为key的结点Nodenhead;while(n.next!null){//变换nnn.next;if(n.key.equals(key)){returnn.value;}}returnnull;}//节点类privateclassNode{//键publicKeykey;//值publicValuevalue;//下一个结点publicNodenext;publicNode(Keykey,Valuevalue,Nodenext){this.keykey;this.valuevalue;this.nextnext;}}}测试:publicclassSymbolTableTest{publicstaticvoidmain(String[]args){//创建符号表对象SymbolTableInteger,StringsymbolTablenewSymbolTable();//测试put方法插入,替换symbolTable.put(1,乔峰);symbolTable.put(2,虚竹);symbolTable.put(3,段誉);System.out.println(插入完毕后元素的个数为:symbolTable.size());symbolTable.put(2,慕容复);System.out.println(替换完毕后的元素的个数为:symbolTable.size());//测试get方法System.out.println(替换完毕后键2对应的值为:symbolTable.get(2));//测试删除方法symbolTable.delete(2);System.out.println(删除完毕后元素的个数:symbolTable.size());}}有序符号表刚才实现的符号表我们可以称之为无序符号表因为在插入的时候并没有考虑键值对的顺序而在实际生活中有时候我们需要根据键的大小进行排序插入数据时要考虑顺序那么接下来我们就实现一下有序符号表。有序链表实现:publicclassOrderSymbolTableKeyextendsComparableKey,Value{//记录首结点privateNodehead;//记录符号表中元素的个数privateintN;privateclassNode{//键publicKeykey;//值publicValuevalue;//下一个结点publicNodenext;publicNode(Keykey,Valuevalue,Nodenext){this.keykey;this.valuevalue;this.nextnext;}}publicOrderSymbolTable(){this.headnewNode(null,null,null);this.N0;}//获取符号表中键值对的个数publicintsize(){returnN;}//往符号表中插入键值对publicvoidput(Keykey,Valuevalue){//定义两个Node变量分别记录当前结点和当前结点的上一个结点Nodecurrhead.next;Nodeprehead;while(curr!nullkey.compareTo(curr.key)0){//变换当前结点和前一个结点即可precurr;currcurr.next;}//如果当前结点curr的键和要插入的key一样则替换if(curr!nullkey.compareTo(curr.key)0){curr.valuevalue;return;}//如果当前结点curr的键和要插入的key不一样把新的结点插入到curr之前NodenewNodenewNode(key,value,curr);pre.nextnewNode;//元素的个数1N;}//删除符号表中键为key的键值对publicvoiddelete(Keykey){//找到键为key的结点把该结点从链表中删除Nodenhead;while(n.next!null){//判断n结点的下一个结点的键是否为key如果是就删除该结点if(n.next.key.equals(key)){n.nextn.next.next;N--;return;}//变换nnn.next;}}//从符号表中获取key对应的值publicValueget(Keykey){//找到键为key的结点Nodenhead;while(n.next!null){//变换nnn.next;if(n.key.equals(key)){returnn.value;}}returnnull;}}debug测试:数组二分查找实现:使用一对平行数组一个存储键一个存储值。二分查找的思想是在内部维护一个按照key排好序的二维数组每一次查找的时候跟中间元素进行比较如果该元素小则继续左半部分递归查找否则继续右半部分递归查找。整个实现代码如下二分查找的 rank() 方法至关重要当键在表中时它能够知道该键的位置当键不在表中时它也能知道在何处插入新键。/** * 有序数组符号表 */publicclassSymbolTableKextendsComparableK,V{privateK[]keys;//键数组privateV[]values;//值数组publicintsize;privatestaticfinalintinitSize10;//默认数组初始大小publicSymbolTable(){this(initSize);}publicSymbolTable(intcapacity){keys(K[])newComparable[capacity];values(V[])newObject[capacity];}/** * 查找键为K的值 */publicVget(Kk){if(isEmpty()){returnnull;}//在数组中找出值intirank(k);if(isizekeys[i].compareTo(k)0){returnvalues[i];}returnnull;}/** * 插入要给键值对 */publicvoidput(Kk,Vv){intirank(k);//如果已经存在了键就交换值if(isizekeys[i].compareTo(k)0){values[i]v;return;}//否则就把键值插入到最小于K的值之后for(intjsize;ji;j--){keys[j]keys[j-1];values[j]values[j-1];}keys[i]k;values[i]v;size;}publicbooleanisEmpty(){returnsize0;}publicintrank(Kk){intlow0;//低位起始下标inthighsize-1;//高位下标长度-1//高低交叉之前都一直查询while(lowhigh){intmidlow(high-low)/2;//找到中位下标intcmdk.compareTo(keys[mid]);//获取数组中中位值与比较K的大小//如果两个值相等说明找到了if(cmd0){returnmid;//小于0说明比中位值小从数组中中位置左侧搜索}elseif(cmd0){highmid-1;//和上面相反从数组右侧搜索}else{lowmid1;}}//否侧返回低位的值这个值就是小于被查找值的数量returnlow;}}debug测试:总结:本文介绍了符号表这一抽象数据结构然后介绍了两种基本实现基于无序链表的实现和基于有序数组的实现两种实现的时间复杂度如下无序链表实现:插入的时候先要查找如果存在则更新value查找的时候需要从链表头进行查找所以插入和查找的平均时间复杂度均为O(n)数组二分查找:采用二分查找只需要最多 logN1次的比较即可找到对应元素所以查找效率比较高。但是对于插入元素来说每一次插入不存在的元素需要将该元素放到指定的位置然后将他后面的元素依次后移所以平均时间复杂度O(n)对于插入来说效率仍然比较低。使用有序数组的二分查找法提高了符号表的查找速度但是插入效率仍旧没有得到提高而且在要维护数组有序还需要进行排序操作。这两种实现方式简单直观但是无法同时达到较高查找和插入效率。本文只是一个引子后面的系列文章将会介绍二叉查找树平衡查找树以及哈希表。数组实现和链表实现对比: