Frage Zeiger eines Zeigers in verknüpfter Liste anhängen


Ich programmiere normalerweise in Python. Um die Leistung meiner Simulationen zu erhöhen, lerne ich C. Ich habe ein Problem zu verstehen, die Verwendung eines Zeigers eines Zeigers beim Implementieren der Append-Funktion zu einer verknüpften Liste. Dies ist ein Auszug aus dem Code aus meinem Buch (Understanding Pointers in C von Kanetkar).

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

struct node{
    int data;
    struct node *link;
};

int main(){
    struct node *p; //pointer to node structure
    p = NULL;   //linked list is empty

    append( &p,1);
    return 0;
}

append( struct node **q, int num){
    struct node *temp, *r;  //two pointers to struct node
    temp = *q;

    if(*q == NULL){
        temp = malloc(sizeof(struct node));
        temp -> data = num;
        temp -> link = NULL;
        *q = temp;
    }
    else{
        temp = *q;
        while( temp -> link != NULL)
            temp = temp -> link;
        r = malloc(sizeof(struct node));
        r -> data = num;
        r -> link = NULL;
        temp -> link = r;
    }
}

In diesem Code gebe ich den Doppelzeiger ** q an die Append-Funktion weiter. Ich bekomme, dass dies die Adresse der Adresse, d. H. Die Adresse von NULL in diesem Fall ist.

Ich verstehe einfach nicht Warum Man macht es so. Wäre es nicht zulässig, einen * Operator von allem in der append () Funktion zu entfernen und einfach die Adresse von NULL (d. H. P anstelle von & p) an die append () Funktion zu übergeben?

Ich habe diese Frage gegoogelt. Die Antworten sind entweder zu schwer zu verstehen (da ich nur ein C-Anfänger bin) oder zu einfach. Ich bin dankbar für Hinweise, Kommentare oder Links, wo ich darüber nachlesen kann.


7
2018-03-06 10:12


Ursprung


Antworten:


Wenn Sie Dinge an Funktionen in C übergeben, sei es ihre Variablen oder Zeiger, handelt es sich um eine Kopie des Originals.

Schnelles Beispiel:

#include <stdio.h>
void change(char *in)
{
    // in here is just a copy of the original pointer.
    // In other words: It's a pointer pointing to "A" in our main case 
    in = "B";
    // We made our local copy point to something else, but did _not_ change what the original pointer points to.
}
void really_change(char **in)
{
    // We get a pointer-to-a-pointer copy. This one can give us the address to the original pointer.
    // We now know where the original pointer is, we can make _that one_ point to something else.
    *in = "B";
}
int main(int argc, char *argv[])
{
    char *a = "A";
    change(a);
    printf("%s\n", a); /* Will print A */
    really_change(&a);
    printf("%s\n", a); /* Will print B */
    return 0;
}

Also der erste Funktionsaufruf an change() wird eine Kopie eines Zeigers an eine Adresse übergeben. Wenn wir es tun in = "B" Wir ändern uns nur das Kopie des Zeigers, den wir erhalten haben.

Im zweiten Funktionsaufruf really_change()erhalten wir eine Kopie eines Pointer-to-a-pointer. Dieser Zeiger enthält die Adresse zu unserem ursprünglichen Zeiger und voila, wir können jetzt auf den ursprünglichen Zeiger verweisen und ändern, worauf der ursprüngliche Zeiger zeigen sollte.

Hoffentlich erklärt es das etwas mehr :)


16
2018-03-06 10:22



Erstens ist es nicht "die Adresse der Adresse". Es ist die Adresse einer Zeigervariablen. Bsp .: Wenn Sie die Adresse eines int Variable n das enthält Null, Sie übergeben die Adresse von Null nicht; Sie übergeben die Adresse einer Variablen (in diesem Fall ein int Variable, in Ihrem Fall eine Zeigervariable). Variablen haben Adressen im Speicher. Der Parameter ist in diesem Fall die Adresse einer Variablen, bei der es sich um eine Zeigervariable handelt, den Kopf Ihrer Liste.

In Bezug darauf, warum man das macht? Einfach. Alle Variablen in C (Arrays über Pointer-Decay werden nicht bestanden) werden übergeben Wert. Wenn Sie etwas nach Referenz (Adresse) ändern möchten, muss der zu übergebende "Wert" eine Adresse sein und der formale Parameter, der ihn empfängt, muss ein Zeigertyp sein. Kurz gesagt, Sie geben an, dass der "Wert" eine Speicheradresse und nicht nur ein einfacher Skaliererwert übergeben wird. Die Funktion verwendet dann (über einen formalen Zeigerparameter) Daten entsprechend zu speichern. Stellen Sie es sich so vor, als ob Sie "dieses Ding, das ich wollte" in diese "Speicheradresse" schreiben.

Nehmen wir als kleines Beispiel an, dass Sie eine Datei durchlaufen möchten, indem Sie jedes Zeichen in eine Datei einfügen nach vorne verknüpfte Liste von Knoten. Du würdest nicht Verwenden Sie eine Append-Methode wie die, die Sie haben (siehe Der Algorithmus des Malers warum). Sehen Sie, ob Sie diesem Code folgen können, der einen Zeiger auf Zeiger, aber keinen Funktionsaufruf verwendet.

typedef struct node
{
    char ch;
    struct node *next;
} node;


node *loadFile(const char *fname)
{
    node *head = NULL, **next = &head;
    FILE *fp = fopen(fname, "r");
    if (fp)
    {
        int ch;
        while ((ch = fgetc(fp)) != EOF)
        {
            node *p = malloc(sizeof(*p));
            p->ch = ch;
            *next = p;
            next = &p->next;
        }
        *next = NULL;
        fclose(fp);
    }
    return head;
}

Stehe eine Weile darauf und schau, ob du den Zeiger auf den Zeiger verstehen kannst next wird verwendet, um den nächsten verknüpften Knoten, der der Liste hinzugefügt werden soll, beginnend mit dem Kopfknoten, immer zu füllen.


6
2018-03-06 10:22



Sie müssen es auf diese Weise tun, damit die Funktion den Speicher zuordnen kann. Vereinfachung des Codes:

main()
{
  void *p;
  p = NULL;
  funcA(&p);

  int i;
  i = 0;
  funcB(&i);
}

funcA(void **q)
{
  *q = malloc(sizeof(void*)*10);
}

funcB(int *j)
{
  *j = 1;
}

Dieser Code ist auf diese Weise so die Unterfunktion funcA kann das zuordnen p Zeiger. Betrachten Sie zunächst einmal void* p als ob es wo wäre int i. Was machst du damit? p = NULL ist in gewisser Weise ähnlich int i = 0. Jetzt, wenn du passierst &i Sie übergeben die Adresse nicht 0Übergeben Sie die Adresse von i. Das gleiche passiert mit &p Sie übergeben die Adresse des Zeigers.

Jetzt in FuncA, möchten Sie die Zuweisung machen, also Sie verwenden malloc aber wenn du es würdest q = malloc(... und q wäre gewesen void* q in der Hauptfunktion wäre p nicht zugewiesen worden. Warum? Denk an funcB, j hält die Adresse von i, wenn Sie ändern möchten, würden Sie dann tun *j = 1, denn wenn du es würdest j = 1 dann hättest du j auf eine andere Speicherregion anstelle von i zeigen lassen. Genauso ist es mit q für funcA. denke darüber nach <type of p>* q es ist ein Zeiger auf den Typ von p, der void * ist, aber im Falle von funcB ist es ein int. Jetzt wollen Sie die Adresse ändern, auf die p zeigt, das heißt, dass Sie nicht die Adresse ändern wollen, auf die q zeigt, Sie wollen die Zeigeadresse ändern, auf die q zeigt, aka *q oder p.

Wenn es noch nicht klar ist. Denk an Boxen. Ich habe ein kurzes Beispiel mit der Funktion der betroffenen Boxen gezeichnet. Jede Box hat einen Namen (innerhalb der Box), diese Box befindet sich im virtuellen Speicher des Prozesses an einer beliebigen Adresse, und jede Box enthält einen Wert. In dieser Sicht sind wir in dem Zustand, in dem die funcA(&p) wurde aufgerufen und der malloc wird fertig sein.

enter image description here


3
2018-03-06 10:43



Hey, warum denkst du es auf diese Weise, denke, wenn jemand Struktur passiert, um Funktion anzuhängen, in diesem Fall ganze Struktur struct node{int data; struct node *link; }; in Ihrem Fall wird auf Stapelrahmen von kopiert append functionEs ist also besser, die Adresse des Strukturzeigers zu übergeben, damit nur 4 Bytes auf den Stack kopiert werden.


2
2018-03-06 10:23



Sie brauchen das if / else nicht; In beiden Fällen verknüpfen Sie den neuen Knoten mit einem Zeiger, der vor der Operation NULL war. Dies könnte der Wurzelknoten oder der -> nächste Knoten des letzten Knotens in der Kette sein. Beide sind Zeiger auf den Strukturknoten und Sie benötigen a Zeiger zu diesen Zeigern, um ihnen zuzuordnen.

void append( struct node **q, int num){

    while (*q){ q = &(*q)->link; }

    *q = malloc(sizeof **q);
    (*q)->data = num;
    (*q)->link = NULL;

}

Warum sollte jemand das tun? Grundsätzlich, weil es kürzer ist, verwendet es nur eine Schleife und keine zusätzlichen Bedingungen, verwendet keine zusätzlichen Variablen und es kann bewiesen werden, dass es korrekt ist. Es sollte natürlich ein Test für das Ergebnis von malloc hinzugefügt werden, der eine zusätzliche Bedingung benötigt.


2
2018-03-06 10:36



Im Wesentlichen, wie Jite und die anderen sagten, ist richtig.

Wann immer Sie eine Änderung auf eine Datenstruktur in C anwenden möchten (Änderung durch eine andere Funktion), müssen Sie eine "Referenz" an diese Datenstruktur übergeben, damit die Änderung erhalten bleibt, nachdem die Funktion change () abgeschlossen wurde. Dies geschieht auch in Python. Sie übergeben Verweise auf Objekte, es sei denn, Sie erstellen explizit eine Kopie. In C müssen Sie angeben, was genau Sie tun möchten. Um es noch mehr zu vereinfachen, ist es entweder:

Geben Sie data_struct ein

change (data_struct) => hier ist eine Kopie von meinem data_struct, mache deine Änderung, aber es interessiert mich nicht in der Caller-Funktion über die Änderung, die du anwendest

oder

change (& data_struct) => hier ist die Adresse (ein "Verweis" auf) von meinem data_struct, wenden Sie Ihre Änderung an, die Caller-Funktion wird diese Änderung sehen, nachdem es angewendet wird.

Je nachdem, was der ursprüngliche "Typ" ist, könnten Sie nun * oder ** haben. Denken Sie jedoch daran, dass es eine Grenze gibt für wie viele "Rückwege" Sie haben können, nicht sicher, ob es System oder Compiler ist, wenn jemand eine Antwort darauf hat, dass ich ein Nehmer bin. Ich hatte nie mehr als 3 Rückweisungen.


1
2018-03-06 10:36



Ich denke, Grund ist wie folgt:

Strukturknoten * p; // Zeiger auf Knotenstruktur     p = NULL;

Oberhalb des Schnipsels, wenn in den Hauptblock geschrieben, bedeutet der Wert des Zeigers p NULL, so dass er nicht auf irgendwas im Speicher zeigt. So übergeben wir die Adresse des Zeigers p, um einen neuen Knoten zu erzeugen, und weisen die Adresse des neuen Knotens dem Wert des Zeigers p zu.

* (& p) == * q == temp;

Mit * q == temp; wir erreichen unser Ziel, dem Zeiger p, der ursprünglich nirgendwohin zeigte, einen Wert zuzuordnen.


0
2017-12-17 17:40