Pseudocode Rekursiv Ringliste etwas Löschen

Bitte aktiviere JavaScript!
Guten Tag zusammen,

da ich nicht wusste wohin mit diesem Thema schreibe ich es in die Plauderecke :D

Aufgabenstellung:
Code:
Gegeben sei eine doppelt verkettete Ringliste bestehend aus

Elementen: Element[integer: Schlüssel, pointer: Next, pointer: Previous] und
dem Zeiger auf das erste Element pointer: Liste.

Das erste Element der Ringliste steht an Stelle n=1.

Vervollständigen Sie den folgenden rekursiven Algorithmus in Pseudocode-Notation, der das n-
te Element (n eine ganze positive Zahl!) löscht.
Bereits initialisierte Variablen sind „n „und „Liste“

START
If (n == 1) && (   ) then

else if ( n>1) && ( ) then
löscheElement( , , )
END

löscheElement ( , , ){ }
Das einzige was mir eingefallen ist bei dieser Aufgabe ist:
Code:
start
if(n == 1 && Liste != null) then {
Liste.next.previous = Liste.previous
Liste = Liste.next
}
else if ( n>1) && ( ) then
löscheElement( , , Liste )
end
Wieso der erste Wert aus der Ringliste auch aus der Rekursion muss verstehe ich auch nicht.

Wie die Rekursion dann Funktionieren soll weiß ich auch nicht da ich nicht mal die Parameter zusammen bekomme :(
Code:
löscheElement ( ??? ,??? ,??? )

Kann mir hierbei jemand Helfen?

LG
 
Visualisieren hilft fast immer bei solchen Dingen.

Beim Löschen sind ja zwei Dinge erforderlich:

a) finde das n-te Element in der Liste
b) entferne das gefundene Element aus der Liste

Zu a) stell Dir mal ein Glücksrad vor, das irgendwo diesen Plöppel hat, der das aktuelle Element anzeigt. Wir beginnen die Suche beim ersten Element, d. h. das erste Element der Liste steht unter dem Plöppel.

Außerdem haben wir ein n gegeben. Gilt n == 1, befindet sich das gesuchte Element unter dem Plöppel und die Suche ist beendet. Ist n > 1, dann können wir, um das n um eins zu verringern, das Rad um ein Element weiterdrehen...

Zu b) Wie können solche Listen denn aussehen?

1. Bild: leere Liste

Code:
Liste -> null
2. Bild: Liste mit einem Eintrag
Code:
+------------+
|            |
+->[Elem1] <-+
      ^
      |
    Liste
3. Bild: Liste mit vielen Einträgen
Code:
+-----------------------------------------------+
|                                               |
+->[Elem1] <--> [Elem2] <--> ... <--> [ElemN] <-+
      ^
      |
    Liste
Wieso der erste Wert aus der Ringliste auch aus der Rekursion muss verstehe ich auch nicht.
In den Bildern sieht man sehr deutlich: wenn man das erste Element löscht, kann Liste nicht mehr auf dieses Element zeigen. D. h. beim Löschen des ersten Elements (und nur bei diesem) verändert sich der Zeiger Liste.

Die Bilder zeigen auch gleich einen Sonderfall: wenn man aus der Liste im 2. Bild das erste und einzige Element löscht, muss im Ergebnis das 1. Bild herauskommen. Da helfen Dir Liste.next.previous = Liste.previous und Liste = Liste.next allerdings wenig, denn dadurch verändert sich genau nichts. Außerdem: was ist mit Liste.previous.next?
 
Erstmal wieder super Danke für die Ausführliche Antwort von dir @mihe7. Wüsste auch gerne mal wie du diese Zeichnungen bastelst GEILOOO :)

Irgendwie verstehe ich leider das ganze immer noch nicht so ganz. Ich muss doch die Werte vergleichen! Was bringt mir da immer das nte Element? oder soll ich das nte Element löschen? Doch das würde keinen Sinn machen dann bräuchte ich keinen Schlüssel. Meiner Meinung nach muss ich erst einmal den Schlüssel suchen!

Dann würde die erste Abfrage bei mir ca. so aussehen:
Code:
START
if(n == 1 && Liste.key == key && Liste.next != Liste)
 
Ich muss doch die Werte vergleichen! Was bringt mir da immer das nte Element? oder soll ich das nte Element löschen? Doch das würde keinen Sinn machen dann bräuchte ich keinen Schlüssel. Meiner Meinung nach muss ich erst einmal den Schlüssel suchen!
Aus der Aufgabenstellung: "Vervollständigen Sie den folgenden rekursiven Algorithmus in Pseudocode-Notation, der das n-te Element (n eine ganze positive Zahl!) löscht."
Du sollst also einfach das n-te Element in der Liste löschen. Wieso willst du hier irgendeinen "Schlüssel" holen oder irgendwie einen Schlüssel vergleichen? Du hast eine doppelt verkettete Liste und das erste Element in der Liste und sollst ausgehend von diesem ersten Element der Liste nun das n-te Element löschen, wobei n=1 das aktuelle/erste Element ist.
Mit was für einem "key" willst du denn hier vergleichen? Die Aufgabenstellung beschreibt doch ganz klar und ganz eindeutig, welche Eingabeparameter du überhaupt hast. Und ein zu suchender/löschender Key ist da nicht drin.
 
Würde eine Klasse so aussehen:
Code:
Liste {
Element Wert
Liste next
Liste previous
}
Denn ich verstehe das ganze Konzept überhaupt nicht!
Ich würde eine Klasse Schreiben Liste die einen Anfang und ein Ende hat so:
Code:
public class List {
Node anfang;
Node ende;

}
und in meiner Node Klasse geht man dann über die next und previous Zeiger hin und her!
Wieso soll alles über die Liste Klasse mit next und previous gehen? Finde das irgendwie schwieriger.

Leider fällt mir nichts zu dem Pseudo-Misst da oben ein!
Trotzdem danke :)

LG

Nicht von mir hab es geschickt bekommen verstehen tu ich es auch nicht wirklich!
Code:
START
if(n==1 && Liste.Next != Liste) then
Liste.Next = Liste.Next.Next
Liste.Next.Previous = Liste
else if (n>1 && Liste.Next!=Liste) then
löscheElement/Liste.Next, n-1, Liste)
END

löscheElement(Element, n, Start)
START
if(n==1) then
Element.Next=Element.Next.Next
Element.Next.Previous=Element
else if(n>1) then löscheElement(Element.Next, n-1, Start)
END
 
Zuletzt bearbeitet:
Wieso soll alles über die Liste Klasse mit next und previous gehen? Finde das irgendwie schwieriger.
Wieso denn nicht? Wieso willst du künstlich eine `Liste` Klasse erzeugen (zusätzlich zu der `Node` Klasse)? Effektiv unterscheidet sich ein `Node` in der Liste von der `Liste` selbst ja überhaupt nicht. Zwei Klassen zu haben wäre hier komplizierter. Du hast halt einfach eine einzige Klasse `Liste` (oder nenne sie `Node` - egal) und die hat eine `previous` und eine `next` Referenz auf denselben Typ. Das einzige Problem bei einer einzigen Klasse ist das Löschen aus einer Liste mit nur einem Element und das Hinzufügen zu einer leeren Liste, da der Client/Nutzer hierfür seine Referenz auf das Listenelement anpassen muss.
 
Uff also das ganze macht mich hier echt noch total verrückt :(
Mein erstes Liste Element Zeigt auf das erste Element in der Liste oder?

Ich hätte jetzt mal bei n==1 so gemacht:

Code:
if (n==1 && Liste != null) then {
Liste = Liste.next //Wenn Liste das erste Element ist wäre .next das zweite Element
Liste.previous = Liste.previous.previous //Da ich mich auf dem zweiten Element befinde möchte ich nun am ersten vorbei und ans ende greifen
Liste.previous.previous.next = Liste //Der next Zeiger vom Letzten Element muss auf die Liste zeigen damit beide Zeiger vom ersten Element entfernt wurden und somit das Element verschwindet
}
Wenn das nun auch nicht passt lasse ich es echt sein. Konnte wieder nicht Schlafen wegen dem Scheiß! :D

LG
 
Konnte wieder nicht Schlafen wegen dem Scheiß! :D
Sorry, das ist meine Schuld: ich habe anfangs nicht richtig gelesen. In Deinem Fall wir die leere Liste nicht durch einen null-Zeiger sondern durch ein Dummy-Element (das immer existiert, sozusagen an Position n==0) dargestellt. Vielleicht verstehst Du nun den Algorithmus, den Du geschickt bekommen hast. Wenn Du noch Java-Code brauchst, sag Bescheid, dann poste ich einen.
 
Ja würde mich über Java Code freuen :)
doch ich glaube ich habe es verstanden.
Vielleicht auch nicht "ich glaube" :D nicht ich weiß oder kann sagen!
Deswegen wäre super Lieb wenn du mir etwas Code schicken könntest?

LG
 
Java:
import java.util.StringJoiner;

public class RingList {
    static class Node {
        Node next;
        Node prev;
        int value;

        public String toString() {
            return "[" + prev.value + " <- " + value + " -> " + next.value + "]";
        }
    }

    private final Node list;
    
    public RingList() {
        list = new Node();
        list.next = list;
        list.prev = list;
        list.value = -1;
    }

    public void insert(int value) {
        // fuegt das Element ans "Ende" der Liste ein.
        // D. h. als Vorgaenger des Dummy-Listenelements

        Node newNode = new Node();
        newNode.value = value;
        newNode.next = list;
        newNode.prev = list.prev;
        list.prev.next = newNode;      

        if (list.next == list) { // falls Liste leer
            list.next = newNode; // muss der Nachfolger von list angepasst werden
        }
        // in jedem Fall muss der Vorgaenger angepasst werden
        list.prev = newNode;
    }

    public void delete(int n) {
        if (n == 1 && list.next != list) { // das erste Element einer nicht-leeren Liste soll entfernt werden
            list.next = list.next.next;
            list.next.prev = list;
        } else if (n > 1 && list.next != list) { // n-te Element einer nicht-leerne Liste soll entfernt werden
            delete(n-1, list.next, list);
        }
    }

    private void delete(int n, Node current, Node first) {
        if (n == 1) { // zu entfernendes Element wurde erreicht
            current.next = current.next.next;
            current.next.prev = current;
        } else if (n > 1) {
            delete(n-1, current.next, first);
        }
    }

    public boolean validate() {
        Node prev = list;
        Node current = list.next;        
        while (current != list) {
            if (current.next.prev != current)
                return false;
            prev = current;
            current = current.next;
        }
        return current.prev == prev;
    }

    public void assertValid() {
        if (!validate()) { 
            StringJoiner j = new StringJoiner(", ");
            j.add(list.toString());
            j.add(toString());
            throw new IllegalStateException(j.toString()); 
        }
    }

    public String toString() {
        Node current = list.next;
        StringJoiner j = new StringJoiner(", ");
        while (current != list) {
            j.add(current.toString());
            current = current.next;
        }
        return j.toString();
    }

    public static void main(String[] args) {
        RingList list = new RingList();
        list.assertValid();
        int[] values = {10, 20, 30, 40};
        for (int value : values) {
            list.insert(value);
            list.assertValid();
            System.out.println("Liste: " + list.toString());
        }

        int[] toDelete = {4, 2, 1, 1};
        for (int pos : toDelete) {
            list.delete(pos);
            list.assertValid();
            System.out.println("Liste: " + list.toString());
        }
    }
}
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben