SinglyList InsertFirst/Last Timeout

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!
Tim Rieber
Erstie
Erstie
Beiträge: 15
Registriert: 18. Apr 2017 17:42

SinglyList InsertFirst/Last Timeout

Beitrag von Tim Rieber » 21. Jun 2017 14:29

Ich habe ein Problem mit den oben genannten Methoden, bei denen bei mir jeweils 2 Tests wegen Timeouts fehlschlagen, Insertion_with_loop_of_a_non_null_non_single_element_in_the_list und Insertion_with_loop_of_a_non_null_non_single_element_in_the_list_with_single_element. Offensichtlich beachtet meine Lösung nicht, dass Eingaben von einer Liste mit Loop natürlich nicht akzeptiert werden sollen. Hier mein Code (von insertfirst, es unterscheiden sich eh nur die dritt- und viertletzte Zeile):

Code: Alles auswählen

{
    if(el==null) return false;
  
    boolean found = false;
    int length = 1;
    ListElement<T> last = el;
    
    while(found==false) {
        if(contains(last)) return false;
        if(last.hasNext()) {
            length++;
            last = last.next();
        } else found = true;
    }

    if(getFirst()==null) {
        setFirst(el);
        setLast(last);
        setSize(length);
        return true;
    }
    
    last.setNext(getFirst());
    setFirst(el);
    setSize(size()+length);
    return true;
}
Mir gelingt es aber nicht, eine Abfrage zu formulieren, die Eingaben mit Loops verwirft, zum Beispiel habe ich probiert:

Code: Alles auswählen

    ListElement a = el.next();
    while(true) {
        if(a==null) {
            break;
        } else if(a==el) {
            return false;
        } else {
            a = a.next();
        }
    }
Kann mir bitte hier jemand auf die Sprünge helfen, danke im Voraus!

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: SinglyList InsertFirst/Last Timeout

Beitrag von joshimoo » 21. Jun 2017 17:14

Hallo Tim,

habe mir das mal angeschaut und es ging bei der Aufgabe wohl eher darum Cycle Finding auf der neuen Eingabe Liste durch zu führen.
Die Beschreibung ist etwas unpräzise und auch das contains als Erlaubte Methode angegeben ist, etwas fragwürdig.
Da das selbst wenn es nicht um cycle finding ginge echt schlechter Stil wäre.

Zumindest wenn man sich die Test Listen anschaut:
- sieht man das Test9 und Test10 einen Cycle in der Eingabe Liste haben.
Welcher durch Cycle Finding gefunden und abgelehnt werden soll

- Alle anderen sind okay und es gibt auch nie ein Duplikat zwischen Eingabe und original Liste.

- Allerdings ist auch Test08 irgendwie komisch oder ich hab einen Fehler in meinem Code :oops:

Anbei mal eine Anleitung wie man die Tests als Nabla Benutzer debuggen kann ;)
Das solltet ihr allerdings auf keinen Fall bei den Testaten machen !!! :evil:
@Julian/Entwickler: Ich hoffe ich trete hier keinem auf den Schlips, falls euch das stört einfach Bescheid sagen oder den Post löschen :roll:

Code: Alles auswählen

{
    if(el == null) { return false; }
    ListElement<T> newHead = el;
    ListElement<T> oldHead = getFirst();
    ListElement<T> next = el;
    int size = size();
    
    // system does not know do while loop?
    for(boolean f = false; f; ) {}
    String s = "";
    
    
    // DEBUG only: evaluate existing list
    // old List before new List eval
    /*el = oldHead;
    s = s + "OLD: ";
    while(el != null) {
        s = s + el + " ";
        el = el.next();
    }
    new Long(s);//*/
    // END debug
    
    // find tail and count
    do {
        // check if element is already contained in linked list
        // I am not sure if this is what they want
        // I assume the original intention was to do cycle finding ala tortoise and hare?
        if (contains(el)) { return false; }
        el = next;
        size++;
        s = s + el + " ";
        
        // DEBUG:
        if(size > 20) { new Long(s + " CYCLE? "); }
        
    } while( (next = el.next()) != null );
    
    // DEBUG only: evaluate existing list
    // TEST08 is weird, since org is empty and new list should be correct
    // new List olnly: new Long(s);
    /*el = oldHead;
    s = s + "|| ";
    while(el != null) {
        s = s + el + " ";
        el = el.next();
    }
    new Long(s);//*/
    // END debug

    // merge lists
    if(oldHead == null) { setLast(el); }
    el.setNext(oldHead);
    setFirst(newHead);
    setSize(size);
    
    return true;
}

Tim Rieber
Erstie
Erstie
Beiträge: 15
Registriert: 18. Apr 2017 17:42

Re: SinglyList InsertFirst/Last Timeout

Beitrag von Tim Rieber » 22. Jun 2017 10:05

Wow tolle Antwort, danke; das hat mir weitergeholfen.

Antworten

Zurück zu „AuD: Programmieraufgaben“