Singly Linked List: Einfügen von Elementen (insert)

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

Singly Linked List: Einfügen von Elementen (insert)

Beitrag von Dadung » 7. Mai 2017 13:29

Hallo,

ich habe mit dieser Aufgabe einige Probleme. Ich habe gesehen, dass andere ähnliche Probleme bei insert-First hatten, aber da gab e scheinbar auch noch keine passende Lösung.

Zuerst mein Code:

Code: Alles auswählen

{
    if (el == null) {
        return false;
    }
    if (contains(el)) {
        return false;
    }
    if (idx < 0) {
        return false;
    }
    ListElement<T> ell = new ListElement<T>();
    ell = el;
    int i = 1;
    while (ell.hasNext()) {
        if (ell.next().equals(el)) {
            break;
        }
        i++;
        ell = ell.next();
    }
    if (isEmpty()) {
        setFirst(el);
        setLast(ell);
        setSize(i);
        return true;
    }
    if (idx == 0) {
        return insertFirst(el);
    }
    if (idx >= size()) {
        return insertLast(el);
    }
    ListElement<T> pos = new ListElement<T>();
    pos = getFirst();
    for (int j = 0; j < idx - 1; j++) {
        pos = pos.next();
    }
    ell.setNext(pos.next());
    pos.setNext(el);
    setSize(size() + i);
    return true;
}
Dabei treten 5 Fehler auf, bei denen es einen Timeout gibt, sowie ein Fehler bezüglich des mehrfachen Einfügens des selben Elements:
Antwort des Servers
Junitreport

Time – 603

Testcount – 29

Failurecount – 6

Ignorerecount – 0

Failurereport

Testheadder – basic_26_Insertion_with_loop_of_a_non_null_non_single_element_at_the_middle_of_the_list(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – test timed out after 100 milliseconds

Trace

Failurereport

Testheadder – basic_19_Insertion_with_loop_of_a_non_null_non_single_element_at_the_end_of_the_list_with_single_element(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – test timed out after 100 milliseconds

Trace

Failurereport

Testheadder – basic_09_Insertion_with_loop_of_a_non_null_non_single_element_at_the_beginning_of_the_list_with_single_element(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – test timed out after 100 milliseconds

Trace

Failurereport

Testheadder – basic_25_Insertion_with_repetitions_of_a_non_null_non_single_element_at_non_edge_positions_of_the_non_empty_list(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – List before operation: (|el-8|el-9|el-10|) Expected list after operation: (|el-8|el-9|el-10|) Repeated insertion of the same element should not be successful

Trace

Failurereport

Testheadder – basic_20_Insertion_with_loop_of_a_non_null_non_single_element_at_the_end_of_the_list(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – test timed out after 100 milliseconds

Trace

Failurereport

Testheadder – basic_10_Insertion_with_loop_of_a_non_null_non_single_element_at_the_beginning_of_the_list(singly_linked_list.insert.test_insert.LinkedList_insert)

Message – test timed out after 100 milliseconds

Trace
Das Problem vermute ich, wie auch andere schon in der Funktion contains(), da ich mit dieser eigentlich das einfügen von doppelten Elementen verhindern sollte.


Also ich habe da jetzt seit einiger Zeit dran herum gearbeitet, aber ich komme schlichtweg nicht weiter und wäre für jede Hilfe dankbar.


Vielen Dank für eure hilfe

Julian Prommer
Moderator
Moderator
Beiträge: 167
Registriert: 17. Apr 2013 15:48

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von Julian Prommer » 7. Mai 2017 19:48

habe dem Ersteller bescheid gesagt sich darum zu kümmern
AuD Orga

VQumDH
Neuling
Neuling
Beiträge: 5
Registriert: 30. Okt 2015 12:01

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von VQumDH » 7. Mai 2017 21:39

Guten Abend!

1) Darf idx unendlich groß sein?

2) Warum erstellst du eine neue Instanz von ListElement<T> ell = new ListElement<T>();?

3) "Diese Methode fügt ein angegebenes Element und dessen nachfolgende Elemente am Index idx..." == ein Element kann auch nicht aleine sein, also durch Next() auf nachfolgendes Element zeigen. Und potenziell jede nachfolgends Element kann wegen wiederholung nich zulässig sein.

Bei weiteren Fragen helfe ich dir gerne 8)

Gruftgrabbler
Neuling
Neuling
Beiträge: 5
Registriert: 16. Mai 2017 10:44

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von Gruftgrabbler » 16. Mai 2017 13:38

Kurze Frage. Kann man den nicht eigentlich einfach auf das letzte Element aus el zugreifen und über setNext dem el dann das erste Element aus der vorherigen Liste zuweisen? Man hätte dann doch eine Ergebnisliste die genau den Anforderungen aus der Aufgabe entspricht oder sehe ich das falsch?

Gruß
David

VQumDH
Neuling
Neuling
Beiträge: 5
Registriert: 30. Okt 2015 12:01

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von VQumDH » 18. Mai 2017 16:30

Wenn ein Element eingefügt wird, dann sollen entsprechend "size", "first" und "last" aktualisiert werden.
Also nur ein "next" auf ein Element zu setzen reicht nicht.

Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von Janosch » 8. Jun 2017 11:42

Hallo,

weiß vielleicht auch jemand wie man Zyklen in der Eingabeliste abfängt? contains() ist eine nicht erlaubte Methode.

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: Singly Linked List: Einfügen von Elementen (insert)

Beitrag von goerlibe » 15. Jun 2017 20:12

Janosch hat geschrieben:
8. Jun 2017 11:42
Hallo,

weiß vielleicht auch jemand wie man Zyklen in der Eingabeliste abfängt? contains() ist eine nicht erlaubte Methode.
du überprüfst einfach die Element der Eingabeliste: wenn irgendwann der next() pointer der selbe ist, wie der vom ersten ListenElement, dann hast du einen Zyklus.

Code: Alles auswählen

for(ListElement t = el.next(); t != null; t = t.next()) {
   if(el.next() == t.next()) return false;
   // hier könnte man natürlich noch weitere Operationen machen, zB ListenGröße ermitteln, letztes Element der Liste ermitteln, ...
}

Antworten

Zurück zu „AuD: Programmieraufgaben“