Code-Schnipsel

Zitat:
Was macht exists()? Prüfen ob ein Element in der Liste ist? Gute Idee!

Was macht defined()?

Ich kenne diese beiden Funktionen von Perl.

Grob übersetzt aus meinem Buch:
exists gibt WAHR zurück, wenn das Element definiert ist, und es kann nur definiert sein, wenn es existiert.
defined gibt ebenfalls einen Boolschen Wert zurück, der angibt, ob das Element einen reelen Wert besitzt oder nicht.

Ich stelle mir das dann so vor:
Wenn n->data==TRUE, dann exists(n->data) == TRUE und defined(n->data) == TRUE.
Wenn n->data==NULL, dann exists(n->data) == TRUE und defined(n->data) == FALSE.
Wenn n->next==NULL, dann exists(n->next) == FALSE und defined(n->next) == FALSE.


Gruß,
Patrick-Oliver

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Zitat:

Meinst Du mit "Head"-Element einen Zeiger auf das vorherige Element, denn die Struktur sieht mir wie eine normale einfach verkettete Liste aus?

Das ist auch eine normale einfach verkettete Liste, aber gelegentlich sieht man auch sowas hier:

typedef struct _ListHead {
        node *list;
        size_t size;
} ListHead;

Die Funktionen erhalten dann einen Zeiger auf ListHead. Das hat folgende Vorteile:

1) die Funktionen bekommen ausnahmslos einen Zeiger auf ListHead, nicht die Adresse des Zeigers auf die Liste selbst (wie bei manchen meiner Funktionen)
2) die Größe der Liste läßt sich in konstanter Zeit ermitteln

Das hat aber auch Nachteile:
3) eine Teilliste ist nicht selbst wieder automatisch eine Liste
4) Operationen wie beispielsweise split erzeugen unnötig Overhead, da jedesmal ein neuer ListHead angelegt werden muss

Wie man es macht, ist im Prinzip Geschmackssache.

Ich mag offensichtlich die Lösung ohne ListHead, da (1) unnötig ist, wenn man mal gelernt hat wie man Zeiger an Funktionen übergibt und (2) unnötig ist weil man in keiner Listenoperation die Länge der Liste mehr als einmal ermitteln muss (die asymptotische Laufzeit sich also nicht ändert).

Davon abgesehen sind (3) und (4) echte Vorteile, die sich nicht durch irgendwelche Tricks ausgleichen liessen.

Zitat:

Ich kenne diese beiden Funktionen von Perl.

Grob übersetzt aus meinem Buch:
exists gibt WAHR zurück, wenn das Element definiert ist, und es kann nur definiert sein, wenn es existiert.
defined gibt ebenfalls einen Boolschen Wert zurück, der angibt, ob das Element einen reelen Wert besitzt oder nicht.

Ich stelle mir das dann so vor:
Wenn n->data==TRUE, dann exists(n->data) == TRUE und defined(n->data) == TRUE.
Wenn n->data==NULL, dann exists(n->data) == TRUE und defined(n->data) == FALSE.
Wenn n->next==NULL, dann exists(n->next) == FALSE und defined(n->next) == FALSE.

Ein Listenelement ist bei mir immer definiert, da man nur mit push() oder insert() neue Elemente hinzufügen kann; beide Operationen verlangen einen korrekten Wert für n->data.
defined(n->data) ergibt also immer TRUE, und zwar für alle Elemente der Liste.

(exists(n->next) == TRUE) kann man auch schreiben als (n->next != NULL)

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Zitat:
Das hat folgende Vorteile:

Zitat:

1) die Funktionen bekommen ausnahmslos einen Zeiger auf ListHead, nicht die Adresse des Zeigers auf die Liste selbst (wie bei manchen meiner Funktionen)

Wo ist da der Vorteil?

Zitat:

2) die Größe der Liste läßt sich in konstanter Zeit ermitteln

Weil die Größe im Strukturelement size vorliegt?

Zitat:
Das hat aber auch Nachteile:

Zitat:

3) eine Teilliste ist nicht selbst wieder automatisch eine Liste

Warum nicht?

typedef struct _ListHead {
node *list;
size_t size;
} ListHead;

...

ListHead *LH;
/* Speicher anfordern für *LH und innere Liste */

...

LH->list->next->next; // Teilliste

Oder wie meinst Du das?

 

Zitat:

Zitat:

1) die Funktionen bekommen ausnahmslos einen Zeiger auf ListHead, nicht die Adresse des Zeigers auf die Liste selbst (wie bei manchen meiner Funktionen)

Wo ist da der Vorteil?

Die Referenz auf die Liste ändert sich, wenn man das erste Element ändert. Deshalb verlangen in meiner Lib alle Funktionen, die möglicherweise das erste Element ändern (push, pop, insert, remove, move, usw.), die Adresse der Referenz statt die Referenz selbst:

// Prototyp:
int list_push(node **_x, int _data)

// Anwendung:
node *x = NULL;

list_push(&x, 17);

Der Adress-Operator beim Pointer verwirrt viele. Weiterhin verlangen manche Funktionen ein node** x, manche nur ein node *x (je nachdem, ob das erste Element geändert werden kann oder nicht).

Das verwirrt viele und macht die API nicht ganz so sauber wie sie sein könnte.

Mit einem ListHead hat man dieses Problem nicht, da sich die Adresse des ListHeads selbst nicht ändert, egal was man macht.

Zitat:

Zitat:

2) die Größe der Liste läßt sich in konstanter Zeit ermitteln

Weil die Größe im Strukturelement size vorliegt?

Genau. Im ListHead kann man noch andere großartige Informationen unterbringen, z.B. ob die Liste sortiert ist oder eine Referenz auf das letzte Element der Liste (z.B. lassen sich damit "insert"-Operationen am Ende der Liste in konstanter Zeit realisieren).

Zitat:

Zitat:

3) eine Teilliste ist nicht selbst wieder automatisch eine Liste

Warum nicht?

Naja. Wenn man mit ListHead arbeitet, besteht eine Liste aus einem ListHead und 0 oder mehr nodes, die miteinander einfach verkettet sind.

Eine Teilliste müsste ebenfalls einen ListHead haben, hat sie aber nicht. In der Konstruktion mit ListHead ist LH->list->next->next KEINE Teilliste, es ist nicht einmal überhaupt eine Liste. Eine Liste wird durch einen ListHead repräsentiert und durch sonst gar nichts.
Sämtliche Funktionen erwarten auch einen ListHead und nicht ein node*, um die Liste zu manipulieren. Ein node* nützt also gar nichts ohne den entsprechenden ListHead.

Folgendes Konstrukt aus list_insert() wäre z.B. nicht möglich:

if((p = list_sub(*_x, _pos-1)) == NULL)
	return(-1);

return(list_push(&(p->next), _data));

p ist die Teilliste, die in _x an der Stelle _pos-1 beginnt. Ich füge also an der Stelle _pos ein Element ein und verbiege den Pointer im Element davor mit dem list_push() im return(). Würde list_push() einen ListHead erwarten, wäre das nicht möglich. Ich müsste die Adresse von node[_pos] zwischenspeichern, ein Element nach _pos-1 einfügen und dessen next-Zeiger auf die gemerkte Adresse von node[_pos] zeigen lassen.

Gruss,
Philip

PS: das obige Konstrukt mit dem Source ist genial, aber leider nicht von mir erfunden.

PPS: Auch bei meiner Konstruktion funktionieren insert()-Operationen in "fast" konstanter Zeit: list_push() geht offensichtlich in O(1), wie sich leicht sehen läßt (keine Schleife, keine Rekursion). Möchte man Elemente am Ende der Liste einfügen (normalerweise sehr kostenintensiv, weil man jedesmal die Größe bestimmen und dann die Liste bis zum Ende traversieren muss, um das Element einzufügen), kann man sich eines einfachen Tricks bedienen:
- Liste reversieren
- Elemente in O(1) mit push() einfügen
- Liste wieder reversieren

Liste reversieren geht in O(n*log(n)), also verflucht schnell.

Damit kann man sowohl am Anfang als auch am Ende Elemente in konstanter Zeit einfügen (für ein einziges oder vielleicht zwei Elemente lohnt sich das Reversieren nicht, aber ab drei wird's schon interessant).

PPPS: es gibt übrigens bereits eine Funktion, die Elemente am Ende der Liste einfügt (falls die jemand vermisst). Zum einen könnte man das mit list_insert(&x, list_size(x), 17) machen, einfacher geht es aber mit list_join(). join hängt normalerweise eine Liste an eine andere dran, aber diese Liste kann ja ruhig nur ein Element haben...

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Zu 1: Achso, natürlich, jetzt versteh ich, wie Du das meinst. Das ist das Problem, welches ich hier beschrieben hab:

Funktion schreibt nicht korrekt in char-Pointer

Oder meinst Du etwas anderes?


Zu 3:

Zitat:

Naja. Wenn man mit ListHead arbeitet, besteht eine Liste aus einem ListHead und 0 oder mehr nodes, die miteinander einfach verkettet sind.

Eine Teilliste müsste ebenfalls einen ListHead haben, hat sie aber nicht. In der Konstruktion mit ListHead ist LH->list->next->next KEINE Teilliste, es ist nicht einmal überhaupt eine Liste. Eine Liste wird durch einen ListHead repräsentiert und durch sonst gar nichts.
Sämtliche Funktionen erwarten auch einen ListHead und nicht ein node*, um die Liste zu manipulieren. Ein node* nützt also gar nichts ohne den entsprechenden ListHead.

Naja, wenn man dies so sieht, hast Du natürlich recht aber man könnte auch einwenden, dass die Version ohne ListHead, dann keine Liste ist (natürlich falsch).
Wenn man die Liste nur mit den Funktionen (welche Operationen darstellen) bearbeiten soll, sind natürlich hier keine Teillisten möglich.
Bei meiner Frage, dachte ich nur mehr daran, dass es ab jedem note ja auch wieder eine Verkettung geben kann, welche dann eine Liste darstellt (eine Liste, wie sie im Buch vorkommt).

Zitat:
Liste reversieren geht in O(n*log(n)), also verflucht schnell

Ist n die Anzahl der besuchten Elemente?
Wie kommst Du auf log(n)?

Die Lib scheint sehr interessant zu werden, weiter so .