Enqueue-Funktion in verketteten Liste

Question

Ich versuche, die Funktion "enqueue" mein Professor zu verstehen, aber ich bekomme keine Schritte.

struct queue_node { 
int item; 
struct queue_node* next; 
}; 
typedef struct queue_node* queue; 


int enqueue (queue* tail, int i) { 
queue n; 
queue *iter; 
n = (queue)malloc(sizeof(struct queue_node)); 
if (!n) return 1; 
n->item = i; 
n->next = NULL; 
for (iter=tail; *iter != NULL; iter = &((*iter)->next) 
; 
*iter = n; 
return 0; 
} 

Erstens, dass "typedef struct queue_node * queue;" ist verwirrend mich so habe ich versucht, den Code auf diese Weise (bitte korrigieren Sie den Code, wenn ich falsch liege) neu zu interpretieren

die Lösung meines Professor habe ich versucht, eine „enqueue zu tun, bevor Sie versuchen

struct queue_node { 
int item; 
struct queue_node* next; 
}; 
typedef struct queue_node queue; 

int enqueue (queue **tail, int i) { 
queue *n; 
queue **iter; 
n = (queue)malloc(sizeof(struct queue_node)); 
if (!n) return 1; --->what does that mean? 
n->item = i; 
n->next = NULL; 
for (iter=tail; **iter != NULL; iter = &((*iter)->next)--->last part of the for is unclear to me... can i rewrite it as "iter = **((iter)->next)"? 
; 
*iter = n; -->this is the part i don't really get... 
return 0; 
} 

So durch die Art und Weise zu lesen "Funktion auf eigene Faust

typedef struct node{ 
int value; 
struct node *next; 
}node; 

void enqueue(node *head,int data){ 
if(head->next != NULL){ 
enqueue(head->next,data); 
} 
node *new=NULL; 
new=malloc(sizeof(node)); 
new->value=data; 
new->next=NULL; 
head->next=new; 
} 

Ist das gut? oder ich kann es nicht benutzen? Vielen Dank an alle im Voraus für die Hilfe

Answer 1

Die typedef struct queue_node* queue; einen neuen Typ definiert, so dass Sie

queue* myqueue = (queue*)malloc(sizeof(struct queue_node)); 

statt

struct queue_node** myqueue = (struct queue_node**)malloc(sizeof(struct queue_node)); 

Wie wies darauf hin, in den Kommentar dieses schreiben kann, ist ein Zeiger- Zu-Zeiger-Typ.

Die Linie

if (!n) return 1; 

-Tests, wenn der Zeiger n gültig ist (das heißt nicht NULL) und gibt 1 als einen Codefehler, wenn der Vergleich fehlschlägt.

Jetzt ist der Code

for (iter=tail; **iter != NULL; iter = &((*iter)->next) 
{ 
    *iter = n; /* -->this is the part i don't really get... */ 
    return 0; 
} 

iteriert über die Liste, bis Sie treffen auf ein NULL Zeiger. Die Linie *iter = n; dereferenziert den aktuellen Iterator (in diesem Fall wird einen Zeiger auf die aktuellen node und ordnet n zu. So im Wesentlichen der für das Ende der Warteschlange sucht und weist das das neue Element bis zum Ende.

**((iter)->next) 

ist nicht die gleiche wie

&((*iter)->next) 

die Aussage (*iter)->next Dereferenzierungen iter, die ein Zeiger auf einen Zeiger auf ein struct queue_node ist, so dass Sie nur den tatsächlichen Zeiger auf queue haben. Dann ist es ge ts das next Feld von der queue. Die & gibt Ihnen einen Zeiger auf das Element, das von next referenziert wird (es ist der Adressoperator), während Ihr Code Ihnen das tatsächliche Objekt gibt, das von ->next referenziert wird.

Jetzt für Sie sind Code:

void enqueue(node *head,int data) 
{ 
    if(head->next != NULL) /* what happens if head is NULL ?*/ 
    { 
     enqueue(head->next,data); 
    } 
    node *new=NULL; 
    new=malloc(sizeof(node)); 
    new->value=data; 
    new->next=NULL; 
    head->next=new; 
} 

Anders als mein Kommentar am Anfang ich nichts falsch mit ihm sehen. Aber ich habe nicht wirklich getestet, ob der Code läuft;)

Ich hoffe das macht die Sache übersichtlicher. :) Wenn es Unklarheiten mit meiner Erklärung gibt, bitte Kommentar und nicht einfach Downvote, ich weiß, ich bin nicht der erfahrenste C Programmierer.

Answer 2

Wenn Ihre Definition der queue

struct queue_node 
{ 
    int item; 
    struct queue_node *next; 
}; 

typedef struct queue_node queue; 

dann die Funktion zu verwenden, wird die folgende Art und Weise suchen.

int enqueue(queue **tail, int item) 
{ 
    queue *node = (queue *)malloc(sizeof(queue)); 
    int success = node != NULL; 

    if (success) 
    { 
     node->item = item; 
     node->next = NULL; 

     while (*tail != NULL) tail = &(*tail)->next; 

     *tail = node; 
    } 

    return success; 
} 

Im Gegensatz zu Funktionsdefinition liefert diese Funktion 1 im Falle des Erfolgs, das ist, wenn der neue Knoten, die an die Warteschlange angehängt wird erfolgreich und sonst 0 zugeordnet.

Also, wenn Sie eine Warteschlange die folgende Art und Weise erklärt

Warteschlange * head = NULL;

dann kann ein Funktionsaufruf aussehen

enqueue(&head, value); 

wo value einige Integer-Ausdruck ist.

Wie Sie sehen, müssen Sie den Kopf der queue indirekt mit Zeigern übergeben. Andernfalls, wenn keine Zeiger verwendet werden sollen und der Kopf direkt an die Funktion übergeben wird, erhält die Funktion eine Kopie des Kopfes. Änderungen der Kopie in der Funktion haben keinen Einfluss auf den ursprünglichen Kopf.

In dieser Erklärung

queue *node = (queue *)malloc(sizeof(queue)); 

ein neuer Knoten erstellt. Die Funktion malloc gibt den Zeiger auf den zugewiesenen dynamischen Knoten zurück.

In dieser Erklärung

int success = node != NULL; 

wird das Ergebnis des Ausdrucks zugewiesen node != NULL (entweder 1 oder 0) abhängig davon, ob der Anruf von malloc erfolgreich war oder nicht.

Wenn der Aufruf von malloc erfolgreich war, der node ungleich NULL ist, wird der neue Knoten initialisiert und an das Ende der Warteschlange angehängt. if (Erfolg) { node-> item = item; Knoten-> nächste = NULL;

 while (*tail != NULL) tail = &(*tail)->next; 

     *tail = node; 
    } 

Wie finden Sie den Schwanz der Liste?

Wenn die Liste anfänglich leer war, dann ist *tail gleich NULL und die Bedingung auf der while *tail != NULL wird gleich falsch sein.So dass der aktuelle Wert des tail, die NULL gleich für die Adresse des zugeordneten Knotens ersetzt ist

*tail = node; 

Andernfalls, wenn *tail ungleich NULL ist erhält man das Datenfeld next des aktuellen Knotens

(*tail)->next 

und wiederum nehmen sein die gleiche Art und Weise Adresse wie wir den Kopf auf die Funktion von Referenz

bestanden

&(*tail)->next 

AT, wenn dieses Datenfeld NULL enthält, ersetzen wir dieses NULL für die Adresse des neu erstellten Knotens.

, wenn Sie eine rekursive Funktion schreiben möchten, einen neuen Knoten in die Warteschlange anhängt dann kann es aussehen

typedef struct node 
{ 
    int value; 
    struct node *next; 
} node; 

void enqueue(node **tail, int data) 
{ 
    if (*tail != NULL) 
    { 
     enqueue(&(*tail)->next, data); 
    } 
    else 
    { 
     node *tmp = malloc(sizeof(node)); 
     tmp->value = data; 
     tmp->next = NULL; 

     *tail = tmp; 
    } 
} 

Answer 3

Sie und Ihr Professor behandeln grundsätzlich die Variablen unterschiedlich. Basierend auf dann Namensgebung ich glaube, der Professor strebt ein Bild, das ein bisschen wie folgt aussieht:

Der tail Zeiger bezieht sich auf den äußersten rechten Knoten, den Sie von dequeue würde, und an die Stelle zu erhalten, die Sie einreihen, Sie Iterieren, bis Sie die Vorderseite der Warteschlange erreichen. Nun ist die wichtige Sache zu beachten, dass iter nicht direkt auf Knoten zeigt, zeigt es auf die next Zellen innerhalb jedes Knotens, bis es eine NULL eins findet, wie ich hier zu veranschaulichen versuche.

denke ich, in der Praxis, Sie haben Recht mit nicht nur eine Schleife durch die Warteschlange wollen einen Knoten hinzuzufügen. Tatsächliche Warteschlangenimplementierungen (die manchmal unter Verwendung von verketteten Listen ausgeführt werden) wollen eine konstante Zeit O(1) in Warteschlangen und aus der Warteschlange, so dass sie zu jedem Zeitpunkt einen Zeiger auf jedes Ende der Warteschlange halten.

Abschließend haben alle unterschiedliche Meinungen über C-Namenskonventionen, aber ich stimme Ihnen zu, dass das Beispiel des Professors einige verwirrende Typdefinitionen aufwies. Einige Codebasen wie der Linux-Kernel empfehlen, typedefs für Zeiger oder gar Strukturen nicht zu verwenden.