C Doppelt verkettete Listen

[thefy]

Hallo Leute,
ich möchte eine doppelt verkettete Liste erstellen und einige Funktionen implementieren.

Als Vorgabe soll ich 2 Structs benutzen. Ein Node Struct mit Wert, previous-Zeiger, Next-Zeiger und ein List Struct, das Zeiger zum head und tail des Node Structs hat. Das ganze soll mit Library files erstellt werden, also ein .h file, ein .c file das sich auf das .h file bezieht und eben ein main file.

Wenn ich die structs im .h file definiere reicht dann z.B.: struct Node; ? Oder müssen sie komplett in das header file übernommen werden? Bei Funktionen wird ja auch nur Ausgabetyp und Name reingeschrieben. Erst im source file werden sie dann genauer definiert.
Ich habe die structs jetzt so im source file der library stehen. Ich denke das passt so.

struct Node {
    long data;
    struct Node* previous;
    struct Node* next;
}

struct List {
    struct List* head;
    struct List* tail;
}

In Bezug auf struct List steht bei der Aufgabe dabei, dass die beiden Zeiger, falls die Liste leer ist, "NULL" sein müssen. Wo genau muss ich das beachten?

Ich habe es in dieser Form (mit 2 Structs) noch nie gesehen. Deshalb bin ich etwas verwirrt.
Zum Beispiel ist die erste Funktion: struct List* new_empty_list()
Mit der eine neue leere Liste zurückgegeben wird. Ich frage mich wie man das genau umsetzt.
Wenn ich nur den Node struct hätte würde ich einen neuen Zeiger auf ein Node erstellen und mit malloc dynamisch zuordnen. Dann Anfangswerte zuteilen. Aber durch den 2. Struct weiß ich nicht genau was ich machen muss.

Ich hoffe ich habe meine Probleme verständlich ausgedrückt.
Danke schon mal!

 

[NemesisFS]

Ich würde es so machen, dann musst du nicht dauernd struct schreiben:

struct Node_t {
    long data;
    struct Node_t *previous;
    struct Node_t *next;
};
typedef Node_t Node;

und analog für die Liste

Da du ja nur eine leere Liste erstellst und in der List-struct nur Pointer zu einer Node existieren musst du nichts anders machen als bisher auch. Erst beim Einfügen in die Liste musst du dich darum kümmern, dass du die Nodes allokierst.

 

[I'm unknown]

Die Listendefinition sollte eher so aussehen:

struct Node {
    long data;
    struct Node* previous;
    struct Node* next;
}

struct List {
    struct Node* head;
    struct Node* tail;
}

Andernfalls würde der Kopf und das Ende der Liste auf kein Listenelement zeigen. Besitzt die Liste keinen oder nur einen Eintrag zeigen beide Pointer auf 0x00 bzw. das selbe Listenelement.

 

[thefy]

Ok danke passt aber wie siehts mit der frage bezüglich dem header File aus? Schreib ich da als Deklaration einfach struct Node; und kann es dann im Library Source File komplett definieren oder muss es im header schon komplett definiert sein?

Ich würde eine neue liste jetzt also so erstellen. Ist das korrekt?

struct List* new_empty_list() {
    struct Node* neu = (struct Node*) malloc(sizeof(struct Node));
    neu->data = -1;
    neu->previous = neu;
    neu->next = neu;
    return neu;
}

 

[misu]

- ins Header-File gehören die Deklarationen (damit man die Funktionen aus anderen Files heraus benutzen kann, C nutzt Separate-Compilation)
- in C-File die Definitionen
- List ist einfach nur ein Wrapper (ein Ding drum rum), um das Handling der Liste von außen als Liste ("List") durchführen zu können. Weil jemanden, der die Liste einfach nur nutzt, Knoten nicht so besonders interessieren. (Nur zum Iterieren.)
- Mit List musst du auch nicht viel machen, einfach nur bei ner neuen Liste leer zurückgeben (hier aufpassen!), ansonsten wird das List-struct nur für wegen der Pointer auf head und tail benötigt, denn wo sollen die auch sonst stehen.

Dein "new_empty_list" erzeugt zwar korrekt einen neuen Knoten, aber das ist nicht, was du willst. Eine neue Liste sollte KEINEN Knoten enthalten. Du willst lediglich eine leer-initialisierte Liste erzeugen. In deinem Code wird aber überhaupt kein List-struct erzeugt.
Also:
- irgendwo musst du ein List-struct erzeugen und korrekt die pointer setzen
- brauchst du wirklich einen Knoten?

 

[thefy]

Ok also muss es eher so aussehen:

struct List* new_empty_list() {
    struct List* neu = (struct List*) malloc(sizeof(struct List));
    neu->head =  ;
    neu->tail =  ;
    return neu;
}

Nur worauf beziehen sich die Pointer bei einer neuen Liste? 0x00?

 

[misu]

Das sieht schon deutlich besser aus. Wenn du die Pointer nicht initialisierst, dann wirst du später nicht mehr wissen, ob ein Pointer auf einen Knoten zeigt oder nicht. D.h. du benötigst einen Wert, der dir signalisiert, ob sich hinter dem Pointer tatsächlich ein Knoten verbirgt. Damit solltest du dir die Antwort selbst geben können.

 

[thefy]

Also muss ich head ja eigentlich einem neuen Knoten zuweisen oder den ich wie davor erstelle?

Oder ist head einfach die Adresse der Liste? Sprich neu->head = neu;

 

[misu]

Du warst vorhin schon auf der richtigen Fährte mit 0x00. Aber was du dir überlegen soltest ist, wie man das in C richtig schreibt und warum man das tun sollte. Warum darf man ein Pointer auf 0x00 setzen? Wofür dient das im Management?
Kannst auch gern nochmal nachfrage. Das ist aber ein bisschen der wesentliche Punkt, weswegen du da optimaleweise selbst draufkommen solltest.

 

[thefy]

Ursprünglich kenne ich das von malloc(). Wenn das schief läuft und kein Speicher zugeteilt werden kann liefert malloc() ja einen NULL Pointer. Also heißt es so viel wie "kein Speicher frei" und es "zeigt auf nichts".
Da ich ja eine leere Liste haben will in der noch nichts steht denke ich dass man das machen muss. Erst später wenn Nodes hinzukommen, kann man head und tail eine richtige Adresse zuordnen oder? Ich hoffe das stimmt so

Schreiben würde ich es so: neu->head = NULL;

 

[asdfman]

Man kann eine forward declaration machen. Ein sehr großer Vorteil gegenüber den Klassen in C++.
Ja, verprügelt mich. In C gibt es Kapselung zur Kompilierzeit, in C++ aber nicht. Sry

€: Hätte vielleicht lieber mal F5 gedrückt. Bezog mich auf #4.

 

[misu]

Das mit NULL ist korrekt. Den "zeigt auf nichts"-Wert brauchst du, um die aktuellen Enden der Liste zu erkennen. Damit solltest du den Rest eigentlich schaffen können.

 

[antred]

Man kann eine forward declaration machen. Ein sehr großer Vorteil gegenüber den Klassen in C++.
Ja, verprügelt mich. In C gibt es Kapselung zur Kompilierzeit, in C++ aber nicht. Sry

€: Hätte vielleicht lieber mal F5 gedrückt. Bezog mich auf #4.

Verstehe nicht, was du meinst. Forward declarations sind in C++ genau so möglich wie in C. Auch die Aussage zu Kapselung zur Kompilierzeit in C vs C++ verstehe ich nicht. Kannst du da genauer drauf eingehen?

 

[misu]

Das gibt's nix zu fragen, klar ist das möglich (in C und C++). Und bitte nicht den Thread kapern.