0001 /* 0002 * 基于列表实现(无序)词典结构 0003 */ 0004 0005 package dsa; 0006 0007 public class Dictionary_DLNode implements Dictionary { 0008 private List L;//存放条目的列表 0009 private EqualityTester T;//判等器 0010 0011 //构造方法 0012 public Dictionary_DLNode() 0013 { this(new EqualityTesterDefault()); } 0014 0015 //默认构造方法 0016 public Dictionary_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 //若词典中存在以key为关键码的条目,则返回其中的一个条目;否则,返回null 0029 public Entry find(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; 0035 } 0036 return null; 0037 } 0038 0039 //返回由关键码为key的条目组成的迭代器 0040 public Iterator findAll(Object key) { 0041 List list = new List_DLNode(); 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)) 0047 list.insertLast(entry); 0048 } 0049 return new IteratorElement(list); 0050 } 0051 0052 //插入条目(key, value),并返回该条目 0053 public Entry insert(Object key, Object value) { 0054 Entry entry = new EntryDefault(key, value);//创建新条目 0055 L.insertFirst(entry);//将新条目插至表首,并 0056 return entry;//返回null标志 0057 } 0058 0059 //若词典中存在以key为关键码的条目,则将摘除其中的一个并返回;否则,返回null 0060 public Entry remove(Object key) { 0061 Iterator P = L.positions(); 0062 while (P.hasNext()) {//逐一对比 0063 Position pos = (Position)P.getNext();//各个位置 0064 Entry entry = (EntryDefault) pos.getElem();//处的条目 0065 if (T.isEqualTo(entry.getKey(), key)) {//若发现key已出现在某个条目中,则 0066 Entry oldEntry = entry;//先保留该条目 0067 L.remove(pos);//删除该条目 0068 return oldEntry;//最后返回原先的条目 0069 } 0070 }//若此循环结束,说明key尚未在词典中出现,因此 0071 return null;//返回null标志 0072 } 0073 0074 //返回词典中所有条目的一个迭代器 0075 public Iterator entries() 0076 { return new IteratorElement(L); }//直接利用List接口的方法生成元素迭代器 0077 }