Guten Tag,
ich besuche zur Zeit einen Java Grundlagenkurs und habe die Aufgabe bekommen, eine SkipList in Java zu implementieren. Ich weiß nun was eine SkipList ist und wozu sie gut ist, allerdings verstehe ich nicht, wie diese Funktioniert bzw. wie ich bei der Implementierung herangehen sol.
Die Aufgabe ist im Anhang. Dazu haben wir folgenden Code bekommen:
Meine Frage nun:
- Was bedeutet der Satz "Die Indexliste soll hierbei eine fixe Größe von vier Einträgen haben. Der in diesen Feldern gehaltene Index soll sich gleichmäßig über die Anzahl der Einträge in der Primärliste verteilen (d.h. Anzahl der nicht indexierten Elemente in den durch die sekundäre Liste definierten Intervallen weicht nie um mehr als 1 ab)." ?
- Wie würde die SkipListe genau arbeiten wenn ich z.B. anfange, die Zahlen einzufügen? Ich kann mir das gar nicht vorstellen, wie ich das unterscheiden kann, dass die Zahlen in die BaseList oder in die IndexList eingefügt werden. Also ich bin völlig planlos, wie ich an diese Aufgabe herangehen soll. Ich habe viel im Internet recherchiert, aber nichts nützliches gefunden.
Vielen Dank für Ansätze!
ich besuche zur Zeit einen Java Grundlagenkurs und habe die Aufgabe bekommen, eine SkipList in Java zu implementieren. Ich weiß nun was eine SkipList ist und wozu sie gut ist, allerdings verstehe ich nicht, wie diese Funktioniert bzw. wie ich bei der Implementierung herangehen sol.
Die Aufgabe ist im Anhang. Dazu haben wir folgenden Code bekommen:
Java:
package de.tuberlin.ise.prog1;
import java.util.Collection;
import java.util.Iterator;
public class SkipList implements Collection<Integer> {
/**
* Returns the value at the specified position
*
* @param index
* @return
*/
public Integer get(int index) {
return null;
}
/**
* Inserts a value into the SkipList.
*
* @param value
* @return
*/
@Override
public boolean add(Integer e) {
// TODO Auto-generated method stub
return false;
}
/**
* Checks, whether a number is contained in the list.
* @param value
* @return boolean value whether number is contained in list
*/
public boolean contains(int value) {
return false;
}
/**
* removes all elements form the list
*/
@Override
public void clear() {
// TODO Auto-generated method stub
}
/**
* @return the size of the list
*/
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
//do not change the following methods
@Override
public boolean isEmpty() {
return size() <= 0;
}
@Override
public boolean contains(Object o) {
try {
Integer casted = (Integer) o;
return contains(casted) ;
} catch (ClassCastException e) {
return false;
}
}
@Override
@Deprecated
public boolean remove(Object o) {
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
for(Object o : c) {
if(!contains(o)) {
return false;
}
}
return true;
}
@Override
public boolean addAll(Collection<? extends Integer> c) {
for(Integer t:c) {
add(t);
}
return true;
}
@Override
@Deprecated
public boolean removeAll(Collection<?> c) {
return false;
}
@Override
@Deprecated
public boolean retainAll(Collection<?> c) {
return false;
}
@Override
public Iterator<Integer> iterator() {
//really slow way to implement this but should be some what understandable
return new Iterator<Integer>() {
int index = 0;
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return index < size();
}
@Override
public Integer next() {
return get(index++);
}
};
}
@Override
public Object[] toArray() {
Object[] obj = new Object[size()];
for (int i = 0; i < size(); i++) {
obj[i] = get(i);
}
return obj;
}
@SuppressWarnings("unchecked")
@Override
public <X> X[] toArray(X[] a) {
for (int i = 0; i < size(); i++) {
a[i] = (X) get(i);
}
return a;
}
}
Java:
package de.tuberlin.ise.prog1;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> daten = Arrays.asList(1,3,6,7,12,14,21,34,36,37);
SkipList list = new SkipList();
list.addAll(daten);
System.out.printf("test get(5) should be:14 is:%d\n",list.get(5));
System.out.printf("test contains(7) should be:true is:%b\n",list.contains(7));
System.out.printf("test contains(37) should be:true is:%b\n",list.contains(37));
System.out.printf("test contains(-1) should be:false is:%b\n",list.contains(-1));
System.out.printf("test toString() should be:\n"
+ "head -> 1 -> 7 -> 21 -> 36 -> null\r\n" +
"head -> 1 -> 3 -> 6 -> 7 -> 12 -> 14 -> 21 -> 34 -> 36 -> 37 -> null\r\n" +
"\nis:\n%s\n",list);
}
}Meine Frage nun:
- Was bedeutet der Satz "Die Indexliste soll hierbei eine fixe Größe von vier Einträgen haben. Der in diesen Feldern gehaltene Index soll sich gleichmäßig über die Anzahl der Einträge in der Primärliste verteilen (d.h. Anzahl der nicht indexierten Elemente in den durch die sekundäre Liste definierten Intervallen weicht nie um mehr als 1 ab)." ?
- Wie würde die SkipListe genau arbeiten wenn ich z.B. anfange, die Zahlen einzufügen? Ich kann mir das gar nicht vorstellen, wie ich das unterscheiden kann, dass die Zahlen in die BaseList oder in die IndexList eingefügt werden. Also ich bin völlig planlos, wie ich an diese Aufgabe herangehen soll. Ich habe viel im Internet recherchiert, aber nichts nützliches gefunden.
Vielen Dank für Ansätze!
)
