تنفيذ LinkedSet Java
-
25-09-2019 - |
سؤال
لقد طُلب منا تنفيذ مجموعة مرتبطة في Java. فيما يلي محاولتي ، تحتوي على جميع الأساليب التي يُطلب منا كتابتها ، لكن الطريقة تزيل مكالمات استثناء مؤشر فارغ دون فشل. جرب كما قد لا يمكنني معرفة ذلك ، أي مساعدة موضع تقدير كبير.
import java.util.*;
class LinkedSet<T> {
private static class Node<T> {
private T item;
private Node<T> next;
Node(T item, Node<T> next) {
this.item = item;
this.next = next;
}
}
private Node<T> head = null;
private int numItems = 0;
int size() {
return (numItems);
}
public boolean add(T t) {
if(contains(t)) return false;
Node<T> newNode = new Node(t, null); //new node to be added
if(numItems==0) {
head = newNode;
numItems++;
return true;
}
Node<T> temp = head;
while(temp.next != null) temp = temp.next;
temp.next = newNode;
numItems++;
return true;
}
public boolean remove(T t) {
if(numItems == 0) return false; //check for empty set
//was tempted to use contains here but would have made it N^2 I think
Node<T> p = head; //t if present
Node<T> pPrev = null; //previous node to p
while(p!=null && !equals(t, p.item)) {
pPrev = p;
p = p.next;
}
//t is present if node p!= null , node p != null ==> t in node p
if(p==null) return false;
else {
pPrev.next = p.next; //null pointer
numItems--;
return true;
}
}
public boolean contains(T t) {
Node<T> temp = head;
for(int i = 0; i < numItems; i++) {
if(equals(temp.item, t)) return true;
temp = temp.next;
}
return false;
}
private boolean equals(T t1, T t2) { //t1, t2 may be null
if(t1!=null) return t1.equals(t2); //learn this
else return t2 == null; //learn this
}
public static void main(String[] args) {
LinkedSet<Integer> test = new LinkedSet<Integer>();
test.add(1);
test.add(2);
test.add(3);
for(int i = 0; i < 10; i ++) {
System.out.println("Testing i = " + i + " - " + test.contains(i));
}
System.out.println(); System.out.println(); System.out.println();
System.out.println(test.remove(1));
}
}
المحلول
النقطة الواضحة هي أن العنصر الأول في القائمة ليس لديه عنصر سابق. (ستضيف بعض تطبيقات القائمة المرتبطة رابطًا وهمية للتعامل مع هذا بشكل أكثر نظافة.)
نصائح أخرى
انظر إلى هذا الجزء من الكود:
Node<T> p = head; //t if present
Node<T> pPrev = null; //previous node to p
while(p!=null && !equals(t, p.item)) {
pPrev = p;
p = p.next;
}
لو equals(t, head.item)
, ، من ثم pPrev == null
عندما تغادر حلقة بينما ستحصل على استثناء مؤشر فارغ لاحقًا.
لا تنتمي إلى StackOverflow