Aufgabenstellung: Fehlerfinden

Ich habe hier ein kleines Programm uns soll erklären, warum kein Element hinzugefügt wird. Ich komm aber einfach nicht drauf:

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

struct node {
  int wert;
  struct node *next;
};

void insert(struct node *root, int wert) {
  if(root == NULL) {
    puts("Root ist Null, also Element anlegen...");
    root = (struct node*) calloc(1,sizeof(struct node));
    root-> wert = wert;
    root->next=0;
  }else{
    puts("Noch ein Element weiter wandern....");
    insert(root->next, wert);
  }
}

int main() {
  struct node *root = NULL;
  struct node *current = root;
  insert(root, 5);
  \\und Ausgeben
  if (root != NULL) {
    puts("Es existiert ein Element");
    printf("%d",root->wert);
  } else {
    puts("Kein Element angelegt");
  }
  return 0;
}

Weil der Funktion insert() der Zeiger root als Kopie übergeben wird. Dadurch wird zwar in der Funktion Speicher reserviert usw., aber nach verlassen der Funktion hat der Zeiger root (im Scope von main()) immernoch den Wert NULL.

Aha! Das verstehe ich, klingt logisch, aber warum funktioniert dann dieser Kode, den ich für eine andere Aufgabe selber geschrieben habe, wunderbar?

int fuelleBaum(struct Knoten* Baum, char string[20])
{
  // ist der in den Baum einzufuegende String "kleiner" als der im aktuellen Knoten, steigen wir links ab
  if(strcmp(string, (*Baum).name)==-1)
  {
    // ist der Platz links frei, erstellen wir einen neuen Knoten mit dem String
    if((*Baum).links==NULL)
    {
      struct Knoten* Blatt;
      Blatt = (struct Knoten*) calloc (1,sizeof(struct Knoten));
      strcpy((*Blatt).name, string);
      (*Blatt).rechts = NULL;
      (*Baum).links = Blatt;
      return 0;
    }
    // ist der Platz nicht frei, steigen wir weiter nach link ab
    else
    {
      fuelleBaum((*Baum).links, string);
    }

    return 1;
  }

  // ist der in den Baum einzufuegende String "groesser" als der im aktuellen Knoten, steigen wir rechts ab
  if(strcmp(string, (*Baum).name)==1)
  {

    // ist der Platz rechts frei, erstellen wir einen neuen Knoten mit dem String
    if((*Baum).rechts==NULL)
    {
      struct Knoten* Blatt;
      Blatt = (struct Knoten*) calloc (1,sizeof(struct Knoten));
      strcpy((*Blatt).name, string);
      (*Blatt).links = NULL;
      (*Baum).rechts = Blatt;
      return 0;
    }
    // ist der Platz nicht frei, steigen wir weiter nach rechts ab
    else
    {
      fuelleBaum((*Baum).rechts, string);
    }

    return 1;
  }

  // es scheint ein Fehler aufgetreten zu sein, wahrscheinlich ist der String schon im Baum enthalten
  return 1;
}

Weil offenbar für "Baum" schon vor Aufruf der Funktion Speicher reserviert wurde.

Das kann ich dir sagen:

struct Knoten* Wurzel;
  Wurzel = (struct Knoten*) calloc (1,sizeof(struct Knoten));
  fgets(string, 20, fp);
  strcpy((*Wurzel).name, string);
  (*Wurzel).links=NULL;
  (*Wurzel).rechts=NULL;

Für "Baum", also in diesem Fall "Wurzel" wurde schon Speicher reserviert, ja, aber für Baum.links und Baum.rechts nicht, und darum geht es ja.

Ich will verstehen warum es nicht geht, aber nach deiner Theorie dürfte mein älterer Kode auch nicht gehen.

supertux

fabske schrieb:

Ich will verstehen warum es nicht geht, aber nach deiner Theorie dürfte mein älterer Kode auch nicht gehen.

Nein, du musst einfach verstehen, wie Argumente übergeben werden. In C gibt es keinen Call-by-Reference im klassischen Stil (wie bei C++), sondern gibt es nur Call-By-Value, weil immer nur Kopien übergeben werden.

Mit Zeigern kannst du das Call-by-Reference nachmachen, weil du über die Adresse einer Variable ihren Inhalt verändern kannst. Betrachte

void foo(int x)
{
  x = 10;
}

void bar(void)
{
    int u = 9;
    foo(u);
    printf("u = %d\n", u);
}

Die Ausgabe ist 9, weil du nur eine Kopie von u übergibst.

void foo(int *x)
{
  *x = 10;
}

void bar(void)
{
    int u = 9;
    int *ptr = &u;
    foo(ptr);
    printf("u = %d\n", u);
}

Hier ist die Ausgabe 10, weil du einen Zeiger auf u übergeben hast, d.h. d'foo' kann über die übergebene Speicheradresse direkt den Wert verändern. Aber an dieser Stelle hat man ebenfalls eine Kopie des Zeigers übergebenm, d.h. 'x' ist eine Kopie von 'ptr', Änderungen am Inhalt von 'x' werden von 'ptr' nicht wahrgenommmen, wie im ersten Beispiel. Wenn du die Adresse ändern willst, worauf ein Zeiger zeigt, dann musst du den Inhalt der Zeigervariable ändern, somit musst du einen Zeiger für den Zeiger bekommen.

Das hier verhält sich genau wie im ersten Beispiel

/* Annahme, malloc liefer NIE NULL */
void foo(int *x)
{

  x = malloc(sizeof(int));
  *x = 10;
}

void bar(void)
{
    int u = 9;
    int *ptr = &u; 
    foo(ptr);
    printf("u = %d\n", *ptr);
}

Man hat zwar einen Zeiger übergeben. 'foo' kann über diesen Zeiger den Inhalt von 'u' verändern, aber 'x' ist eine Kopie von 'ptr' und deswegen merkt 'ptr' nicht, dass seine Kopie sich geändert hat. Und das ist genau, was du in deiner insert Funktion hast.

/* Annahme, malloc liefer NIE NULL */
void foo(int **x)
{

  /* Damit änderst du, worauf ptr zeigt */
  *x = malloc(sizeof(int));

  /* damit änderst du den Inhalt an der Adresse, worauf ptr zeigt */
  **x = 10;
}

void bar(void)
{
    int u = 9;
    int *ptr = &u; 
    foo(&ptr);
    printf("u = %d\n", *ptr);
}

Hier ist die Ausgabe tatsächlich 10, weil man jetzt den Inhalt des Zeigers verändert hat und somit zeigt der Zeiger irgendwo anders zeigt.

So, jetzt fragst du dich, warum mit dem Baum funktioniert? Die Antwort ist ganz einfach:

Baum zeigt bereits irgendwo, d.h. du veränderst den Inhalt des Zeigers (und damit worauf der Zeiger zeigt) nicht!
Baum->links bzw. Baum->rechts können von mir aus auf NULL zeigen, aber die werden nicht als Kopie übergeben, sondern greifst du über die Adresse zu, die im Zeiger 'Baum' enthalten ist. Die Elemente eines structs sind davon nicht betroffen, dafür sind Zeiger da. Im Gegensatz zur 'Baum' Variable, werden Baum->rechts und Baum->rechts [n]nicht[/b] als Zeiger übergeben. Sie sind im diesem Fall völlig transparent, denn du veränderst nur den Inhalt an der Speicherstelle, worauf 'Baum' zeigt aber nicht die Adresse, worauf 'Baum' zeigt.

Btw: wieso sehe ich hier öfters diese krumme Schreibweise (*Baum).elemente statt Baum->element? Was soll das? sowas kann man nicht lesen.

//edit: Fehler korrigiert, danke Sterngucker

supertux schrieb:

/* Annahme, malloc liefer NIE NULL */
void foo(int *x)
{
  *x = malloc(sizeof(int));
  *x = 10;
}

in der ersten zeile der funktion muss das sternchen weg.

supertux

jo, danke. Ist mir beim Copy&Paste kleiner Fehler unterlaufen.