- 浏览: 182730 次
- 性别:
- 来自: 自己输入城市...
文章分类
- 全部博客 (128)
- Java (13)
- Util (21)
- IO (1)
- Thread (4)
- Net (0)
- Design Patterns (0)
- Training (4)
- ----------------- (0)
- JS-1 (15)
- JS-3 (7)
- AJAX (3)
- AS (2)
- ------------------- (0)
- HTML (3)
- CSS (3)
- Art (15)
- -------------------- (0)
- RegExp (4)
- --------------------- (0)
- SQL (6)
- Servlet $ JSP (2)
- JDBC (2)
- ---------------------- (0)
- Bird (3)
- Setting (7)
- DL (4)
- PHP (4)
最新评论
-
durong11:
或者直接在函数的中加入:if(head.data.equals ...
我的Java单链表练习 -
durong11:
一种解释是:如果是从头结点insert 直接使用addFrom ...
我的Java单链表练习 -
老肥猴_vi:
谢谢。但是貌似insert函数( public boolean ...
我的Java单链表练习 -
niepeng880208:
支持
List转换成String数组 -
haohao-xuexi02:
EventHelp
幻灯片效果
Iterable接口
Iterator接口
Map接口
OrderedMap接口
Set接口
TreeMap类
测试类Test
辅助测试类Time24
package MyInterface; public interface Iterable<T>{ Iterator<T> iterator(); }
Iterator接口
package MyInterface; public interface Iterator<T> { boolean hasNext(); T next(); void remove(); }
Map接口
package MyInterface; import MyInterface.Set; public interface Map<K, V> { int size(); boolean isEmpty(); boolean containsKey(Object key); V get(Object key); V put(K key, V value); V remove(Object key); void clear(); Set<K> keySet(); Set<Map.Entry<K, V>> entrySet(); /** 内部接口 */ interface Entry<K, V> { K getKey(); V getValue(); V setValue(V value); } }
OrderedMap接口
package MyInterface; public interface OrderedMap<K, V> extends Map<K, V> { K firstKey(); K lastKey(); }
Set接口
package MyInterface; import MyInterface.Iterable; public interface Set<T> extends Iterable<T> { int size(); boolean isEmpty(); boolean contains(Object item); Iterator<T> iterator(); Object[] toArray(); boolean add(T item); boolean remove(Object item); void clear(); }
TreeMap类
package Map; import java.util.ConcurrentModificationException; import java.util.NoSuchElementException; import MyInterface.Set; import MyInterface.Map; import MyInterface.OrderedMap; import MyInterface.Iterator; /** * TreeMap类的设计 * @author baby69yy2000 */ public class TreeMap<K, V> implements OrderedMap<K, V> { /*====================TreeMap结点内部类Entry====================*/ private static class Entry<K, V> implements Map.Entry<K, V> { // Entry类实例变量 K key; V value; Entry<K, V> left, right, parent; // Entry结点类构造函数 public Entry(K key, V value, Entry<K, V> parent) { this.key = key; this.value = value; this.left = null; this.right = null; this.parent = parent; } // 取键 public K getKey() { return key; } // 取值 public V getValue() { return value; } // 更新值 // 返回被更新的值 public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public String toString() { return key + "=" + value; } } /*===============================================================*/ /*=========================TreeMap类的设计=========================*/ // TreeMap类实例变量 private Entry<K, V> root; private int mapSize; private int modCount; // TreeMap类构造函数 public TreeMap() { root = null; mapSize = 0; modCount = 0; } // 判断二叉排序树是否为空 public boolean isEmpty() { return mapSize == 0; } // 返回此映射中的键-值映射关系数 public int size() { return mapSize; } public void clear() { modCount++; mapSize = 0; root = null; } // 私有方法 getEntry()接受一个键,并且返回 Entry 对象,或者在映射中不包含这个键时返回 null // 类似二叉排序树的私有方法 findNode() private Entry<K, V> getEntry(K key) { Entry<K, V> entry = root; int orderValue; while(entry != null) { orderValue = ((Comparable<K>)key).compareTo(entry.key); if(orderValue == 0) return entry; else if(orderValue < 0) entry = entry.left; else entry = entry.right; } return null; } // 返回指定键所映射的值,如果对于该键而言,此映射不包含任何映射关系,则返回 null public V get(Object key) { Entry<K, V> p = getEntry((K)key); if(p == null) return null; else return p.getValue(); } // 如果此映射包含指定键的映射关系,则返回 true public boolean containsKey(Object key) { return getEntry((K)key) != null; } // 将指定值与此映射中的指定键进行关联。如果该映射以前包含此键的映射关系,那么将替换旧值 public V put(K key, V value) { Entry<K, V> entry = root, parent = null, newNode; int orderValue = 0; while(entry != null) { parent = entry; orderValue = ((Comparable<K>)key).compareTo(entry.key); if(orderValue == 0) return entry.setValue(value); else if(orderValue < 0) entry = entry.left; else entry = entry.right; } newNode = new Entry<K, V>(key, value, parent); if(parent == null) root = newNode; else if(orderValue < 0) parent.left = newNode; else parent.right = newNode; mapSize++; modCount++; return null; } // 删除结点的私有方法 removeNode private void removeNode(Entry<K, V> dNode) { if (dNode == null) return; // dNode: 待删除结点 // pNode: 待删除结点的父结点 // rNode: 待删除结点的替换结点 Entry<K, V> pNode, rNode; // 待删除结点的父结点找到了 pNode = dNode.parent; // ①待删除的结点至少具有一棵空子树 if(dNode.left == null || dNode.right == null) { // 找替换结点 if(dNode.right == null) rNode = dNode.left; else rNode = dNode.right; // 判断待删除结点是不是叶结点的情况 if(rNode != null) rNode.parent = pNode; // 待删除结点是根结点的情况 if(pNode == null) root = rNode; // 连接替换结点到待删除结点父结点的正确分枝上 else if(((Comparable<K>)dNode.key).compareTo(pNode.key) < 0) pNode.left = rNode; else pNode.right = rNode; // ②待删除的结点具有两个非空子树 }else { // pOfR是替换结点父结点的引用 Entry<K,V> pOfR = dNode; rNode = dNode.right; while(rNode.left != null) { pOfR = rNode; rNode = rNode.left; } // 先将R的(key和value)复制到D dNode.key = rNode.key; dNode.value = rNode.value; // 如果pOfR是待删除的结点,那么将(R的右子树)作为(D的右子结点)连接 if(pOfR == dNode) dNode.right = rNode.right; // 否则将(R的右子树)作为(pOfR的左子结点)连接 else pOfR.left = rNode.right; // 在这两种情况下,我们都必须要更新R的右子树的父结点 if (rNode.right != null) rNode.right.parent = pOfR; dNode = rNode; } dNode = null; } // 删除结点 // 返回删除的结点 public V remove(Object key) { Entry<K,V> dNode = getEntry((K)key); if(dNode == null) return null; V returnedValue = dNode.getValue(); removeNode(dNode); mapSize--; modCount++; return returnedValue; } // 返回最小的键 public K firstKey() { Entry<K, V> nextNode = root; if(nextNode == null) return null; while(nextNode.left != null) nextNode = nextNode.left; return nextNode.key; } // 返回最大的键 public K lastKey() { Entry<K, V> nextNode = root; if(nextNode == null) return null; while(nextNode.right != null) nextNode = nextNode.right; return nextNode.key; } public String toString() { int max = mapSize - 1; StringBuffer buf = new StringBuffer(); Iterator<Map.Entry<K, V>> it = entrySet().iterator(); buf.append("{"); for(int j = 0; j <= max; j++) { Map.Entry<K, V> e = it.next(); buf.append(e.getKey() + "=" + e.getValue()); if(j < max) buf.append(", "); } buf.append("}"); return buf.toString(); } // 跌代器 private class MyIterator<T> implements Iterator<T> { private int expectedModCount = modCount; private Entry<K,V> lastReturned = null; private Entry<K,V> nextNode = null; // 构造函数初始化nextNode指向二叉排序树最小的元素 MyIterator() { nextNode = root; if(nextNode != null) while(nextNode.left != null) nextNode = nextNode.left; } // 返回Entry对象 final Entry<K,V> nextEntry() { checkIteratorState(); if(nextNode == null) throw new NoSuchElementException( "Iteration has no more elements"); lastReturned = nextNode; Entry<K,V> p; // ①右子树非空移到最左结点 if(nextNode.right != null) { nextNode = nextNode.right; while(nextNode.left != null) nextNode = nextNode.left; // ②在右子树为空时,使用父结点引用在树中向上移动,直到查找到一个左子结点. // 这个左子结点的父结点就是要访问的下一结点 }else { p = nextNode.parent; while(p != null && nextNode == p.right) { nextNode = p; p = p.parent; } nextNode = p; } return lastReturned; } public boolean hasNext() { return nextNode != null; } public void remove() { // check for a missing call to next() or previous() if (lastReturned == null) throw new IllegalStateException( "Iterator call to next() " + "required before calling remove()"); // make sure our state is good checkIteratorState(); // if lastReturned has two children, the replacement node // during deletion is nextNode. the value in nextNode // is copied to lastReturned. nextNode must be // lastReturned if (lastReturned.left != null && lastReturned.right != null) nextNode = lastReturned; removeNode(lastReturned); // list has been modified modCount++; expectedModCount = modCount; // we did a deletion. indicate this by setting lastReturned // to null and decrementing treeSize lastReturned = null; mapSize--; } public T next() { return null; } private void checkIteratorState() { if (expectedModCount != modCount) throw new ConcurrentModificationException( "Inconsistent iterator"); } } // 键跌代器 // next()方法返回键 private class KeyIterator extends MyIterator<K> { public K next() { return nextEntry().key; } } // next()方法返回Entry对象 private class EntryIterator extends MyIterator<Map.Entry<K, V>> { public Map.Entry<K, V> next() { return nextEntry(); } } /*===============================================================*/ /*=========================视图===================================*/ private Set<K> kSet = null; private Set<Map.Entry<K, V>> eSet = null; public Set<K> keySet() { // 匿名内部类 if(kSet == null) { kSet = new Set<K>() { public int size() { // 引用TreeMap的size()方法 return TreeMap.this.size(); } public boolean isEmpty() { return TreeMap.this.isEmpty(); } public void clear() { TreeMap.this.clear(); } public boolean contains(Object item) { return containsKey(item); } public Iterator<K> iterator() { return new KeyIterator(); } public boolean remove(Object item) { int oldSize = mapSize; TreeMap.this.remove(item); return mapSize != oldSize; } public Object[] toArray() { Object[] arr = new Object[size()]; Iterator<K> it = this.iterator(); for (int i = 0; i < arr.length; i++) { arr[i] = it.next(); } return arr; } public String toString() { int max = size() - 1; StringBuffer buf = new StringBuffer(); Iterator<K> it = iterator(); buf.append("["); for (int i = 0; i < mapSize; i++) { buf.append(it.next()); if(i < max) buf.append(", "); } buf.append("]"); return buf.toString(); } public boolean add(K item) { throw new UnsupportedOperationException(); } }; } return kSet; }//end keySet~ public Set<Map.Entry<K, V>> entrySet() { if(eSet == null) { eSet = new Set<Map.Entry<K, V>>() { public int size() { return TreeMap.this.size(); } public boolean isEmpty() { return TreeMap.this.isEmpty(); } public void clear() { TreeMap.this.clear(); } public boolean contains(Object item) { if(!(item instanceof Map.Entry)) return false; Entry<K, V> e = (Entry<K, V>) item; V value = e.getValue(); Entry<K, V> p = getEntry(e.getKey()); return p != null && p.getValue().equals(value); } public Iterator<MyInterface.Map.Entry<K, V>> iterator() { return new EntryIterator(); } public boolean remove(Object item) { if(!(item instanceof Map.Entry)) return false; Entry<K,V> entry = (Entry<K,V>)item; K key = entry.getKey(); return TreeMap.this.remove(key) != null; } public Object[] toArray() { Object[] arr = new Object[size()]; Iterator<Map.Entry<K, V>> it = this.iterator(); for(int i = 0; i < arr.length; i++) { arr[i] = it.next(); } return arr; } public String toString() { return TreeMap.this.toString(); } public boolean add(MyInterface.Map.Entry<K, V> obj) { throw new UnsupportedOperationException(); } }; } return eSet; }//end entrySet~ /*===============================================================*/ }//end TreeMap~
测试类Test
package Map; import MyTime24.Time24; import MyInterface.*; import MyInterface.Map.Entry; public class Test { public static void main(String[] args) { /* TreeMap<String, Integer> tm = new TreeMap<String, Integer>(); tm.put("V", new Integer(20)); tm.put("A", new Integer(200)); tm.put("C", new Integer(80)); tm.put("C", new Integer(80*2)); tm.put("G", new Integer(60)); tm.remove("G"); Set<String> s = tm.keySet(); s.remove("A"); System.out.println(s); // [C, V] Iterator<String> iter = s.iterator(); String str = ""; while(iter.hasNext()) { str = iter.next(); System.out.print(str + "=" + tm.get(str) + " "); // C=160 V=20 } System.out.println('\n' + "size=" + s.size()); // 2 System.out.println(tm); Set<Map.Entry<String,Integer>> eSet = tm.entrySet(); Object[] obj = eSet.toArray(); for (int i = 0; i < obj.length; i++) { System.out.println(obj[i]); // 调用了Entry类的toString()方法 System.out.println(eSet.contains(obj[i])); } */ // Test entrySet() TreeMap<String, Time24> tm = new TreeMap<String, Time24>(); tm.put("Session 1", new Time24(9, 30)); tm.put("Session 2", new Time24(14, 00)); tm.put("Lunch", new Time24(12, 0)); tm.put("Dinner", new Time24(17, 30)); Set<Map.Entry<String, Time24>> e = tm.entrySet(); Iterator<Map.Entry<String, Time24>> it1 = e.iterator(); Iterator<Map.Entry<String, Time24>> it2 = e.iterator(); setTime(it1); System.out.println("======Session starting time======"); Start(it2); } private static void setTime(Iterator<Map.Entry<String, Time24>> it) { while(it.hasNext()) { Map.Entry<String, Time24> me = it.next(); Time24 t = me.getValue(); t.addTime(30); me.setValue(t); System.out.println(me.getKey() + " " + me.getValue()); } } private static void Start(Iterator<Map.Entry<String, Time24>> it) { while(it.hasNext()) { Map.Entry<String, Time24> me = it.next(); String s = me.getKey(); if(s.indexOf("Session") > -1) System.out.println(s + " starting time " + me.getValue()); } } }
辅助测试类Time24
package MyTime24; import java.text.DecimalFormat; import java.util.StringTokenizer; public class Time24 { private int hour; // 0 to 23 private int minute; // 0 to 59 private void normalizeTime() { int extraHours = minute / 60; // set minute in range 0 to 59 minute %= 60; // updata hour. set in range 0 to 23 hour = (hour + extraHours) % 24; } public Time24() { this(0, 0); } public Time24(int hour, int minute) { setTime(hour, minute); } public void setTime(int hour, int minute) { if (hour < 0 || minute < 0) throw new IllegalArgumentException( "parameters must be positive integers"); this.hour = hour; this.minute = minute; this.normalizeTime(); } public void addTime(int m) { if (m < 0) throw new IllegalArgumentException( "argument must be positive integers"); minute += m; this.normalizeTime(); } public Time24 interval(Time24 t) { // convert current time and time t to minutes int currTime = hour * 60 + minute; int tTime = t.hour * 60 + t.minute; // if t is earlier than the current time, add 24 hours to // indicate that t is time in the next day if (tTime < currTime) tTime += 24 * 60; // return a reference to a new Time24 object return new Time24(0, tTime - currTime); } public static Time24 parseTime(String s) { StringTokenizer stok = new StringTokenizer(s, " :"); String timePeriod = null; int hour, minute; hour = Integer.parseInt(stok.nextToken()); minute = Integer.parseInt(stok.nextToken()); return new Time24(hour, minute); } public int getHour() { return hour; } public int getMinute() { return minute; } public String toString() { DecimalFormat df = new DecimalFormat("00"); return new String(hour + ":" + df.format(minute)); } }
发表评论
-
优先队列的实现
2008-05-11 05:00 938package Heap; import MyInter ... -
堆操作
2008-05-11 02:06 947Comparator接口 package MyInterfac ... -
HashSet 类的实现
2008-04-28 16:03 1162package Hash; import MyInter ... -
HashMap类的实现
2008-04-28 12:20 1507package Hash; import java.ut ... -
Hash类的实现
2008-04-27 15:10 792package Hash; import java.util ... -
散列表的设计-->线性探查法
2008-04-24 09:07 1890性能分析: 散列表中条目数的比例较小时,使用线性探查法的效率较 ... -
java集合操作
2008-04-23 23:26 2993package Sets; import java.util ... -
二叉排序树的实现
2008-04-20 01:46 1640最适合用STree排序的是不可变类,不可变类的主要特征是它的对 ... -
InorderIterator类的实现
2008-04-07 08:41 931接口的定义: public interface MyItera ... -
BinaryTree遍历练习::表达式树
2008-04-05 14:35 1757package ExpressionTree; import ... -
二叉树遍历
2008-03-31 01:48 1056二叉树的高度 图(1) /**用后根遍历求二叉树的高度*/ ... -
有界队列
2008-03-26 00:14 972package Queue; import java.uti ... -
Stack练习:: 中缀-后缀表达式
2008-03-21 17:18 1745package Stack.Calculate; imp ... -
链式队列的实现
2008-03-21 17:05 1312package Queue; import java.u ... -
Stack练习:: 十进制正整数转化成二进制
2008-03-17 16:09 1243include "stdio.h" in ... -
顺序栈的实现
2008-03-14 00:16 1054package Stack; /** * 顺序栈的实现 ... -
数据结构 Java循环双向链表
2008-03-08 17:33 3108■ 构造函数 每个构造函数都通过 this 来初始化链接域 p ... -
我的Java单链表练习
2008-03-06 19:14 2997package LinkedList; /** * ... -
我的ArrayList实现
2008-03-04 21:26 1345package ArrayList; /** * < ... -
[转]数据结构 用Java实现单链表
2007-11-28 12:56 17162007-08-24 页面自动刷 ...
相关推荐
自然语言理解 关于词频统计的代码 利用treemap来完成
表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法4.3.5 平均情况分析4.4 AVL树4.4.1 单旋转4.4.2 双旋转4.5 伸展树4.5.1 一个简单的想法...
4.5.1 一个简单的想法(不能直接使用) 4.5.2 展开 4.6 树的遍历 4.7 b树 4.8 标准库中的集合与映射 4.8.1 关于set接口 4.8.2 关于map接口 4.8.3 treeset类和treemap类的实现 4.8.4 使用多个映射...
4.5.1 一个简单的想法(不能直接使用) 4.5.2 展开 4.6 树的遍历 4.7 b树 4.8 标准库中的集合与映射 4.8.1 关于set接口 4.8.2 关于map接口 4.8.3 treeset类和treemap类的实现 4.8.4 使用多个映射...
表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法4.3.5 平均情况分析4.4 AVL树4.4.1 单旋转4.4.2 双旋转4.5 伸展树4.5.1 一个简单的想法...
4.8.3 TreeSet类和TreeMap类的实现 4.8.4 使用多个映射的例 小结 练习 参考文献 第5章 散列 5.1 一般想法 5.2 散列函数 5.3 分离链接法 5.4 不用链表的散列表 5.4.1 线性探测法 5.4.2 平方探测法 5.4.3 双散列 5.5 ...
表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法4.3.5 平均情况分析4.4 AVL树4.4.1 单旋转4.4.2 双旋转4.5 伸展树4.5.1 一个简单的想法...
3.1.3 TreeMap和TreeSet 3.2 Map和List 3.2.1 Map的values()方法 3.2.2 Map和List的关系 3.3 ArrayList和LinkedList 3.3.1 Vector和ArrayList的区别 3.3.2 ArrayList和LinkedList的实现差异 3.3.3 ...