0001 /* 0002 * 基于有序查找表实现的有序词典 0003 */ 0004 0005 package dsa; 0006 0007 public class SortedDictionary_ExtArray implements SortedDictionary { 0008 Vector S;//有序查找表 0009 Comparator C;//比较器 0010 0011 //默认构造方法 0012 public SortedDictionary_ExtArray() 0013 { this(new ComparatorDefault()); } 0014 0015 //构造方法 0016 public SortedDictionary_ExtArray(Comparator comp) 0017 { S = new Vector_ExtArray(); C = comp; } 0018 0019 /**************************** 辅助方法 ****************************/ 0020 //二分查找 0021 //返回值可能是命中元素的秩,也可能是key可以插入的秩 0022 //具体如何,需要进一步检查 0023 //不变性:若将key按照返回的秩插入有序向量,向量依然有序 0024 private static int binSearch(Vector s, Comparator c, Object key, int lo, int hi) { 0025 if (lo > hi) return lo;//递归基,查找失败 0026 int mi = (lo + hi) >> 1; //取中值 0027 Entry e = (Entry)s.getAtRank(mi);//居中的条目 0028 int flag = c.compare(key, e.getKey());//比较关键码 0029 if (flag < 0) return binSearch(s, c, key, lo, mi - 1); //转向左半区间 0030 else if (flag > 0) return binSearch(s, c, key, mi + 1, hi); //转向右半区间 0031 else return mi;//命中 0032 } 0033 0034 /**************************** 无序词典ADT方法 ****************************/ 0035 //查询词典结构当前的规模 0036 public int getSize() 0037 { return S.getSize(); } 0038 0039 //判断词典结构是否为空 0040 public boolean isEmpty() 0041 { return S.isEmpty(); } 0042 0043 //若词典中存在以key为关键码的条目,则返回其中的一个条目;否则,返回null 0044 public Entry find(Object key) { 0045 int k = binSearch(S, C, key, 0, S.getSize() - 1); //查找关键码为key的条目 0046 if (0 > k || k >= S.getSize() || (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey()))) 0047 return null;//若这样的条目不存在,则返回失败标志 0048 return (Entry) S.getAtRank(k); 0049 } 0050 0051 //返回由关键码为key的条目组成的迭代器 0052 public Iterator findAll(Object key) { 0053 List L = new List_DLNode();//创建一个链表L 0054 int k = binSearch(S, C, key, 0, S.getSize() - 1); //查找关键码为key的条目 0055 if (0 > k || k >= S.getSize() || (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey()))) 0056 return new IteratorElement(L);//若这样的条目不存在,则返回空迭代器 0057 L.insertFirst(S.getAtRank(k));//将e插入L中 0058 int lo = k;//从S[k-1]开始 0059 while (0 <= --lo) {//不断向前搜索 0060 if (0 != C.compare(key, ((Entry)S.getAtRank(lo)).getKey())) break;//直到第一个不命中的条目 0061 L.insertFirst(S.getAtRank(lo));//将命中的条目插入L中 0062 } 0063 int hi = k;//从S[k+1]开始 0064 while (++hi < S.getSize()) {//不断向后搜索 0065 if (0 != C.compare(key, ((Entry)S.getAtRank(hi)).getKey())) break;//直到第一个不命中的条目 0066 L.insertLast(S.getAtRank(hi));//将命中的条目插入L中 0067 } 0068 return new IteratorElement(L);//由L创建迭代器,返回之 0069 } 0070 0071 //插入条目(key, value),并返回该条目 0072 public Entry insert(Object key, Object value) { 0073 Entry e = new EntryDefault(key, value);//创建新条目 0074 //若词典为空,则直接插入新元素 0075 if (S.isEmpty()) return (Entry) S.insertAtRank(0, e); 0076 //通过二分查找,确定可插入位置 0077 //请读者自己检查:即便key在S中为最小或最大,都可以正常插入 0078 return (Entry) S.insertAtRank(binSearch(S, C, key, 0, S.getSize() - 1), e); 0079 } 0080 0081 //若词典中存在以key为关键码的条目,则将摘除其中的一个并返回;否则,返回null 0082 public Entry remove(Object key) { 0083 int k = binSearch(S, C, key, 0, S.getSize() - 1); //查找关键码为key的条目 0084 if (0 > k || k >= S.getSize() || (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey()))) 0085 return null;//若这样的条目不存在,则返回失败标志 0086 return (Entry) S.removeAtRank(k); 0087 } 0088 0089 //返回词典中所有条目的一个迭代器 0090 public Iterator entries() { 0091 List L = new List_DLNode(); 0092 for (int i = 0; i < S.getSize(); i++) 0093 L.insertLast(S.getAtRank(i)); 0094 return new IteratorElement(L);//直接利用List接口的方法生成元素迭代器 0095 } 0096 0097 /**************************** 有序词典ADT方法 ****************************/ 0098 //若词典非空,则返回其中关键码最小的条目;否则,返回null 0099 public Entry first() 0100 { return (S.isEmpty()) ? null : (Entry) S.getAtRank(0); } 0101 0102 //若词典非空,则返回其中关键码最大的条目;否则,返回null 0103 public Entry last() 0104 { return (S.isEmpty()) ? null : (Entry) S.getAtRank(S.getSize() - 1); } 0105 0106 //返回由关键码不小于key的条目依非降序组成的迭代器 0107 public Iterator successors(Object key) { 0108 List L = new List_DLNode();//创建一个链表L 0109 int k = binSearch(S, C, key, 0, S.getSize() - 1); //查找关键码为key的条目 0110 if (0 > k || k >= S.getSize() || (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey()))) 0111 return new IteratorElement(L);//若这样的条目不存在,则返回空迭代器 0112 while (0 <= --k)//从S[k-1]开始向前搜索,直至符合要求的、秩最小的元素 0113 if (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey())) break; 0114 while (S.getSize() > ++k)//将后继的所有元素依次 0115 L.insertLast(S.getAtRank(k));//插入L中 0116 return new IteratorElement(L);//由L创建迭代器,返回之 0117 } 0118 0119 //返回由关键码不大于key的条目依非升序组成的迭代器 0120 public Iterator predecessors(Object key) { 0121 List L = new List_DLNode();//创建一个链表L 0122 int k = binSearch(S, C, key, 0, S.getSize() - 1); //查找关键码为key的条目 0123 if (0 > k || k >= S.getSize() || (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey()))) 0124 return new IteratorElement(L);//若这样的条目不存在,则返回空迭代器 0125 while (S.getSize() > ++k)//从S[k-1]开始向后搜索,直至符合要求的、秩最大的元素 0126 if (0 != C.compare(key, ((Entry)S.getAtRank(k)).getKey())) break; 0127 while (0 <= --k)//将前驱的所有元素依次 0128 L.insertLast(S.getAtRank(k));//插入L中 0129 return new IteratorElement(L);//由L创建迭代器,返回之 0130 } 0131 }