C Verkettete Liste

[WIng93]

Wieso sollte man sie nicht global definieren? Welchen Nachteil bringt das denn mit sich?

 

[LencoX2]

Viel zu lernen du noch hast, junger Wing
Kleiner Scherz, den ich mir nicht verkneifen konnte.

Globale Variablen sind technisch gesehen total OK. Jedoch sind die Grenzen der technischen Möglichkeiten selten ein guter Designansatz. Fachfremdes Beispiel: Technisch fahren Autos über 100 km/h und doch fahren wir in der Stadt 50 km/h. Das ist eine Konvention bzw. Best Practice.

Ein guter Designansatz ist es Variablen und sogar auch Typdefinitionen im engsten Scope zu definieren, der benötigt wird um die Anforderungen zu erfüllen. Wenn es im ganzen Programm genau eine verkettete Liste gibt, könnte man darüber nachdenken, diese Liste global zu definieren.

Ergänzung (11. Februar 2020)

Wieso sollte man sie nicht global definieren? Welchen Nachteil bringt das denn mit sich?

Ah ja: Nachteil:
1. Der globale Raum wird "zugemüllt"
2. Man hat keine Kontrolle, wer zu welcher Zeit wie auf die Variable zugreift und sie ggfs manipuliert.
3. Allgemein heisst es so gut wie immer zu Globalen Variablen : meide sie !

 

[WIng93]

Also sollte ich wie mein Prof das ganze angegangen ist so dabei vorgehen:

node_t *createlist()
{                   
    return 0;
}

Ich verstehe leider immer noch nicht genau was diese Funktion hier macht. Ich weiss, dass sie einen NULL-Zeiger auf den typ node_t zurück liefert. Aber wofür das Programm, diese Funktion verwendet (anscheinend ist die das erste Element oder Header (bin mir noch unsicher)) .


-> "Euch lebend zu sehen mein Herz aufs Wärmste erfreut." 😂 😂

 

[LencoX2]

Also sollte ich wie mein Prof das ganze angegangen ist so dabei vorgehen:

node_t *createlist()
{                
    return 0;
}

Ich verstehe leider immer noch nicht genau was diese Funktion hier macht. Ich weiss, dass sie einen NULL-Zeiger auf den typ node_t zurück liefert. Aber wofür das Programm, diese Funktion verwendet (anscheinend ist die das erste Element oder Header (bin mir noch unsicher)) .


-> "Euch lebend zu sehen mein Herz aufs Wärmste erfreut." 😂 😂

Sie erzeugt sozusagen eine leere Liste, da diese als ein Zeiger auf das erste Listenelement gefordert ist. Da die Liste leer ist, ist es in diesem Fall ein null Zeiger. Falls die leere Liste irgendwann Mal anders gefordert ist, könnte man das zentral in dieser Funktion programmieren.

UND: es war die Aufgabenstellung eine Funktion anzugeben 8)

 

[Multivac]

node_t* liste1 = NULL;
node_t* liste2 = createlist();

Sind gleichwertig und wenn ich mich richtig erinnere sind Globalevariablen automatisch mit 0 initialisiert. Laut Bild aus deinem Ersten Post ist das die erste Node nicht Head! createlist gibt einfach 2Punkte es ist auch schöner einen function call als ein extra Kommentar zu schreiben. Es für die Aufgabe nicht notwendig Head als lokale variable zu nutzen, aber denk mal weiter und ich gebe dir Jetzt eine neue aufgabe F) Legen sie eine zweite Liste an. Jetzt musst du Jede Funktion ändern. deswegen wird jeder gute Programmierer es direkt als lokale variable schreiben. Selbst beim lesen den Codes ist es ein echtes Problem ich muss jede Zeile lesen um zu sehen wo Head geändert wird.

 

[WIng93]

Hallo zusammen,

ich weiss jetzt wo mein Denkfehler leider bei der ganzen Sache war und weshalb ich das Thema nicht richtig verstanden habe. Leider hat unser Professor uns nie gezeigt, wie man die verkettete Liste anwendet , sondern lediglich wie man die einzelnen Funktionen schreibt. Also ich hab sie nie in der main-Funktion gesehen, wie sie arbeitet. Daher habe ich mich auch die ganze Zeit gefragt, woher die Liste sozusagen weiss, an welcher Stelle wir uns gerade befinden oder warum bei der anhängen Funktion , die Liste weiss, dass das Element am Ende angehängt wird (wir sind ja keine while-schleife durchlaufen, bis wir das letzte Element erreicht haben).

Ich habe irgendwo noch einen Fehler gemacht, aber zunächst geht es mir erstmal um das Grundprinzip. Ich hoffe ich habe das soweit verstanden.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// Strukturen für die Liste
struct data
{
    unsigned int nummer;
    char name[42];
    int anzahl;
};

typedef struct node
{
    struct data data;
    struct node *next;
}node_t;


// leere Liste anlegen
node_t *createlist()
{
    return NULL;
}


// funktion um am Ende der Liste anzuhängen
node_t *newElement(unsigned int nummer, char name[42], int anzahl)
{
    node_t *new = malloc (sizeof(node_t));

    if(new == NULL)
    {
        return NULL;
    }

    new->next = NULL;
    new->data.nummer = nummer;
    strcpy(new->data.name, name);
    new->data.anzahl = anzahl;

    return new;
}


// funktion zum ausgeben der Liste
void printListe(node_t *head)
{
    node_t *temp = head;

    while(temp != NULL)
    {
        printf("%3u : %s (%02d) \n" ,temp->data.nummer, temp->data.name, temp->data.anzahl);
        temp = temp->next;
    }
}



int main()
{
    node_t *knotenAktuell;           // Knoten der das aktuelle Element besitzt
    node_t *liste = createlist();   // leere Liste wird erstellt
    liste = malloc(sizeof(node_t)); // Speicher für die Liste erzeugt

    liste->next = NULL;             // Leere Liste zeigt auf NULL

    liste->data.nummer = 1;
    strcpy(liste->data.name , "schwarz");
    liste->data.anzahl = 10;

    knotenAktuell = liste;       // Wir haben in der Liste nur ein Element, und das ist gleichzeitig knoten Aktuell

    knotenAktuell = newElement(2, "lila", 8);   // knotenAktuell bekommt nun den zweiten Knoten übergeben
    knotenAktuell = newElement(3, "rot", 20);   // aktueller Knoten ist jetzt der dritte Knoten

    printListe(liste);

    return 0;


}

Ich habe vorher nie verstanden, woher meine Liste weiss, dass sie jetzt hinten ein Knoten anhängen muss, jetzt habe ich verstanden (ich weiss das war dumm), dass ja das Element einfach hinten angehängt wird in der main-Funktion. Der aktuelle Knoten bekommt einen neuen Knoten zugewiesen. Dort wird dann de nextr Zeiger des aktuellen Knotens (der eigentlich auf NULL zeigt) auf den neuen Knoten gesetzt und der next Zeiger des neuen Knotens verweist auf NULL (da es jetzt der letzte Knoten ist)


Ich weiss auch (durch Orientierung an Musterbeispiele vom Internet) , dass ich eigentlich, damit das Programm so funktioniert wie ich es möchte folgendermaßen umgeändert werden müsste:

Zeile 74 und 75:

    knotenAktuell = newElement(knotenAktuell, 2, "lila", 8);  
    knotenAktuell = newElement(knotenAktuell, 3, "rot", 20);

Zeile 28 bis 43:

node_t *newElement(node_t *knotenAktuell, unsigned int nummer, char name[42], int anzahl)   // knotenAktuell auch als Argument übergeben
{

    node_t *new = malloc (sizeof(node_t));

    if(new == NULL)
    {
        return NULL;
    }
    knotenAktuell->next = new;  // next zeiger vom letzten Element verweist auf new statt auf NULL
    new->next = NULL;
    new->data.nummer = nummer;
    strcpy(new->data.name, name);
    new->data.anzahl = anzahl;

    return new;
}

Ich hatte es jedoch absichtlich nicht umgeändert gehabt, da die Musterlösung vom Professor für diese Aufgabe , in der newElement - Funktion den aktuellen Knoten nicht übergeben hat .

Ich wollte daher fragen, ob mir jemand sagen könnte wie ich die main-Funktion ändern könnte, dass es auch ohne der Übergabe von knotenAktuell an newElement funktioniert.

oder ist es im Grunde egal (nach dem Motto alle Wege führen nach Rom) oder habe ich dort irgendeinen Fehler gemacht, der zu Fehler im nachhinein führen kann oder auch zu "unsichtbaren" Fehlern ?



Vom Gefühl her, weiss ich das ich hier auch etwas falsch gemacht habe bzw. es schlecht geschrieben habe, dass es auch besser und kürzer geht :

Zeile 63 - 72:

    node_t *liste = createlist();  
    liste = malloc(sizeof(node_t));

    liste->next = NULL;            

    liste->data.nummer = 1;
    strcpy(liste->data.name , "schwarz");
    liste->data.anzahl = 10;

    knotenAktuell = liste;

Ich hätte noch eine allgemeine frage zu typedef und Strukturen könnte ich statt :

struct data
{
    unsigned int nummer;
    char name[42];
    int anzahl;
};

typedef struct node
{
    struct data data;
    struct node *next;
}node_t;

folgendes schreiben:

struct data
{
    unsigned int nummer;
    char name[42];
    int anzahl;
};

typedef struct node node_t;        //hier typedef schon anwenden

struct node
{
    struct data data;
    node_t *next;            // hier schon node_t schreiben statt struct node *next
};

oder wäre dies auch nicht von vorteil?




Ich danke euch allen im voraus auf eure Rücksicht und eure Hilfe. Ich glaube ohne euch, hätte ich dieses Thema immer noch nicht annähernd verstanden.

_____________________________

Eine kleine Frage fällt mir doch noch ein.
Wenn ich hier in der Aufgabe, den String als Pointer deklariert hätte, könnte ich ihn dann ohne strcpy initalisieren.

struct data
{
    unsigned int nummer;
    char *name;
    int anzahl;
};

dann könnte ich name folgendermaßen initialisieren:

    new->next = NULL;
    new->data.nummer = nummer;
    new->data.name = name;
    new->data.anzahl = anzahl;

Müsste ich dann das listing an einer anderen Stelle ändern , weil ich statt ein string array einen string pointer genutzt habe?


P.S. ich weiss, dass in der Aufgabenstellung gefordert war, einen String in der Größe von 42 Zeichen zu deklarieren, aber in der Klausur muss ich auf alle Eventualitäten eingestellt sein.

 

[Zuse1]

Ich habe vorher nie verstanden, woher meine Liste weiss, dass sie jetzt hinten ein Knoten anhängen muss, jetzt habe ich verstanden (ich weiss das war dumm), dass ja das Element einfach hinten angehängt wird in der main-Funktion. Der aktuelle Knoten bekommt einen neuen Knoten zugewiesen. Dort wird dann de nextr Zeiger des aktuellen Knotens (der eigentlich auf NULL zeigt) auf den neuen Knoten gesetzt und der next Zeiger des neuen Knotens verweist auf NULL (da es jetzt der letzte Knoten ist)

Richtig.

node_t ist bei Dir global vereinbart. Besser wäre es, es lokal in der main()-Methode zu erzeugen und dann an die jeweiligen Methoden zu übergeben. Also statt

typedef struct node
{
    struct data data;
    struct node *next;
}node_t;

schreibst Du

typedef struct node
{
    struct data data;
    struct node *next;
};

Und in der main()-Methode erzeugst Du dann die Strukturvariable:

struct node node_t*;

Es gibt ein Sprichwort: "So lokal wie möglich, so global wie nötig".
Das gehört nämlich zur sogenannten Datenkapselung welches die Übersichtlichkeit, Wartbarkeit und Modulation verbessert. Wenn Dir das Dein Lehrer anders gezeigt hat (mit globalen Variablen) dann musst Du es so machen wie er will, auch wenn das schlechter Programmierstil ist. "Alles im Ganzen" neigt dein Code Richtung Spaghetticode, auch wenn es noch im Rahmen ist. Tipp: Versuche mal alles auf Papier zu bringen (Zeichnen, ausdrucken) und auf dem Papier durchzugehen. Das kann oft helfen Fehler oder Denkfehler aufzuspüren. Diesen statischen Test nennt man "Schreibtischtest" und gehört zum Bereich des Software Engineering.

 

[simpsonsfan]

Das hast du was durcheinandergebracht, Zuse1. node_t ist der Typenbezeichner, keine Variable. Der von dir gepostete Code kompiliert auch gar nicht. Also davon nicht verwirren lassen, @WIng93.
Ich schreibe gerade noch ein paar Sätze zu der Antwort davor, das kann man auch nicht unbedingt so stehen lassen. Dauert aber noch kurz.

Also, grundsätzlich. Eine einfach verkettete Liste weiß gar nicht, an welcher Stelle wir uns befinden. Der Einstieg erfolgt zunächst immer über den Kopf und dann hangelt man sich durch.
Die von deiem Prof geforderte Funktion newElement soll lediglich ein neues Element im Speicher anlegen, sie soll es noch gar nicht in die Liste einfügen / mit der Liste verknüpfen. Dafür wäre dann die Funktion insert gedacht, die wiederum einen Pointer auf die Liste (d.h. den Listenkopf) erhält und einen Pointer auf ein in die Liste einzufügendes Element. Die Funktion insert würde dann die Liste von Beginn an durchgehen und an der richtigen Stelle (soll ja sortiert sein) das ihr übergebene Element einfügen. Der Aufruf von insert könnte dann bspw. so aussehen:

node_t *newElem = newElement(1, "Blub", 42);
insert(head, newElem);

oder in einer Zeile

insert(head, newElement(1, "Blub", 42));

Willst du ein Element am Ende der Liste einfügen, so musst du zunächst tatsächlich alle Elemente durchgehen, bis du beim letzten angekommen bist. Falls "Einfügen am Ende der Liste" ein häufiger Usecase ist, wäre es aber natürlich sinnvoll, sich neben dem Zeiger head auch einen Zeiger tail auf das letzte Listenelement vorzuhalten. Will man dann auch noch von hinten nach vorne durch die Liste gehen, speichert man für jeden Knoten neben next auch prev und landet bei einer doppelt verketteten Liste.
Dein oberer Codeblock funktioniert daher auch nicht wirklich. Du erhälst dort eben gerade keine zusammenhängende Liste, sondern lediglich einen Knoten in liste und einen Knoten in knotenAktuell, sowie einen nicht mehr ansprechbaren Speicherbereich (Memory Leak), in dem dein lila Element gespeichert ist. Folgerichtig gibt dein korrekt implementiertes printListe auch nur einen Knoten aus.

Zur zweiten Frage, ja das funktioniert, den typedef bereits vorher zu schreiben. Kommt aufs Gleiche raus.

Zur dritten Frage: Nein, das wäre nicht zielführend. Das würde zwar theoretisch gehen, du würdest aber eben lediglich einen Pointer auf einen schon bestehenden Speicherbereich übergeben. Da name hier aber ein als Funktionsargument übergebenener String ist, willst du das nicht unbedingt tun. Solange der Speicherbereich, auf den name zeigt gültig ist, ist das kein Problem, wenn aber du irgendwo lokal einen String anlegst und diesen dann deiner Funktion übergeben willst, so zeigt das neue Element ebenfalls auf einen sinnlosen Speicherbereich, sobald dein lokal übergebener String ungültig wird.
Ich finde es sowieso schon grenzwertig, das euer Prof euch dynamisch Speicher allozieren lässt, aber nicht wieder freigeben lässt. Das

free(liste);

aus Post #18 gibt nämlich auch nur den ersten Knoten wieder frei, führt also zu einem Speicherleck.

 

[WIng93]

Vielen dank, ich bin so fokussiert in das Thema , weil es in der Klausur 40% der Punktzahl ausmacht . Also die main die ich geschrieben habe, lässt sich ausgeben (Also ich bin mir auch ziemlich sicher , dass sie (höchstwahrscheinlich) sehr ineffizient ist, aber sie funktioniert 😂 ) .

Ergänzung (12. Februar 2020)

Das hier war die Musterlösung vom Professor für insert , aber ich hab irgendwann den Faden verloren weil er sie 20 mal korrigiert hat an der Tafel und seine Meinung immer geändert hat, welcher Ansatz der beste wäre um den Aufgabenteil zu lösen :

void insert (node_t **list, node_t*)
{
    if(*list == NULL)
    {
        *list = node;
    }
    else
    {
        if(*list->data.nummer  <  node->data.nummer)
        {
            node->next = *list;
            *list = node;
        }
        else if(*list->data.nummer == node->data.nummer)
        {
            *list->data.anzahl += node-> data.anzahl;
            free(node);
        }
        else
        {
            node_t *temp = *list;
            while(temp->next != NULL)
            {
                if(temp->next->data.nummer == node->data.nummer)
                {
                    temp->next->data.anzahl += node->data.anzahl;
                    free(node);
                    return;
                }
                else if(temp->next->data.nummer > node->data.nummer)
                {
                    temp->next = temp->next;
                    temp->next = node;
                }
                else if(temp->next->data.nummer < node->data.nummer)
                {
                    temp = temp -> next;
                }
            }
            temp->next=node;
        }
    }
}

Ergänzung (12. Februar 2020)

Der Anfang ist noch bisschen zu verstehen.
Falls die Liste leer ist, so ist der neue Knoten , der Listenanfang

Ansonsten
- falls die Artikelnummer vom ersten Element der Liste, kleiner ist als die Artikelnummer des neuen Elements, dann lass den nextZeiger des neuen Elements auf den Listenanfang zeigen (somit ist es jetzt das erste Element der Liste) und weise den Listenanfang jetzt den neuen Knoten zu .

- falls aber die Artikelnummern des ersten Knotens und die des neuen Knotens gleich sind, so addiere die Anzahl des neuen Knotens zum alten dazu und lösche dann node indem du seinen Speicher frei gibst


Das letzte Else ist ab der while schleife nicht mehr Verständlich gewesen

 

[simpsonsfan]

Da entweder was beim Abtippen der Musterlösung schief gelaufen, oder aber diese grauenhaft und auch nicht funktionstüchtig ist, hier mal eine funktionierende Lösung von mir:

void insert (node_t **list, node_t* insertNode)
{
    //Liste ist leer
    if(*list == NULL)
    {
        *list = insertNode;
        return;
    }
    
    //Der Knoten muss neuer Kopf werden
    if((*list)->data.nummer  >  insertNode->data.nummer)
    {
        insertNode->next = *list;
        *list = insertNode;
        return;
    }
        
    //Der Knoten muss mit einem bestehenden Knoten verschmolzen oder weiter hinten eingefügt werden
    node_t* currentNode = *list; //betrachte als ersten Knoten den Listenkopf
    node_t* nextNode = (*list)->next;
    while(1) //Endlosschleife, wird mit return beendet
    {
        //Verschmelzen mit dem aktuellen Knoten
        if(currentNode->data.nummer == insertNode->data.nummer)
        {
            currentNode->data.anzahl += insertNode->data.anzahl;
            free(insertNode);
            return;
        }
        
        //Einfügen am Ende der Liste
        if(nextNode == NULL)
        {
            currentNode->next = insertNode;
            return;
        }
        
        //Einfügen zwischen jetzigem und nächstem Knoten
        if(nextNode->data.nummer > insertNode->data.nummer)
        {
            currentNode->next = insertNode;
            insertNode->next = nextNode;
            return;
        }
        
        //knoten wurde in dieser Schleifeniteration nicht verarbeitet, einen Knoten weiter springen
        currentNode = nextNode;
        nextNode = nextNode->next;
    }
}

Die Verwendung in der main wäre dann bspw.

int main()
{
    node_t *liste = createlist(); 
    //liste = newElement(1, "schwarz", 10); //syntaktisch zulässig für das allererste Listenelement  

    insert(&liste, newElement(1, "schwarz", 10));
    insert(&liste, newElement(2, "lila", 8));
    insert(&liste, newElement(3, "rot", 20));
    insert(&liste, newElement(3, "rot", 20));
    insert(&liste, newElement(2, "lila", 1));
    insert(&liste, newElement(0, "gruen", 1));

    printListe(liste);

    return 0;
}

[...] die main die ich geschrieben habe, lässt sich ausgeben

Ich bezog mich auf den oberen Codeblock, in welchem newElement keinen zusätzlichen Pointer als Argument erhält.

 

[Multivac]

P.S. ich weiss, dass in der Aufgabenstellung gefordert war, einen String in der Größe von 42 Zeichen zu deklarieren, aber in der Klausur muss ich auf alle Eventualitäten eingestellt sein.

Spoiler: ISO/IEC 9899:1999 (E)

ISO/IEC 9899:1999 (E)
6.2.4 Storage durations of objects
3 An object whose identifier is declared with external or internal linkage, or with the storage-class specifier static has static storage duration. Its lifetime is the entire execution of the program and its stored value is initialized only once, prior to program startup.

6.4.5 String literals
5 In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals.65) The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence. ...

Strings die mit scanf gelesen werden müssen von dir gespeichert werden du kontrollierst selbst die dauer.

@simpsonsfan
Jetzt solltest du ihn noch ** und & erklären.

Die insert function sollte zwei geteilt werden in eine "finde die richtige stelle" und "einfügen an dieser stelle". Du wirst sonst Code duplizieren und Sie sind leichter zu verstehen.

 

[simpsonsfan]

Jetzt solltest du ihn noch ** und & erklären.

Die sollten aus den Vorlesungen zu den Pointern hoffentlich schon bekannt sein, der Doppelpointer kam ja auch in der "Musterlösung" vor. Nichtsdestotrotz an dieser Stelle noch mal die Kurzfassung:
node_t** list kennzeichnet hier list als einen Doppelpointer, also einen Pointer auf einen Pointer auf node_t.
& ist der Adress-Operator, &liste gibt hier also die Speicheradresse von head an.

 

[WIng93]

Also die Funktionsweise von Doppelpointer ist mir bekannt . Meine Frage ist eher wieso nutzen wir einen Pointer auf einen Pointer ? Hätten wir nicht einen "einfachen" Pointer dafür verwenden können ?

 

[simpsonsfan]

Nein, da du ja den Pointer ändern willst. Veranschauliche es dir am besten an einem Beipiel:
Ausgangspunkt: Wir haben noch keine Elemente. Der Pointer liste zeigt auf NULL (also die Speicheradresse 0x0000). Der Pointer liste selbst liege im Speicher an der (von mir willkürlich gewählten) Adresse 0x1B75. Nun legst du in der newElement Funktion einen neuen Knoten an, für den du mit new Speicher anforderst. Als Beispiel liegt der neu angeforderte Speicherbereich jetzt bei Adresse 0x3FA1 (ebenfalls willkürlicher Wert).
Diese Adresse übergibst du der Funktion insert. Wunschergebnis ist, dass nach Ablauf der Funktion der Pointer liste ebenfalls auf die Adresse des neuen Knotens (namentlich 0x3FA1) zeigt, und nicht mehr auf NULL. Du musst also den Pointer liste ändern.
Würdest du an insert nun liste (Als Zahlenwert 0x0000) übergeben (statt mit &liste die Adresse [0x1B75] von liste), so hättest du keine Möglichkeit, liste zu ändern. Dein Funktionsaufuf wäre dann nämlich mit bereits eingesetzten Werten für die Argumente:

insert(0x0000, 0x3FA1)

Wenn du jetzt den Wert 0x0000 an der Speicheradresse 0x1B75 auf 0x3FA1 ändern willst, kannst du das nicht, weil du ja die Adresse 0x1B75 gar nicht kennst. Ist dein Funktionsaufruf hingegen

insert(0x1B75, 0x3FA1)

, so kannst du sagen "ändere den Wert an der Speicheradresse 0x1B75 (von 0x0000) auf 0x3FA1.

Eine alternative Möglichkeit ohne den Doppelpointer wäre sonst nur die Rückgabe des Listenkopfs als Funktionsrückgabewert, also

liste = insert(liste, newElement(1, "schwarz", 10))

Was in einem Funktionsaufruf als Argument steht, kannst du nicht ändern, das ist immer eine Kopie des Wertes, den du da reinschreibst. Über den Pointer kannst du aber sagen, "nenne mir die Adresse, an der dieser Wert steht" und später "ändere den Wert, der an dieser Adresse steht".