C - 瞭解指向指針的指針並修改內存位置的值

Question

自從我真的使用C以來已經有一段時間了，所以我很抱歉，如果這是顯而易見的事情，我只是忘記指針如何工作。基本上，我有一個鏈接列表結構，其中每個鏈接都有一個分數。我試圖編寫一個遍歷我的列表並刪除最低分數的鏈接的算法。我的結構看起來像這樣：

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

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

其中Head是列表中默認的第一個鏈接。我現在的算法看起來大致是這樣的：

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; 

    } 

} 

現在，我知道這個代碼將不能工作，我想我明白它在做什麼。我不明白的是如何修改代碼來完成我的預期目標。

我的意圖是將指針的內存位置存儲到變量「lowestPrev」中的最低得分節點，然後將最低得分節點之後的節點的指針值分配給該內存位置。所以，我每次遇到比我現在的得分最低得分較低的節點，我會拿着它的點的存儲位置的變量：

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

，並在年底，我將分配的指針值在這個存儲位置下一個環節：

*lowestPrev = (*lowestPrev)->next; 

然而，似乎「lowestPrev」（如果我正確理解這一點）不會簡單的保留它最初分配給它的內存位置，但更新它的值每它指向的指針被更新的時間，在這裏：

current = current->next; 

我是否正確理解此行爲，如果是這樣，我如何修改我的代碼以完成我所說明的目標？

Answer 1

沒有理由使用雙指針lowestPrev;它是head，這可能應該是一個雙指針，但在這種情況下這不是必需的。

可能的是，該列表中的最低值是在第一列表節點，並且如果head指向該節點，的head值將需要在removeLowest()函數內進行修改。這在函數之外是不可見的，所以在這裏可以使用雙指針。

但是，由於head實際上是指向虛擬節點的指針，所以不需要這個。第一個列表節點可以在不修改頭節點的情況下進行更改。

發佈的代碼有幾個問題。 current是一個指針，所以lowestScore = current.score;應改爲lowestScore = current->score;。另一個問題與雙指針lowestPrev有關。在循環內，該指針的地址值爲current，然後current的值爲current->next。在循環結束之前，current變爲NULL;但現在*lowestPrev == NULL，因爲lowestPrev持有地址current。這導致未定義行爲（最有可能是分段故障）在該行：

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

擺脫這種雙重指針在正確的方向邁出的第一步的。但實際刪除具有最低值的節點需要以不同的方式處理。要刪除此節點，最低節點前面的節點需要連接到它後面的節點。一種策略是始終保持指向最低節點之前的節點的指針，以便在循環終止後進行適當的連接。

最初，prev和lowestPrev應該是NULL;它們分別指向當前節點之前的列表節點和最低節點之前的列表節點。當循環終止時，如果lowestPrev爲NULL，則第一個列表節點最低，並且head->next被設置爲指向第一個列表節點之後的節點。如果lowest之後的節點爲NULL，則最後一個列表節點最低，lowestPrev-next設置爲指向NULL。否則，lowestPrev->next被設置爲指向lowest之後的節點。

請注意，如果用於列表節點（以及對於頭節點）動態分配，該存儲器必須是free d，並對拆下的列表節點將需要free d從removeList()返回之前。這是發佈代碼的修改版本。此函數假定head不NULL，作爲發佈功能所做的：

/* 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); 
    } 
} 

它可能通過識別LinkedList和Head結構是相同的以簡化這個碼的位，並且所述虛設Head節點可以替換爲虛擬的LinkedList節點。

該實現也可以改變，以避免完全需要虛擬節點;這樣做的一種方法是將指針的地址傳遞給第一個列表節點到函數中。下面是如何可能做一個例子：

struct node { 
    struct node *next; 
    int score; 
}; 

/* Assumes that head is not NULL */ 
void remove_lowest(struct node **head) 
{ 
    if (*head) { 
     struct node *current = *head; 
     struct node *prev = NULL; 
     struct node *lowest = current; 
     struct node *low_prev = NULL; 
     int low_score = current->score; 

     while (current) { 
      if (current->score < low_score) { 
       lowest = current; 
       low_prev = prev; 
       low_score = current->score; 
      } 
      prev = current; 
      current = current->next; 
     } 

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