Wer kennt sich mit Listen aus?

[johann2]

Hallo,

ich schreibe bald meine Informatik Klausur und konnte so bis jetzt fast alle Übungsblätter lösen, nur ein paar Aufgaben halten sich noch hartnäckig

Vielleicht kann sie ja jemand?

Aufgabe:

Eine verkettete Liste enthält einen Zyklus, wenn man beginnend von einem Knoten p, den next-Zeigern folgt und wieder beim Knoten p ankommt. Die Liste habe n Knoten, wobei n nicht bekannt ist.

a.

Beschreiben Sie einen Algorithmus mit der Zeitkomplexität O(n), welcher bestimmt ob eine verkettete Liste einen Zyklus enthält. Sie können O(n) extra Speicherplatz verwenden.

b.

Wiederholen Sie Aufgabe a). Benutzen Sie diesmal aber nur O(1) extra Speicherplatz. Lösungshinweis: Verwenden Sie zwei Iteratoren, die sich mit verschiedenen Geschwindigkeiten durch die Liste bewegen.

Aufgabe:

In einer einfach verketteten Liste haben Sie eine Referenz auf einen Knoten, welcher nicht der letzte Knoten der Liste ist. Beschreiben Sie einen O(1) Algorithmus der den Wert in diesem Knoten löscht und die Integrität der Liste bewahrt.

Ich bin für jeden Hinweis dankbar =)

[flashpixx]

Ich bin für jeden Hinweis dankbar =)

... und wir dafür, dass Du Deine Lösungsansätze postest

[lilith2k3]

Wer kennt sich mit Listen aus?

So ziemlich jeder hier, denke ich

[MartinSt]

Wer kennt sich mit Listen aus?

Listige Frage

[johann2]

... und wir dafür, dass Du Deine Lösungsansätze postest

Ich habe ja fast keine, darum hab ich nichts geschrieben.

a.

Beschreiben Sie einen Algorithmus mit der Zeitkomplexität O(n), welcher bestimmt ob eine verkettete Liste einen Zyklus enthält. Sie können O(n) extra Speicherplatz verwenden.

Den Zyklus in O(n) zu prüfen ist einfach. Man lässt den Iterator solange durchlaufen bist er wieder bei Anker.next angekommen ist oder eben auf null stößt.

Aber was ist mit : "Sie können O(n) extra Speicherplatz verwenden." gemeint?

Bei Aufgabe b muss ich passen, da hab ich keine Ahnung:confused:

Genauso wie bei der letzeren Aufgabe. Um den entsprechenden Knoten auszuketten, ist ja auch noch die Referenz auf seinen Vorgänger knoten nötig.

Man könnte ja auch wenn man die Referenz des Letzen Knotens hätte, den Inhalt der beiden Knoten tauschen und das letzte einfach mit = null löschen.

Nur um das letzte Element zu finden, muss man den Iterator ja auch durchlaufen lassen und das wäre dann nicht mehr O(1)

[Klotzkopp]

Den Zyklus in O(n) zu prüfen ist einfach. Man lässt den Iterator solange durchlaufen bist er wieder bei Anker.next angekommen ist oder eben auf null stößt.

Was ist Anker.next?

Aber was ist mit : "Sie können O(n) extra Speicherplatz verwenden." gemeint?

Dass du nicht beliebig viele zusätzliche Variablen anlegen darfst. Das muss eben im Rahmen von O(n) bleiben.

Man könnte ja auch wenn man die Referenz des Letzen Knotens hätte, den Inhalt der beiden Knoten tauschen und das letzte einfach mit = null löschen.

Nur um das letzte Element zu finden, muss man den Iterator ja auch durchlaufen lassen und das wäre dann nicht mehr O(1)

Du musst ja nicht mit dem letzten tauschen

[johann2]

Was ist Anker.next?

Anker ist die Zelle, über die ich in die Liste einsteige (oft auch Wurzel genannt). Der next-Zeiger der Ankerzelle zeigt auf das erste Element in der Liste.

Du musst ja nicht mit dem letzten tauschen

puh da habe ich aber keine idee

[Klotzkopp]

Anker ist die Zelle, über die ich in die Liste einsteige (oft auch Wurzel genannt). Der next-Zeiger der Ankerzelle zeigt auf das erste Element in der Liste.

Dann funktioniert dein Algorithmus nur, wenn das erste Element Teil des Zyklus ist. Das muss aber nicht so sein.

puh da habe ich aber keine idee

Mit welchem Knoten könntest du denn noch tauschen? An welchen kommst du garantiert schnell ran?

[flashpixx]

Dann funktioniert dein Algorithmus nur, wenn das erste Element Teil des Zyklus ist. Das muss aber nicht so sein.

Wenn Du danach gehst, dann hast Du per Definition keine Liste mehr, da Listen lineare Datenstrukturen sind, sondern einen gerichteten Graphen. Wenn man das als Graphenproblem betrachtet wären die Ansätze eine Tiefensuche oder eine topologische Sortierung, wobei ich bei beiden davon ausgehe, dass es sich hierbei nicht mehr um einen O(n) Algorithmus handelt bzw er auf beschränktem Speicher O(1) bzw O(n) operieren kann.

[Bubble]

Den Zyklus in O(n) zu prüfen ist einfach. Man lässt den Iterator solange durchlaufen bist er wieder bei Anker.next angekommen ist oder eben auf null stößt.

Dann müsste das erste Element der "Liste" bereits Teil vom Zyklus sein, das muss aber nicht so sein. Du sollst ja herausfinden, ob es sich tatsächlich um eine (einfach) verkettete Liste handelt, oder nicht versehentlich ein Zyklus eingebaut wurde.

Aber was ist mit : "Sie können O(n) extra Speicherplatz verwenden." gemeint?

Das bedeutet anders ausgedrückt ungefähr: Du darfst Dir etwas merken, zu jedem Element der Liste gleich viel.

Jetzt ist es ganz einfach auf Zyklen zu prüfen. Du kommst bestimmt drauf.

Bei Aufgabe b muss ich passen, da hab ich keine Ahnung:confused:

Lies noch einmal den Hinweis ganz genau, die Lösung steht praktisch schon da. Probiere es mal auf einem Blatt Papier aus.

Genauso wie bei der letzeren Aufgabe. Um den entsprechenden Knoten auszuketten, ist ja auch noch die Referenz auf seinen Vorgänger knoten nötig.

Überlege es Dir noch einmal genau, welcher Knoten (d.h. welcher Speicher) tatsächlich entfernt werden muss, um zum gewünschten Ergebnis zu kommen.

Bearbeitet 1. September 2010 von Bubble

[Klotzkopp]

Wenn Du danach gehst, dann hast Du per Definition keine Liste mehr, da Listen lineare Datenstrukturen sind, sondern einen gerichteten Graphen.

Ich fürchte aber, dass man für die Antwort "Widerspruch in der Aufgabenstellung" nicht so besonders viele Punkte in der Klausur bekommen wird.

[johann2]

Dann müsste das erste Element der "Liste" bereits Teil vom Zyklus sein, das muss aber nicht so sein.

Achso, stimmt:D ich hatte immer das Bild einer Ringliste im Kopf..

Ok ich habe die jetzt gelöst und wollte noch fragen ob das so richtig ist. Also:

a.

Beschreiben Sie einen Algorithmus mit der Zeitkomplexität O(n), welcher bestimmt ob eine verkettete Liste einen Zyklus enthält. Sie können O(n) extra Speicherplatz verwenden.

Dafür benutzt man in jeder Zelle eine zusätzliche Variable in der gespeichert wird, ob die Zelle unbesucht/besucht ist. Wenn der Iterator auf eine bereits besuchte Zelle stößt, ist es eine Liste mit Zyklus.

b.

Wiederholen Sie Aufgabe a). Benutzen Sie diesmal aber nur O(1) extra Speicherplatz. Lösungshinweis: Verwenden Sie zwei Iteratoren, die sich mit verschiedenen Geschwindigkeiten durch die Liste bewegen.

Hierbei lässt man einen Iterator jeweils in einer Schritten und den andere Iterator in zweier Schritten durch die Liste laufen. Sobald ein Iterator auf null trifft, ist die Liste ohne Zyklen. Wenn die Iteratoren sich aber irgendwann wieder treffen, dann ist ein Zyklus vorhanden.

In einer einfach verketteten Liste haben Sie eine Referenz auf einen Knoten, welcher nicht der letzte Knoten der Liste ist. Beschreiben Sie einen O(1) Algorithmus der den Wert in diesem Knoten löscht und die Integrität der Liste bewahrt.

Man tauscht den Inhalt der Zelle auf die man die Referenz hat mit dem Inhalt von seinem Nachfolger. Jetzt kann man diesen Nachfolger einfach ausketten.

Danke für die Hilfe:)

[flashpixx]

Dafür benutzt man in jeder Zelle eine zusätzliche Variable in der gespeichert wird, ob die Zelle unbesucht/besucht ist. Wenn der Iterator auf eine bereits besuchte Zelle stößt, ist es eine Liste mit Zyklus.

schau mal hier rein Zyklus (Graphentheorie) ? Wikipedia

(deshalb der Hinweis von mir auf die Graphentheorie).

Ansonsten würde ich sagen, dass die Algos passend, ob wirklich die passenden Aufwandsklassen korrekt sind, habe ich jetzt nicht nachgerechnet