Wieso ist eine verkette Liste eine rekursive Datenstruktur?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
Dr.Miles
User
Beiträge: 38
Registriert: Montag 15. Dezember 2008, 08:33
Wohnort: Mannheim
Kontaktdaten:

Hallo,
was ist gemeint mit:
Eine verkettete Liste wird als rekursive Datenstruktur betrachtet, weil sie rekursiv definiert ist. Quelle
Was ist an einer verketten Liste denn rekursiv?
Also rekursiv ist für mich etwas, wenn es durch sich selbst definiert ist, aber in welcher weißer ist das bei dieser Art Listen der Fall?

Danke für die Antwort im voraus.
Gruß
Dr.Miles[/url]
www.i2p2.de <--- sehr interressantes Anonymisierungsprojekt.
www.schaeuble-wegtreten.de <--- Petition gegen Schäuble
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

'ne verkettete Liste definiert sich doch in sich selbst! Jedes Element enthält einen Verweis auf einen Element des selben Types.
Benutzeravatar
Dr.Miles
User
Beiträge: 38
Registriert: Montag 15. Dezember 2008, 08:33
Wohnort: Mannheim
Kontaktdaten:

Also eine verkette Liste sieht für mich so aus:


|---Knoten--|
|inhalt |
|verweis |
|-------------|

|---Knoten--|
|inhalt |
|verweis |
|-------------|

|---Knoten--|
|inhalt |
|verweis |
|-------------|

oder:

|---Knoten--|
|inhalt |
|verweis |
|-------------|

oder:

[None] (Also eine leere Liste)

Wenn sich diese Liste dann durch sich selbst definiert, dann hat sie doch jedesmal eine andere Definition?!

Edit: Ist mit rekursive Datenstruktur gemeint, das die Struktur die die Liste hat sich durch sich selbst (also rekursiv) definiert?
Edit2: Also dieser Satz in anderen Worten:
Eine verkettete Liste besitzt eine rekursive Datenstruktur , weil die Struktur dieser Listenart sich aus der Anzahl der vorhandenen Elemente ergibt
Zuletzt geändert von Dr.Miles am Samstag 31. Januar 2009, 21:43, insgesamt 1-mal geändert.
www.i2p2.de <--- sehr interressantes Anonymisierungsprojekt.
www.schaeuble-wegtreten.de <--- Petition gegen Schäuble
BlackJack

Ein Knoten enthält einen Verweis auf einen Knoten, also auf den gleichen Typ, von dem er selbst ist. Das ist die Rekursion.
Benutzeravatar
Dr.Miles
User
Beiträge: 38
Registriert: Montag 15. Dezember 2008, 08:33
Wohnort: Mannheim
Kontaktdaten:

BlackJack hat geschrieben:Ein Knoten enthält einen Verweis auf einen Knoten, also auf den gleichen Typ, von dem er selbst ist. Das ist die Rekursion.
Also ist der Knoten rekursiv definiert?
Und weil der Knoten aus einem anderen Knoten besteht ist er selbst rekursiv definiert?

Aber definiert wird der Knoten doch hier:

Code: Alles auswählen

class Knoten:
	def __init__(self, inhalt=None, naechster=None):
		self.inhalt = inhalt
		self.naechster  = naechster
	def __str__(self):
		return str(self.inhalt) 
Also wird doch nur ein Verweis auf eine Instanz des Knotens in der Knoteninstanz gespeichert.

Ich glaube ich weiß was du meinst, das
Knoten= inhalt , naechsterknoten(der vom Typ Knoten ist) ist
Also zur Laufzeit der Liste kann ich da etwas erkennen was mich vom Muster her ein wenig an Rekursion erinnert, aber nur mit Gewalt.

Edit: Also ist diese Rekursion bei einem Endknoten nicht mehr gegeben? Weil dort zeigt knoten.naechster ja auf None.

PS: Ich glaub ich habs:
Die bei einer vL bestehnd aus 3 Knoten ist die Definition von Knoten 1:
.inhalt
.naechster = knoten2 (was knoten 3 mit einschließt)
Also ist die Definition von Knoten 1 = nutzdaten + alle anderen knoten (indirekt über .naechster der jeweilig folgenden Knoten)
www.i2p2.de <--- sehr interressantes Anonymisierungsprojekt.
www.schaeuble-wegtreten.de <--- Petition gegen Schäuble
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Man sieht die Rekursivität sehr schön z.B. an der Definition in Haskell:

Code: Alles auswählen

data LinkedList a = Nil | Cons a (LinkedList a)
Die LinkedList taucht also in ihrer eigenen Typdefinition auf.

Ähnliches gilt z.B. für Bäume, wo das etwa so aussehen kann:

Code: Alles auswählen

data SomeTree a  = Leaf a | Node (SomeTree a) (SomeTree a)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
BlackJack

@Dr.Miles: Man sieht das Python nicht so gut, weil man bei der Definition keine Typen für die Attribute angeben muss. Bei statisch typisierten Programmiersprachen wird das deutlicher, wie in dem Haskell-Beispiel von birkenfeld.

Hier so etwas in C#:

Code: Alles auswählen

class Node<T>
{
    T data;
    Node<T> next;
    
    // Methoden...
}
Innerhalb der Definition des Typs `Node<T>` wird der Typ selbst verwendet.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

In Prosa: Eine Liste ist entweder leer oder es ist ein Element plus eine Liste.

Das ist offensichtlich rekursiv.

Stefan
Benutzeravatar
Dr.Miles
User
Beiträge: 38
Registriert: Montag 15. Dezember 2008, 08:33
Wohnort: Mannheim
Kontaktdaten:

Also ich habe mir einmal die Arbeit gemacht und den Abschnitt 17.1 neu geschrieben wie ich es formuliert hätte:

17.1 Eingeschlossene Verweise

Wir haben Beispiele gesehen, bei denen Objekte in Attributen gespeichert wurden. So etwas nennt man einen eingeschlossenen Verweis.
Eine sog. verkette Liste nutzt diese Möglichkeit.

Verkettete Listen bestehen aus Knoten, wobei jeder Knoten einen Verweis zum nächsten Knoten der Liste enthält. (Es sei denn es ist der "Endknoten")
Weiterhin enthält jeder Knoten eine bestimmte Menge Nutzdaten, die den (für den Gebrauch nützlichen) Inhalt dieses Knotens darstellen.

Eine verkettete Liste besitzt eine rekursive Datenstruktur, d.h. das sich die Struktur der verketten Liste aus der Anzahl
der vorhandenen Knoten zusammensetzt. (A)

Eine verkette Liste >ist< ein oder mehrere Knoten(*1). Ein Knoten enthält zwei Attribute, einem Attribut das die Nutzdaten enthält
und einem, welches den nächsten Knoten beinhaltet. Falls es keinen nächsten Knoten gibt (also am Ende der verketten Liste), wird dem Attribut,
welches den nächsten Knoten enthalten sollte None zugewiesen. Das None kennzeichnet das Ende der verketten Liste.

Eine verkette Liste ohne einem einzigen Element wird mit None dargestellt. (Die Bedeutung von None ist nur in diesem Kontext "leere verkette Liste"
None an sich ist ein Objekt, welches einfach gesagt nichts repräsentiert.)

Die folgende Abbildung stellt eine verkette Liste visuell dar:

Bild

*1 In anderen Worten: Der erste Knoten ist die verkette Liste, da in ihm alle anderen Knoten definiert sind, was Abb.1 deutlich zeigt.


Ist das soweit alles richtig?
www.i2p2.de <--- sehr interressantes Anonymisierungsprojekt.
www.schaeuble-wegtreten.de <--- Petition gegen Schäuble
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Klingt gut.

Streng genommen müssen es nicht explizite Knoten sein. Wenn man (in früheren Zeiten) ein bisschen Speicherplatz sparen wollte, verschmilzt man Nutzdaten und Verweis zu einem Objekt, z.B.

Code: Alles auswählen

class Process: # pseudocode, um Typen klar zu machen
    pid = int
    name = str
    next = Process
Stefan
Antworten