创建单向链表

Question

我有一个函数可以连接两个结构来创建一个链表。

这里是代码：

struct point{
    int x;
    int y;
    struct point *next;
};
void printPoints(struct point *);
void printPoint(struct point *);
struct point * append(struct point *, struct point *);
void main(){
    struct point pt1={1,-1,NULL};
    struct point pt2={2,-2,NULL};
    struct point pt3={3,-3,NULL};
    struct point *start, *end;
    start=end=&pt1;
    end=append(end,&pt2);
    end=append(end,&pt3);
    printPoints(start);
}
void printPoint(struct point *ptr){
    printf("(%d, %d)\n", ptr->x, ptr->y);
}
struct point * append(struct point *end, struct point *newpt){
    end->next=newpt;
    return newpt;
}
void printPoints(struct point *start){
    while(start!=NULL){
        printPoint(start);
        start=start->next;
    }
}

在这里，append 函数的任务涉及更改结束指针。

append函数的参数都是指针；在第一种情况下，第一个参数是 &pt1，第二个参数是 &pt2.

该函数复制了类型为 struct point 的结束指针。由于传递了 &pt1，因此这个重复的结束指针的 x 分量为 1，y 分量为 -1，下一个分量为 NULL。现在我们将此副本的下一个组件更改为 newpt 指针和 return newpt 指针。

回到main函数，原来的结束指针现在的值为&pt2。

end->next = newpt; 不应在 main 中对原始结束指针产生任何更改，因为仅更改了局部指针。

那我为什么会得到一个链表

我得到的：

(1, -1)
(2, -2)
(3, -3)

我认为我应该得到的：

(1, -1)

Answer 1

end->next = newpt; shouldn't produce any change in the original end pointer in main. Because, only the local pointer was changed

不太正确。确实，当您调用 append 时，会创建 end 的 copy。但是，-> 运算符 取消引用 该指针指向的内容。使用 (*end). 会得到相同的行为。由于 main 中的 end 与 append 中的 end 相同，因此它们都指向同一事物。你可以有 100 个指针副本，都指向同一个东西。如果你选择了一个，跟随它指向的东西并改变它，那么你已经改变了所有其他 99 个指针指向的相同的东西。此外，您通过 returning newpt 在 main 中重新分配 end，因此每次调用 append 都会导致更新的 end。您观察到的输出是正确的。考虑压缩堆栈帧：

在main中，第一次调用append时：

____main____
|___pt1____| <----+  <-+
|x=1 y=-1  |      |    |
|_next=NULL|      |    |
|___pt2____|      |    |
|___pt3____|      |    |
|__start___|------+    |
|___end____|-----------+      // cell sizes NOT drawn to scale
// start and end both point to pt1

现在，在第一次调用 append 时，main 堆栈帧保持不变，并为 append 创建一个新堆栈帧，其中 end 和pt2 的地址被传入。

|___main____
|___pt1____| <----+  <-+
|_next=NULL|      |    |   // x and y omitted for brevity
|___pt2____|      |    |
|___pt3____|      |    |
|___end____|------+    |
                       |
___append__            |
|___&pt2___|           |
|___end____|-----------+  // also points to pt1 back in main

当您使用 -> 运算符时，您 取消引用 该指针指向的内容。在本例中，pt1，所以main中的end和append中的end都指向pt1。在append，你

end->next = newpt;

这是pt2的地址。所以现在你的堆栈框架看起来像这样：

|___main____
|___pt1____| <-----------+  <-+
|_next=&pt2|------+      |    |  // x and y omitted for brevity
|          |      |      |    |  // (made pt1 cell bigger just to make the picture clearer, no other reason)
|__________|      |      |    |   
|___pt2____| <----+      |    |
|___pt3____|             |    |
|___end____|-------------+    |
                              |
___append__                   |
|___&pt2___|                  |
|___end____|------------------+  // also points to pt1 back in main

最后，当你从appendreturn时，你return pt2 的地址并将其分配给end，所以你的堆栈在main在第二次调用 append 之前看起来像这样（同样，为了图片清晰度，一些单元格变大了，这并不意味着任何东西都变大了）：

____main____
|___pt1____| <-----------+
|_next=&pt2|---+         |
|          |   |         |
|__________|   |         |
|___pt2____| <-+ <-+     |
|___pt3____|       |     |
|___end____|-------+     |
|___start__|-------------+  // flipped start and end position to make diagram cleaner, they don't really change positions on the stack

然后你再次调用 append，传入 end（现在指向 pt2）和 pt3 的地址。在所有对append的调用之后，start指向pt1，pt1->next指向pt2，pt2->next指向pt3 ，正如您在输出中看到的那样。

最后一点，你有一个incorrect function signature for main

Answer 2

如图所示，start仍然指向p1，end指向pt3。

void main(){
    struct point pt1={1,-1,NULL};
    struct point pt2={2,-2,NULL};
    struct point pt3={3,-3,NULL};
    struct point *start, *end;
    start=end=&pt1;
    end=append(end,&pt2);
    end=append(end,&pt3);
    printPoints(start);
}

与在 main 函数中一样，您使 start 和 end 指向 pt1。这就是为什么对 end 所做的任何更改也会从 start.

中看到

struct point * append(struct point *end, struct point *newpt){
    end->next=newpt;
    return newpt;
}

在append函数中，end->next=newpt将end的next设置为newpt。在第一种情况下，当 end 指向 pt1 时，next 被设置为指向 pt2。从 start.

也可以看出列表中的这一变化

因此，您得到的输出是正确的。

改变指针

当您将指针传递给函数时，指针的值（即地址）被复制到函数中，而不是它指向的值。

因此，当您取消引用指针并更改它时，也可以从包含相同地址的任何指针中看到更改。请记住 p->next 与 (*p).next 相同。

void change_the_pointer_reference(int* ip)
{
    int i = 1;
    *ip = i;
    printf("%d\n", *ip); // outputs 1
}

int main()
{
    int i = 0;
    change_the_pointer_reference(&i);
    printf("%d\n", i); // outputs 1
}

但是由于指针的值被复制，如果你赋值给指针，这种变化只会在本地看到。

void change_the_pointer(int* ip)
{
    int i = 1;
    ip = &i;
    printf("%d\n", *ip); // outputs 1
}

int main()
{
    int i = 0;
    change_the_pointer(&i);
    printf("%d\n", i); // outputs 0
}

最后一点，你有一个incorrect signature of main

创建单向链表

Creating a singly-linked list

c

linked-list

改变指针