C - Zeiger auf Zeiger verstehen und Wert am Speicherplatz ändern

Question

Es ist schon eine Weile her, seit ich C benutzt habe, also entschuldige ich mich, wenn das etwas ist, was offensichtlich sein sollte und ich vergesse nur, wie Zeiger funktionieren. Grundsätzlich habe ich eine verkettete Listenstruktur, in der jeder Link eine Punktzahl hat. Ich versuche einen Algorithmus zu schreiben, der meine Liste durchläuft und den Link mit der niedrigsten Punktzahl entfernt. Meine Strukturen in etwa so aussehen:

typedef struct linkedList_tag { 
    struct linkedList_tag *next; 
    int score; 
} LinkedList; 

typedef struct head_tag { 
    int size; 
    struct linkedList_tag *next; 
} Head; 

Wo Leiter ist der Standard erste Glied in der Liste. Mein aktueller Algorithmus sieht in etwa wie folgt aus:

void removeLowest(Head *head) 
{ 

    LinkedList** lowestPrev; 
    LinkedList* current; 
    int lowestScore; 

    if (head->next != NULL) { 
    head->size--; 
    lowestPrev = &head->next; 
    current = head->next; 
    lowestScore = current->score; 

    while (current != NULL) { 
     if (current->score < lowestScore) { 
     lowestPrev = &current; 
     lowestScore = current.score; 
     } 
     current = current->next; 
    } 

    *lowestPrev = (*lowestPrev)->next; 

    } 

} 

Nun, ich weiß, dieser Code wird nicht funktionieren und ich glaube, ich verstehe, was es tut. Was ich nicht verstehe, ist, wie man den Code ändert, um mein beabsichtigtes Ziel zu erreichen.

Meine Absicht war es, die Speicherstelle des Zeigers auf den Knoten mit der niedrigsten Bewertung in der Variablen "lowestPrev" zu speichern und dann den Zeigerwert des Knotens nach dem Knoten mit der niedrigsten Bewertung diesem Speicherort zuzuweisen. Also, jedes Mal wenn ich einen Knoten angetroffen, die niedriger als meine aktuelle niedrigste Punktzahl hat, würde ich den Speicherort es der Punkt in einer Variablen halten:

if (current->score < lowestScore) { 
    lowestPrev = &current; 
    lowestScore = current.score; 
} 

und am Ende, würde ich den Zeigerwert der zuweisen nächsten Link zu diesem Speicherplatz:

*lowestPrev = (*lowestPrev)->next; 

es scheint jedoch, dass „lowestPrev“ (wenn ich zu verstehen, dies richtig) nicht einfach den Speicherplatz beibehalten wurde ursprünglich ihm zugewiesenen, aber aktualisieren sie es Wert ist jeder Zeit, auf die der Zeiger, auf den er zeigt, aktualisiert wird, hier:

current = current->next; 

Verstehe ich dieses Verhalten richtig und, wenn ja, wie kann ich meinen Code ändern, um mein erklärtes Ziel zu erreichen?

Answer 1

Es gibt keinen Grund, einen Doppelzeiger für lowestPrev zu verwenden; Es ist head, dass vielleicht ein Doppelzeiger sein sollte, aber das ist in diesem Fall nicht notwendig.

Es ist möglich, dass der niedrigste Wert in der Liste in dem ersten Liste-Knoten ist, und wenn head zu diesem Knoten zugespitzt, muss der Wert von head würde innerhalb der removeLowest() Funktion modifiziert werden. Dies wäre außerhalb der Funktion nicht sichtbar, so dass stattdessen ein Doppelzeiger verwendet werden könnte.

Aber, da head tatsächlich ein Zeiger auf einen Dummy-Knoten in diesem Fall ist, besteht keine Notwendigkeit dafür. Der erste Listenknoten kann geändert werden, ohne den Kopfknoten zu ändern.

Es gibt ein paar Probleme mit dem gebuchten Code. current ist ein Zeiger, daher sollte lowestScore = current.score; zu lowestScore = current->score; geändert werden. Ein anderes Problem hat mit dem Doppelzeiger lowestPrev zu tun. Innerhalb der Schleife erhält dieser Zeiger den Wert der Adresse current und current den Wert current->next. Bevor die Schleife beendet wird, wird currentNULL; aber jetzt *lowestPrev == NULL, seit lowestPrev hält die Adresse current.Dies führt zu undefiniertem Verhalten (höchstwahrscheinlich ein Segmentierungsfehler) in der Zeile:

*lowestPrev = (*lowestPrev)->next; // probable segfault 

Erste ein erster Schritt in der richtigen Richtung dieser Doppelzeiger befreien. Die tatsächliche Entfernung des Knotens mit dem niedrigsten Wert muss jedoch anders gehandhabt werden. Um diesen Knoten zu entfernen, muss der dem niedrigsten Knoten vorausgehende Knoten mit dem ihm folgenden Knoten verbunden sein. Eine Strategie besteht darin, zu jedem Zeitpunkt einen Zeiger auf den Knoten zu halten, der dem untersten Knoten vorangeht, so dass die geeignete Verbindung hergestellt werden kann, nachdem die Schleife beendet ist.

Zunächst sollten prev und lowestPrevNULL sein; Diese zeigen auf den Listenknoten vor dem aktuellen Knoten bzw. auf den Listenknoten vor dem niedrigsten Knoten. Wenn die Schleife beendet wird, wenn lowestPrevNULL ist, dann ist der erste Listenknoten der niedrigste und head->next ist so eingestellt, dass er auf den Knoten zeigt, der dem ersten Listenknoten folgt. Wenn der Knoten lowestNULL ist, ist der letzte Listenknoten der niedrigste und lowestPrev-next wird auf NULL gesetzt. Andernfalls wird lowestPrev->next auf den Knoten festgelegt, der auf lowest folgt.

Beachten Sie, dass, wenn die dynamische Zuordnung für die Listen-Knoten verwendet wird (und für den Kopf-Knoten), muss dieser Speicher free d, und die entfernten Liste-Knoten müssen seine free d sein, bevor von removeList() zurück. Hier ist eine modifizierte Version des gebuchten Codes. Diese Funktion geht davon aus, dass head nicht NULL ist, wie die gepostete Funktion hat:

/* Assumes that head is not NULL */ 
void removeLowest(Node *head) 
{ 
    LinkedList* current = NULL; 
    LinkedList* lowest = current; 
    LinkedList* prev = NULL; 
    LinkedList* lowestPrev = NULL; 
    int lowestScore; 

    if (head->next != NULL) { 
     head->size--; 
     current = head->next; 
     lowestScore = current->score; 
     lowest = current; 

     while (current != NULL) { 
      if (current->score < lowestScore) { 
       lowest = current; 
       lowestPrev = prev; 
       lowestScore = current->score; 
      } 
      prev = current; 
      current = current->next; 
     } 

     if (lowestPrev == NULL) {    // first node is lowest 
      if (head->next) { 
       head->next = head->next->next; 
      } 
     } else if (lowest->next == NULL){  // last node is lowest 
      lowestPrev->next = NULL; 
     } else { 
      lowestPrev->next = lowest->next; 
     } 
//  free(lowest); 
    } 
} 

Es kann möglich sein, diesen Code ein wenig zu vereinfachen, indem die Erkenntnis, dass die LinkedList und Head Strukturen identisch sind, und dass die Dummy-Head Knoten könnten durch einen Dummy LinkedList Knoten ersetzt werden.

Die Implementierung könnte auch geändert werden, um die Notwendigkeit eines Dummy-Knotens zu vermeiden; Eine Möglichkeit wäre, die Adresse eines Zeigers an den ersten Listenknoten in die Funktion zu übergeben. Hier ist ein Beispiel, wie das gemacht werden könnte: