linus大神的二级指针

电玩女神 2022-01-15 07:29 162阅读 0赞

看到这段代码的时候，我眼前一亮，果然是大神。

一般我们删除单向链表种的一个节点的时候都会这样写：

typedef struct node
    {
        struct node * next;
        ....
    } node;
    
    typedef bool (* remove_fn)(node const * v);
    
    // Remove all nodes from the supplied list for which the 
    // supplied remove function returns true.
    // Returns the new head of the list.
    node * remove_if(node * head, remove_fn rm)
    {
        for (node * prev = NULL, * curr = head; curr != NULL; )
        {
            node * const next = curr->next;
            if (rm(curr))
            {
                if (prev)
                    prev->next = next;
                else
                    head = next;
                free(curr);
            }
            else
                prev = curr;
            curr = next;
        }
        return head;
    }

用一个指针prev来存储前一个节点，用prev->next = curr->next来操作，且看下面的代码，是不是显的更优美。

void remove_if(node ** head, remove_fn rm)
    {
        for (node** curr = head; *curr; )
        {
            node * entry = *curr;
            if (rm(entry))
            {
                *curr = entry->next;
                free(entry);
            }
            else
                curr = &entry->next;
        }
    }

以上的代码是linus给出的，我改写了一下，这样可能理解起来更加简单。

void remove_if(node ** head, remove_fn rm)
    {
        for (node** curr = head; *curr; )
        {
            if (rm(*curr))
            {
                node *tmp = *curr;
                *curr = (*curr)->next;
                free(tmp);
            }
            else
                curr = &((*curr)->next);
        }
    }

删除节点的核心代码是这句：

\*curr = (\*curr)->next;

理解的关键在于：

0. 我们要做的，就是更新某个节点的成员next，而curr定义为某个节点的成员next的**地址**，那么最终肯定是用语句\*curr = xxxx来更新。

捋一捋：

1. curr：是一个指针的指针

2. **\*curr：是一个指针变量，它的值是某个节点的成员next**（next是一个指针，它的值是下一个节点的地址）。

3. (\*curr)->next：相当于p->next->next，是节点(p->next)的next成员，是一个指针。

\*curr = (\*curr)->next;

就成功的更新了 **欲删除节点的前一个节点** 的next成员。