0001 /* 0002 * 基于列表实现映射结构 0003 */ 0004 0005 package dsa; 0006 0007 public class Map_DLNode implements Map { 0008 private List L;//存放条目的列表 0009 private EqualityTester T;//判等器 0010 0011 //构造方法 0012 public Map_DLNode() 0013 { this(new EqualityTesterDefault()); } 0014 0015 //默认构造方法 0016 public Map_DLNode(EqualityTester t) 0017 { L = new List_DLNode(); T = t; } 0018 0019 /***************************** ADT方法 *****************************/ 0020 //查询映射结构当前的规模 0021 public int getSize() 0022 { return L.getSize(); } 0023 0024 //判断映射结构是否为空 0025 public boolean isEmpty() 0026 { return L.isEmpty(); } 0027 0028 //若M中存在以key为关键码的条目,则返回该条目的数据对象;否则,返回null 0029 public Object get(Object key) { 0030 Iterator P = L.positions(); 0031 while (P.hasNext()) { 0032 Position pos = (Position)P.getNext(); 0033 Entry entry = (EntryDefault) pos.getElem(); 0034 if (T.isEqualTo(entry.getKey(), key)) return entry.getValue(); 0035 } 0036 return null; 0037 } 0038 0039 //若M中不存在以key为关键码的条目,则将条目(key, value)加入到M中并返回null 0040 //否则,将已有条目的数据对象替换为value,并返回原先的数据对象 0041 public Object put(Object key, Object value) { 0042 Iterator P = L.positions(); 0043 while (P.hasNext()) {//逐一对比 0044 Position pos = (Position)P.getNext();//各个位置 0045 Entry entry = (EntryDefault) pos.getElem();//处的条目 0046 if (T.isEqualTo(entry.getKey(), key)) {//若发现key已出现在某个条目中,则 0047 Object oldValue = entry.getValue();//先保留该条目原先的数据对象 0048 L.replace(pos, new EntryDefault(key, value));//再替之以新数据对象 0049 return oldValue;//最后返回原先的数据对象。注意:返回null时的歧义 0050 } 0051 }//若此循环结束,说明key尚未在M中出现,因此 0052 L.insertFirst(new EntryDefault(key, value));//将新条目插至表首,并 0053 return null;//返回null标志 0054 } 0055 0056 //若M中存在以key为关键码的条目,则删除之并返回其数据对象;否则,返回null 0057 public Object remove(Object key) { 0058 Iterator P = L.positions(); 0059 while (P.hasNext()) {//逐一对比 0060 Position pos = (Position)P.getNext();//各个位置 0061 Entry entry = (EntryDefault) pos.getElem();//处的条目 0062 if (T.isEqualTo(entry.getKey(), key)) {//若发现key已出现在某个条目中,则 0063 Object oldValue = entry.getValue();//先保留该条目原先的数据对象 0064 L.remove(pos);//删除该条目 0065 return oldValue;//最后返回原先的数据对象。注意:返回null时的歧义 0066 } 0067 }//若此循环结束,说明key尚未在映射中出现,因此 0068 return null;//返回null标志 0069 } 0070 0071 //返回M中所有条目的一个迭代器 0072 public Iterator entries() 0073 { return new IteratorElement(L); }//直接利用List接口的方法生成元素迭代器 0074 }