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 ;它们分别指向当前节点之前的列表节点和最低节点之前的列表节点。当循环终止时，if 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);
    }
}