johann2

Hallo,

ja was ist der Unterschied zwischen HTML Injection und Cross Site Scripting?

Laut Wikipedia ist Cross Site Scripting eine Art von HTML Injection, für mich ist das aber ein und dasselbe...

Gruß

Johann

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:)

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

... 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)

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 =)