malloc() und Lineare Listen

zoro

Kann mir jemand mal einfach erklären wann ich malloc() benötige bei linearen Listen, habe das Gefühl das bei vielen Beispielen die ich im Internet gesehen habe die das willkürlich machen, manchmal machen sies manchmal nicht....

TyRoXx

zoro schrieb:

habe das Gefühl das bei vielen Beispielen die ich im Internet gesehen habe die das willkürlich machen

Was genau machen die?

zoro schrieb:

Kann mir jemand mal einfach erklären wann ich malloc() benötige bei linearen Listen, habe das Gefühl das bei vielen Beispielen die ich im Internet gesehen habe die das willkürlich machen, manchmal machen sies manchmal nicht....

Swordfish

zoro schrieb:

Kann mir jemand mal einfach erklären wann ich malloc() benötige bei linearen Listen, [...?]

Immer dann, wenn ihr bereits alloziierter Speicher nicht mehr ausreicht.

zoro

Zum Beispiel:

int ElementEinfuegen(struct LinListe *root, struct LinListe *Neu)
  {
  struct LinListe *Tail;
  usw....
return 1;

*root sei die schon gesamte vorhandene Liste, *Neu sei das neu anzuhängende Element sein, und *Tail sei der Zeiger zum referieren der Elemente. Warum wird hier *Tail nich mit = malloc(sizeof(struct LinListe)); initialisiert?

dachschaden

zoro schrieb:

*root sei die schon gesamte vorhandene Liste, *Neu sei das neu anzuhängende Element sein, und *Tail sei der Zeiger zum referieren der Elemente. Warum wird hier *Tail nich mit = malloc(sizeof(struct LinListe)); initialisiert?

Wäre ungut, wenn tail referieren würde - damit willst du doch dereferenzieren. :p

Außerdem, warum sollte man?

int ElementEinfuegen(struct LinListe*root,const struct LinListe*const Neu)
{
    struct LinListe *Tail;

    if(!root || !Neu)
        return EFAULT;

    /*An den Anfang der Liste gehen.*/
    Tail=root;

    /*Durchgehen, bis wir am Ende sind.*/
    while(Tail->next)
    {
        Tail=Tail->next;
    }

    /*Ende erweitern, indem wir Speicher vom Heap holen, und dann zuweisen.*/
    Tail->next=malloc(sizeof(*Tail->next));
    *Tail->next=*Neu;

    /*0 gibt man nur als Anfaenger oder wenn die Funktion keinen wirklichen
    **Fehlercode raushauen KANN zurück.*/
    return 0;
}

Gerade dahingehackt, und das könnte man noch schöner machen (indem man auf Tail ganz verzichtet und stattdessen nur root durchgeht). Aber das generelle Konzept bleibt das gleiche.

zoro

Ok das verstehe ich.
Aber warum kann ich nicht auch einfach:

Tail->next = Neu;

machen?

anstatt:

Tail->next=malloc(sizeof(*Tail->next));
    *Tail->next=*Neu;

abgesehen von *, weil ich immer nur mit Adressen arbeite^^

Danke im voraus!

zoro

Das ist mein eigentlicher Code, zum einsortieren von Elementen in die Liste
aber ich bin mir nicht sicher ob ich *Tail mit malloc vorbelegen muss^^

struct LinListe *ElementEinfuegen(struct LinListe *root, struct LinListe *Neu)
  { 
  struct LinListe *Tail;
  /* Wenn Neu das erste Listenelement werden muss, */
  /*dann ist die globale Variable root zu aendern */

  if (root == NULL)
    /*Liste noch leer, erstes Element, root wird neues Element */
    root = Neu;
  else if (strcmp(Neu->inhalt, root->inhalt) < 0)
    /* Einfuegen vor dem ersten Element, root aendert sich */
    {
    Tail = root;
    root = Neu;
    Neu->next = Tail;
    }
  else
    {
    Tail = root;
    /* Element suchen, nach dem Neu einzuhaengen ist */
    while ((Tail->next != NULL) && (strcmp(Tail->next->inhalt, Neu->inhalt) < 0)) 
      /*Reihenfolge beachten: erst auf NULL testen */
      Tail = Tail->next;
    /* Neu nach Tail einhaengen */
    Neu->next = Tail->next;
    Tail->next = Neu;
    }
  return(root);
  }

Danke nochmal!

dachschaden

zoro schrieb:

Ok das verstehe ich.
Aber warum kann ich nicht auch einfach:
Tail->next = Neu;
machen?

anstatt:
Tail->next=malloc(sizeof(*Tail->next));
    *Tail->next=*Neu;

Überleg mal: wenn das Objekt, auf das Neu zeigt, aus irgendeinem Grund verloren geht (weil, sagen wir mal, der Programmierer ein Objekt auf dem Stack erstellt, und dann deine Funktion mit dem Objekt aufruft, und da die Adresse gespeichert wird, und danach die Funktion zurückkehrt). Dann ist das Objekt weg, und dein Zeiger zeigt ins Nirvana. Und nicht in die gute Art von Nirvana (NULL), sondern in die böse Art von Nirvana - der, der man nicht ansieht, dass sie ins Nirvana zeigt.

Deswegen macht man in der Regel eine tiefe Kopie des Objekts innerhalb der Routine. Das ist aber für manche Anwendungsgebiete echt langsam (einmal malloc kann mehrere tausend Prozessorcycles einfach so verhauen!). Deswegen sollte man (meine Meinung zumindest) zwei Funktionen beifügen: eine, die das Objekt kopiert, und eine, die es direkt speichert. Damit faule Programmiere ihre Sachen auf dem Stack verwalten und gute Programmiere eine ordentliche Speicherverwaltung hinter der Liste aufbauen können.