链接列表插入函数通过引用发送参数的误解

Question

我正在阅读一本关于 C/C++ 的书，并从中学习链表。

我将 LL 实现为：

struct Node {
    int information; // the information of one node. assumed is that this is an integer only
    struct Node * next; // pointer which stores the address of next node in the list. points to next node in the list.
}

typedef struct Node * List;

我创建 Insert 函数为：

void Insert(List & First, List p, int x) { // First is given by reference because after insertion the First node can be changed.
    // Dynamically allocate new memory for the node we want to insert
    struct Node * q  = new Node;
    
    // Populate the new node with its information (the integer it contains)
    q -> information = x;

    if (!p) { // case 1: insert at beginning
        q -> next = First;
        First = q;
    }
    else { // case 2: insert in the middle of the list or at the end of the list
        q -> next = p -> next;
        p -> next = q; 
    }
}

我的问题是：

为什么我们发送 First 参数作为参考而 p 参数不作为参考？我看到 First 更改了“'as a whole'”，只有 p 中的“'piece'”发生了更改，因此“'not as a whole'”。会是这个原因吗？

First = q;

p -> next = q;

我不是很熟悉指针，但是如果我们将一个变量的地址从调用函数发送到被调用函数，被调用函数可以''manipulate the variable''因为它不会复制它将实际参数的值堆栈到一个新对象中，但对调用函数堆栈中的实际变量起作用。

为什么我们需要写那个参考符号，为什么我们不需要为 p 写那个符号？

我使用这个函数来创建一个队列：

First = Last = NULL;
std::cin >> n; // this many events (n) will populate the Queue

for (int i=1; i<=n; i++) {
    std::cin >> x; // the information of this i-th node.

    if (First) { // the Queue is NOT EMPTY
        Insert(First, Last, x);
        Last = Last -> next;
    }
    else { // the Queue is EMPTY
        Insert(First, NULL, x);
        Last = First;
    }
}

谢谢！

Answer 1

引起一些混淆的是这个 typedef（至少对我来说，一开始是混淆的根源）：

typedef struct Node * List;

所以这里的论点：

void Insert(List & First, List p, int x) {

实际上是

void Insert(Node*& First, Node* p, int x) {

参数在 C++ 中按值传递，除非您通过引用传递它们。指针也不例外。当你打电话

Insert(head,node,42);

那么Insert会修改head，不会修改node 代码中可以看到：

void Insert(Node*& First, Node* p, int x) { 
    struct Node * q  = new Node;
    q->information = x;
    if (!p) {
        q->next = First;
        First = q;              // (1)
    } else {
        q->next = p->next;
        p->next = q;            // (2)
    }
}

行(1)在传递给函数时确实修改了head。 (2) 行仅修改指针指向的内容而不是指针本身。如果有类似

的东西

 p = nullptr;

在函数中，那么这只会修改函数局部p，不会影响传递给函数的node。因为该函数不需要修改它的第二个参数，所以它没有作为引用传递。

Answer 2

Why do we send the First parameter as reference and the p parameter not as a reference?

因为 First 可能会改变（以一种需要传达给调用者的方式）而 p 可能不会——正如评论所说。

I see that First changes ''as a whole'', and only a ''piece'' of p changes

不，p 根本没有改变。更改 p 看起来像

p = new_value_for_p;

或

++p;

什么的，但是没有这样的代码

... only a ''piece'' of p changes

不不不。变量 p 是一个指针。它永远不会改变。改变一个指针意味着你让它指向别的东西（或者什么都没有，nullptr）。

行

p->next = q;

不会改变 p 的“一块”。它更改了引用的对象p。该对象没有名称，但我们可以称它为 *p。更改此对象的内容 根本不会影响 p。相反，将指针更改为指向其他地方不会影响它指向的对象。

I am not extremely familiar with pointers

这是显而易见的。您需要学习理解指针间接寻址，否则在阅读使用指针的代码时总会遇到麻烦。当我说“麻烦”时，我的意思是不知道代码在做什么。

试着退后一步，画一些方框指针图 (pdf)。

链接列表插入函数通过引用发送参数的误解

linked lists insertion function send argument by references misunderstanding

c++

queue

pointers

data-structures