C语言函数中的参数作为指针指向指针的问题

enxuqcxy 于 2023-04-29 发布在其他

关注(0)|答案(1)|浏览(138)

我正在阅读"C Programming: A Modern Approach" by KN King这本书，在第17章。在第432页，它们定义了一个从单链表中删除节点的函数：
下面的函数delete_from_list使用了我们刚刚概述的策略。当给定一个列表和一个整数n时，该函数删除包含n的第一个节点。如果没有节点包含n，则delete_from_list不执行任何操作。在这两种情况下，函数都会返回一个指向列表的指针。

struct node *delete_from_list(struct node *list, int n)
{
  struct node *cur, *prev;

  for (cur = list, prev = NULL;
       cur != NULL && cur->value != n;
       prev = cur, cur = cur->next)
     ;
  if (cur == NULL)
    return list;               /* n was not found */
  if (prev == NULL)
    list = list->next;         /* n is in the first node */
  else
    prev->next = cur->next;    /* n is in some other node */
  free(cur);
  return list;
}

这本书在第454页的练习中提到了这个函数：

练习

1.修改delete_from_list函数，使其只使用一个指针变量，而不是两个（cur和prev）。
我的问题是关于我在Github上找到的以下解决方案：

struct node *delete_from_list(struct node **list, int n) {
    struct node *item = *list;
    while (item) {
        if (item->value == n) {
            *list = item->next;
            free(item);
            break;
        }
        list = &item->next;
        item = item->next;
    }
    return *list;
}

我知道指针指向指针是什么。但我不明白struct node **list行之后会发生什么。如果有人能用可视化的方式逐行解释这个解决方案，我将非常感激。

c

来源：https://stackoverflow.com/questions/76041189/question-about-argument-in-a-function-as-a-pointer-to-a-pointer

1条答案

按热度按时间

dfty9e191#

如果有人能用可视化的方式逐行解释这个解决方案，我将非常感激。
让我们举一个链表的例子，它的值为1、2和3，其中head指向它的第一个节点，我们有一个值n等于2。我们可以将主程序中列表的状态描述如下：

┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

使用这个解决方案代码，调用者必须传递一个指向节点的指针，因此如果主程序中的head变量是指向第一个节点的指针，我们需要传递它的 address，如下所示：

delete_from_list(&head, n);

现在让我们想象一下函数如何看到自己的list变量：

┌───────┐
      │ list  │
      └───│───┘
          ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

第一个语句是：

struct node *item = *list;

所以我们得到：

┌───────┐   ┌───────┐
      │ list  │   │ item  │
      └───│───┘   └───│───┘
          ▼           ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

执行进入循环，但if条件为false，因此下一个执行的语句是：

list = &item->next;

现在，本地变量list将指向item所指向的节点的next成员的地址：

┌───────┐
                  │ item  │
                  └───│───┘
                      ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │  │             │  │              │
                  └───│─────────┘  └─────────────┘  └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

循环体中的最后一条语句是：

item = item->next;

所以我们得到：

┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │  │             │  │              │
                  └───│─────────┘  └─────────────┘  └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

在下一次迭代中，if条件为真，因此我们执行以下操作：

*list = item->next;

这会使列表发生如下变化：

┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────┐│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │ ││ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │ ││             │┌►│              │
                  └───│─────────┘ │└─────────────┘│ └──────────────┘
                      │           └───────────────┘
                  ┌───│───┐
                  │ list  │
                  └───────┘

现在可以使用free(item)释放找到的节点：

┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐                   ┌──────────────┐
      │ head ────►│ ┌─────────┐ │                   │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │                   │ │ value 3  │ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │ ┌─────────┐ │                   │ ┌──────────┐ │
                  │ │ next─────────────────────────►│ │ next NULL│ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │   ▲         │                   │              │
                  └───│─────────┘                   └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

最后，函数返回*list，但这没有什么用途：调用者不应该使用该返回值来赋值给自己的head变量，否则会出错。调用者应该只依赖函数来适应它的head，如果有必要的话（不是这个例子中的情况）。
这是呼叫者最终得到的结果：

┌───────┐   ┌─────────────┐                   ┌──────────────┐
      │ head ────►│ ┌─────────┐ │                   │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │                   │ │ value 3  │ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │ ┌─────────┐ │                   │ ┌──────────┐ │
                  │ │ next─────────────────────────►│ │ next NULL│ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │             │                   │              │
                  └─────────────┘                   └──────────────┘

备注

在我看来，这并不是一个“公平”的解决方案，因为它改变了函数的签名：

调用方必须传递双指针而不是单指针，并且
调用者不应该使用返回的指针将其赋值回自己的列表指针。相反，该函数返回一个指向后继节点的指针，在大多数情况下，这不是有趣的信息，因此调用者可以忽略返回值。

原始函数必须这样调用：

head = delete_from_list(head, n);

...而这个函数应该这样调用：

delete_from_list(&head, n);

基于上述原因，我不确定这是否是这项工作的预期解决方案。有关解决此问题的其他想法，请参见this Q&A。

赞(0）回复(0）举报 2023-04-29

我来回答

C语言函数中的参数作为指针指向指针的问题

练习

1条答案

备注

相关问题

热门标签

最新问答

C语言 函数中的参数作为指针指向指针的问题

练习

1条答案

备注

相关问题

热门标签

最新问答

C语言函数中的参数作为指针指向指针的问题