Hallo,
Leider komme ich nicht weiter und kann mir garnicht vorstellen, wie ich vorzugehen habe oder was ich als erstes tuhen muss. Ich freue mich wirklich auf jede Antwort und vielen Dank im vorraus.
FRAGESTELLUNG
Implementieren Sie die SkipList-Datenstruktur für Integer-Daten. Die Indexliste soll hierbei ebenfalls eine fixe Größe von vier Feldern 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; die Indexliste muss sich dynamisch anpassen). Weiter soll die Skiplist folgende Methoden anbieten: • add(value) – Fügt ein int in die Skiplist ein und updatet die Indexliste falls notwendig. Die Methode soll immer true zurückgeben, wenn das Einfügen erfolgreich war. • get(index) – Gibt den Wert an der durch index definierten Position zurück oder null, wenn index nicht vorhanden ist. • contains(value) – Gibt einen boolean-Wert zurück, welcher anzeigt ob das übergebene Element in der Primärliste enthalten ist. • size() – Gibt einen int-Wert zurück, welcher die Anzahl der Elemente in der Primärliste beschreibt. • clear() – Entfernt alle Einträge aus der Liste, so dass die Liste wie neu verwendet werden kann • toString() – Gibt eine Stringdarstellung der Listenelemente der Sekundär- und Primärliste zurück
konkrete Frage ; wie kann ich es implementieren das die Indexliste eine fixe Größe von vier Feldern hat.
was müsste ich im Code ergänzen damit so eine index Liste realisiert wird.
CODE
liebe grüße
louis
Leider komme ich nicht weiter und kann mir garnicht vorstellen, wie ich vorzugehen habe oder was ich als erstes tuhen muss. Ich freue mich wirklich auf jede Antwort und vielen Dank im vorraus.
FRAGESTELLUNG
Implementieren Sie die SkipList-Datenstruktur für Integer-Daten. Die Indexliste soll hierbei ebenfalls eine fixe Größe von vier Feldern 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; die Indexliste muss sich dynamisch anpassen). Weiter soll die Skiplist folgende Methoden anbieten: • add(value) – Fügt ein int in die Skiplist ein und updatet die Indexliste falls notwendig. Die Methode soll immer true zurückgeben, wenn das Einfügen erfolgreich war. • get(index) – Gibt den Wert an der durch index definierten Position zurück oder null, wenn index nicht vorhanden ist. • contains(value) – Gibt einen boolean-Wert zurück, welcher anzeigt ob das übergebene Element in der Primärliste enthalten ist. • size() – Gibt einen int-Wert zurück, welcher die Anzahl der Elemente in der Primärliste beschreibt. • clear() – Entfernt alle Einträge aus der Liste, so dass die Liste wie neu verwendet werden kann • toString() – Gibt eine Stringdarstellung der Listenelemente der Sekundär- und Primärliste zurück
konkrete Frage ; wie kann ich es implementieren das die Indexliste eine fixe Größe von vier Feldern hat.
was müsste ich im Code ergänzen damit so eine index Liste realisiert wird.
CODE
Code:
package main;
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;
}
}
package main;
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);
}
}liebe grüße
louis
