如何在链表的节点之间移动？

Question

这是一段试图构建链表的代码.

struct node {
    char name[20];
    int age;
    int height;
    node* next; // Pointer to the next node
};
node* startPTR = NULL;

void addNode_AT_END() {
    node *temp1;
    node *temp2;

    temp1 = new node;  

    cout << "Enter the name : ";
    cin  >> temp1->name;
    cout << endl << "Enter the age : ";
    cin  >> temp1->age;
    cout << endl << "Enter height : ";
    cin  >> temp1->height;

    temp1->next = NULL;

    if( startPTR == NULL) {
       startPTR = temp1; 
    }  else {
       temp2 = startPTR;

       while( temp2->next != NULL )
           temp2 = temp2->next;

       temp2->next = temp1;
    }
 }

以下是对上述函数进行2次背靠背调用后的示意图.

start = addr1;
|
V
(addr1) ----> (addr2) ----> (NULL)      at end
^
|
temp2

其中addr1和addr2分别是第一个和第二个节点的地址.

第三次通话后会发生什么？迭代将如何继续进行第三次调用？我无法理解list第二次通话后链接是怎么回事.据我所知,所有这些都已经建立起来,直到知道会消失.然后如何进一步列出？如何在第三次呼叫期间放置节点？

Answer 1

这是所有魔法发生的地方:

1. temp2 = startPTR;
2. while( temp2->next != NULL )
3.    temp2 = temp2->next;
4. temp2->next = temp1;

首先,temp2将指向列表的开头.在第2和3,您更改temp2,直到你到达那里的节点到下一个节点temp2->next是NULL.无论列表的大小如何,此节点都是列表的最后一个节点.

最后,在第4行中,您将更temp2->next改为temp1现在它指向新节点(即最后一个节点现在指向新节点).temp1->next也是NULL,所以temp1现在代表清单的结尾.

在第1行之后你有

start = addr1;
|
V
(addr1) ----> (addr2) ----> (NULL)
^
|
temp2

temp2->next不是NULL(它是addr2),所以你迭代并执行第3行,你得到:

start = addr1;
|
V
(addr1) ----> (addr2) ----> (NULL)
              ^
              |
              temp2

temp2->next现在NULL.所以你停止循环并执行第4行,你得到:

start = addr1;
|
V
(addr1) ----> (addr2) ----> (addr3) ----> (NULL)
              ^             ^
              |             |
              temp2         temp1

注意:你知道指针是如何工作的吗？想象一下:你有一个节点,它是内存中的一些数据.当你在内存中有变量时,这些变量都有地址.假设addr1为10,addr2为150,addr3(刚刚new编辑的节点)为60. start值为10.因此,"指向"列表的第一个节点(即使用此地址,您可以访问它数据).其中一个数据是该next领域.第一个节点的next字段的值为150,因此指向下一个节点.当你说temp2 = start,你把数字10放入temp2,此时temp2->next有150的值.当你说temp2=temp2->next,你只需要输入值150 temp2,覆盖以前的值.这样您就可以有效地将指针从指向第一个节点移动到现在指向第二个节点.现在temp2->next是NULL(即0).如果现在说temp2->next=temp1,你把值60的next领域temp2.所以,现在temp2->next是60 temp2->next->next时NULL.