verkettete Liste an den Schwanz Hinzufügen Verwirrung

Question

Visual Studio 2008 C

Was ich nicht über diese verknüpften Liste verstehen, ist die an den Schwanz, indem zu in anderen Teil der if-Anweisung.

Wenn Kopf und Zahl die Speicheradresse von node_temp zugewiesen ist, zeigen beide auf den gleichen Speicherplatz.

In dem else Teil ist der Kopf tatsächlich immer noch auf den Schwanz. Es gibt etwas, das ich nicht erklären und nicht verstehen kann.

Ich hoffe, dass jemand besser für mich erklären kann.

static struct convert_temp 
{ 
    size_t cel; 
    size_t fah; 
    struct convert_temp *next; 
} *head = NULL, *tail = NULL; 

/** Add the new converted temperatures on the list */ 
void add(size_t cel, size_t fah) 
{ 
    struct convert_temp *node_temp = NULL; /* contain temp data */ 

    node_temp = malloc(sizeof(*node_temp)); 

    if(node_temp == NULL) 
    { 
     fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", 
      __FUNCTION__, __LINE__); 
     exit(0); 
    } 

    /* Assign data */ 
    node_temp->cel = cel; 
    node_temp->fah = fah; 
    node_temp->next = NULL; 

    if(head == NULL) 
    { 
     /* The list is at the beginning */ 
     head = node_temp; /* Head is the first node = same node */ 
     tail = node_temp; /* Tail is also the last node = same node */ 
    } 
    else 
    { 
     /* Append to the tail */ 
     tail->next = node_temp; 
     /* Point the tail at the end */ 
     tail = node_temp; 
    } 
} 

Answer 1

Wenn Sie das erste Mal ein Element (nennen wir es A) zur Liste hinzufügen, ist head null und Sie gehen durch den if Teil. Das bedeutet, dass sowohl head als auch das Ende auf A zeigen, wenn dieses erste Element hinzugefügt wird.

Jetzt fügen wir ein weiteres Element B hinzu. Diesmal ist head nicht null, also geht es durch den else Teil, Einstellung tail, um auf B zu zeigen, aber head lassend, zeigend auf A.

Das wie erwartet, haben Sie jetzt zeigen head auf A, A deutete auf B, B nichts zeigt (null) und tail-B zeigen.

Nehmen wir es Schritt für Schritt.

Initial state: head -+-> null 
         | 
       tail -+ 

Insert item A: head -+-> A ---> null 
         | 
       tail -+ 

Insert item B: head ---> A -+-> B ---> null 
          | 
       tail --------+ 

Insert item C: head ---> A ---> B -+-> C ---> null 
            | 
       tail ---------------+ 

Sie an jeder Stufe (mit Ausnahme der Anfangs) sehen kann, dass der Strom-Schwanzes an den neuen Knoten Punkt gesetzt ist (die bereits für den nächsten Knoten auf Nullpunkte), wird der Endzeiger zum Punkt aktualisiert wird an die neue letzten Knoten.

In der Tat, sie die Zugabe von C in noch mehr Detail durch (Zeile für Zeile), so können Sie jede Codezeile sehen, was (ich habe gerade umbenannt node_temp-node mit Formatierung zu helfen) tut :

Starting state:    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node = malloc(sizeof(*node)); node ---> C ----------> ? 
(allocate node C)    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node->next = NULL;    node ---> C --------+ 
(ignore payload cel/fah       | 
    for now since it's not  head ---> A -+-> B -+-> null 
    relevant to the list     | 
       structure)  tail --------+ 

tail->next = node;    node ---------------+ 
(first in else clause)       | 
           head ---> A -+-> B -+-> C ---> null 
              | 
           tail --------+ 

tail = node;     node ---------------+ 
(second in else clause)       | 
           head ---> A ---> B -+-> C ---> null 
                | 
           tail ---------------+ 

Dann schließlich node verschwindet, da es sich um eine lokale Variable ist und Sie Ihre endgültige Zustand haben:

       head ---> A ---> B -+-> C ---> NULL 
                | 
           tail ---------------+ 

der Vorteil einerAufrechterhaltungZeiger in einer einfach verknüpften Liste verhindern, dass Sie die gesamte Liste durchlaufen müssen, um das Ende zu finden, wenn Sie versuchen, ein Element am Ende hinzuzufügen.

Wenn Sie die gesamte Liste durchlaufen, wird am Ende eine O(n) Zeitoperation eingefügt (die Zeit hängt von der Anzahl der Elemente in der Liste ab). Die Verwendung des tail Zeigers macht dies zu einer O(1) Zeitoperation (gleiche Zeitdauer unabhängig von der Listengröße).

Als Nebenwirkung eine doppelt verknüpfte Liste eine zusätzliche Verwendung für einen tail Zeiger hat - es gibt die Möglichkeit, schnell eine Traversal vom Ende der Liste an den Start zu beginnen, mit tail und den prev Zeigern anstelle von head und die next Zeiger.

Answer 2

Der else-Teil aktualisiert nur die tail der Liste, da der Kopf nicht ändert, wenn Sie auf eine verknüpfte Liste anhängen.

Es ist eine Optimierung, um einen Zeiger auf das Schwanzelement gepuffert zu halten, so dass Sie nicht die gesamte Liste vom Kopf jedes Anhangs durchlaufen müssen.

Answer 3

Es ist nicht so, dass der Kopf immer noch auf den Schwanz zeigt. Kopf zeigt auf ehemaligen Schwanz. Wenn die Liste nur ein Element enthielt, war es sowohl Kopf als auch Schwanz. Wenn ein neuer Knoten angehängt wurde, wurde der Endzeiger aktualisiert. Der Kopfzeiger zeigt immer noch auf den ersten Knoten, der korrekt ist.

Answer 4

Beim ersten Aufruf von add zeigen head und tail auf einen neu erstellten Speicherblock. Alle nachfolgenden Aufrufe zum Hinzufügen werden durch den else-Teil ausgeführt, der nur den Tail-Zeiger ändert, indem der alte Tail-> next-to-Punkt auf den neuen Speicherblock geändert wird und dann das Tail aktualisiert wird, um auch auf diesen neuen Speicherblock zu zeigen .

Es ist eine effiziente Art des Anhängens. Wenn nur head verwendet wurde, müssten Sie jedes Mal, wenn Sie einen neuen node_temp hinzufügen, alle nächsten Zeiger von head bis zum zuvor hinzugefügten node_temp (dessen nächster Zeiger NULL wäre) durchlaufen und dann den neuen Knoten hinzufügen . Dies wäre dann ein O (n) -Algorithmus und nicht das obige O (1).