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指向此节点，则需要在removeLowest()函数中修改head的值。这在函数外部不可见，因此可以在此处使用双指针。

但是，由于在这种情况下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的;它们分别指向当前节点之前的列表节点和最低节点之前的列表节点。当循环终止时，如果lowestPrevNULL，则第一个列表节点最低，head->next设置为指向第一个列表节点之后的节点。如果lowest后面的节点是NULL，则最后一个列表节点是最低的，并且lowestPrev-next设置为指向NULL。否则，lowestPrev->next将设置为指向lowest后面的节点。

请注意，如果对列表节点(和头节点(使用动态分配，则需要freed，并且删除的列表节点需要freed，然后才能从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);
}
}