Wie soll ich malloc/realloc mit einer Struktur machen, die ein Array enthält?

Question

Ich bin ziemlich neu in C, also wenn meine Schritte falsch sind, lassen Sie es mich bitte wissen. Angenommen, ich habe etwas Ähnliches wie:

struct graphNode{
    int val;
    graphNode* parent;
    int succSize;
    int succMaxSize;
    graphNode* succ[1];
};

Ich werde einen neuen Knoten erstellen mit:

graphNode *n;
n = malloc(sizeof(struct graphNode));
assert(n);
n->val = 1;
n->parent = NULL;
n->succSize = 0;
n->succMaxSize = 1;

Dann, wenn ich einen Nachfolger zum Knoten hinzufügen möchte

if (n->succSize == n->succMaxSize){
    n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
    n->succMaxSize *= 2;
} 
n->succ[succSize] = n2; //n2 ist vom Typ graphNode*
succSize++;

Ist das korrekt? Muss ich auch für das struct realloc verwenden oder reicht realloc des Arrays aus? Müsste ich für das anfängliche Array malloc verwenden? Sollte die anfängliche Arraygröße bei meinem malloc-Aufruf für n enthalten sein?

Answer 1

Die übliche Möglichkeit, ein "dehnbares" Array-Mitglied in C zu definieren, besteht darin, entweder eine Größe von 0 anzugeben oder überhaupt keine Größe anzugeben, z.B.:

struct foo {
    int stuff;
    bar theBars[]; // oder theBars[0]
};

Mit dieser Definition wird sizeof(struct foo) alle Elemente außer dem Array am Ende enthalten, und Sie können die richtige Größe allozieren, indem Sie malloc(sizeof(struct foo) + numberOfBars * sizeof(bar)) angeben.

Wenn Sie es neu zuweisen müssen, um die Anzahl der bar-Elemente zu ändern, verwenden Sie dieselbe Formel (aber mit einer neuen numberOfBars).

Zur Klarstellung: Sie können nicht einfach einen Teil einer Struktur mit realloc. Sie müssen das gesamte Ding realloc.

Answer 2

realloc(ptr,size) benötigt 2 Parameter, nicht nur 1, wie in realloc(sizeof(graphNode*) * n->succMaxSize * 2) verwendet.

// Etwas wie ...
graphNode *n;
n->succSize = 0;
n->succMaxSize = 0; // auf 0 gesetzt
n->succ = NULL;  // Auf NULL initialisieren

// Dann, wenn OP einem Nachfolgerknoten hinzufügen möchte
if (n->succSize <= n->succMaxSize){
  n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
  n->succMaxSize *= 2;
} 
n->succ[succSize++] = n2;

---

Wie bei allen Speicherzuweisungen, sollte auf eine Rückgabe von NULL überprüft werden. Bei realloc() sollte der ursprüngliche Wert gespeichert werden, damit bei einem Fehlschlag von realloc() der ursprüngliche Zeiger nicht verloren geht.

Answer 3

Normalerweise bedeutet es, wenn Sie eine Strukturdefinition sehen, bei der das letzte Feld ein Array der Größe 0 oder 1 ist, dass der Autor beim Allozieren der Struktur mit malloc einige subtile Dinge tun wird.

Zum Beispiel

struct foo {
   int x;
   :
   : 
   type a[0];
};

Mit einem malloc wie

  struct foo *p = malloc(sizeof(*p) + (n * sizeof(type));

Was dies macht, ist, dass es einen zusammenhängenden Speicherbereich für die Struktur und das nachfolgende Array zuweist. In diesem Fall hat das Array die Größe n. Verweise auf das Array sehen in diesem Fall so aus:

p->a[i] // wobei i >= 0 und i < n

Ein Grund dafür ist Speicherplatz zu sparen.

Sicherlich gibt es bessere Erklärungen dafür auf StackOver; es ist eine sehr verbreitete C-Idiomatik.

Es wird im Allgemeinen nicht verwendet, wenn das Array dynamisch ist. Es wird eher verwendet, wenn die Größe des Arrays zum Zeitpunkt von malloc() bekannt ist. Natürlich können Sie es dynamisch verwenden, aber Sie müssen den gesamten Speicherbereich neu zuweisen, nicht nur die Struktur oder das Array alleine. Um die Größe auf 2n zu erhöhen, würden Sie sagen

  p = realloc(p, sizeof(*p) + (2 * n * sizeof(type)));

Jetzt ist Ihr Array doppelt so groß wie zuvor, und es ist immer noch ein zusammenhängendes Speicherstück.

Answer 4

Wenn Sie nur ein einzelnes Array möchten, machen Sie succ einfach zu einem einzelnen Zeiger und verwenden Sie nur malloc/realloc usw., um Speicher für das Array zuzuweisen.

graphNode* succ;

Was Sie tun, wird höchstwahrscheinlich fehlschlagen.

Answer 5

Ich bin auch neu in C, aber es gibt einige Dinge, die ich sofort erkennen kann. Erstens kann man Arrays nicht neu zuweisen. In c89 sind sie zur Compile-Zeit festgelegt. In C99 und C11 können sie dynamisch zugewiesen werden, aber nicht neu zugewiesen (so weit ich weiß). Daher müssen Sie für dies einen graphnode *succ; Zeiger zuweisen und malloc(nodes * sizeof(node)).

graphNode* succ[1];

Dies erstellt ein Array der Größe eins, nicht ein Array mit einem maximalen Index von eins. Also ist es (fast) funktional dasselbe wie graphNode* succ;, außer dass Sie seine Größe nicht ändern können, nachdem Sie es erstellt haben.

Ich glaube, dass Sie einen Baum erstellen möchten, mit einer dynamisch neu zuweisbaren Anzahl von Zweigen. In diesem Fall müssen Sie nur die Größe des graphNode* pointer neu zuweisen und dann auf jedes Element über den Index zugreifen, als würden Sie auf ein Array zugreifen.