0001 /* 0002 * 基于无序列表实现的优先队列 0003 */ 0004 0005 package dsa; 0006 0007 public class PQueue_UnsortedList implements PQueue { 0008 private List L; 0009 private Comparator C; 0010 0011 //构造方法(使用默认比较器) 0012 public PQueue_UnsortedList() 0013 { this(new ComparatorDefault(), null); } 0014 0015 //构造方法(使用指定比较器) 0016 public PQueue_UnsortedList(Comparator c) 0017 { this(c, null); } 0018 0019 //构造方法(使用指定初始元素) 0020 public PQueue_UnsortedList(Sequence s) 0021 { this(new ComparatorDefault(), s); } 0022 0023 //构造方法(使用指定比较器和初始元素) 0024 public PQueue_UnsortedList(Comparator c, Sequence s) { 0025 L = new List_DLNode(); 0026 C = c; 0027 if (null != s) 0028 while (!s.isEmpty()) { 0029 Entry e = (Entry)s.removeFirst(); 0030 insert(e.getKey(), e.getValue()); 0031 } 0032 } 0033 0034 //统计优先队列的规模 0035 public int getSize() 0036 { return L.getSize(); } 0037 0038 //判断优先队列是否为空 0039 public boolean isEmpty() 0040 { return L.isEmpty(); } 0041 0042 //若Q非空,则返回其中的最小条目(并不删除);否则,报错 0043 public Entry getMin() throws ExceptionPQueueEmpty { 0044 if (L.isEmpty()) 0045 throw new ExceptionPQueueEmpty("意外:优先队列空"); 0046 Position minPos = L.first(); 0047 Position curPos = L.getNext(minPos); 0048 while (null != curPos)//依次检查所有位置,找出最小条目 0049 if (0 < C.compare(minPos.getElem(), curPos.getElem())) 0050 minPos = curPos; 0051 return (Entry) minPos.getElem(); 0052 } 0053 0054 //将对象obj与关键码k合成一个条目,将其插入Q中,并返回该条目 0055 public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid { 0056 Entry entry = new EntryDefault(key, obj);//创建一个新条目 0057 L.insertLast(entry);//接至列表末尾 0058 return(entry); 0059 } 0060 0061 //若Q非空,则从其中摘除关键码最小的条目,并返回该条目;否则,报错 0062 public Entry delMin() throws ExceptionPQueueEmpty { 0063 if (L.isEmpty()) 0064 throw new ExceptionPQueueEmpty("意外:优先队列空"); 0065 Position minPos = L.first(); 0066 Iterator it = L.positions(); 0067 while (it.hasNext()) {//依次检查所有位置,找出最小条目 0068 Position curPos = (Position) (it.getNext()); 0069 // System.out.println("\t" + ((Entry)(curPos.getElem())).getKey()); 0070 if (0 < C.compare( 0071 ((Entry)(minPos.getElem())).getKey(), 0072 ((Entry)(curPos.getElem())).getKey()) 0073 ) 0074 minPos = curPos; 0075 } 0076 return (Entry) L.remove(minPos); 0077 } 0078 }