что содержит temp2-> next?

Question

Эта программа пытается создать связанный список.

#include <iostream>
using namespace std;

struct node {
char name[20];
int age;
int height;
node* next; // Pointer to the next node
 };
 node* startPTR = NULL; // Start Pointer (root)
                   // This pointer permanantly points to the start of the list
                   // Initially there are no nodes

void addNode_AT_END(); // prototype for the function that 'adds nodes at the end'

int main() {
   do {
 addNode_AT_END();
     cout << "Add more ?";
     char ch;
     cin >> ch;
   } while( ch == 'y');
}

void addNode_AT_END() {
node *temp1;
node *temp2;
temp1 = new node;  // We declare space for a pointer item and assign a temporary pointer to it  
                   //*temp1 is the node that it points to
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; // indicates that this node when inserted in the list will be the last node
  if( startPTR == NULL) {
    startPTR = temp1;  // In the empty list last node will be the first node
  }  else {
        temp2 = startPTR;
        while( temp2->next != NULL )
            temp2 = temp2->next;
        temp2->next = temp1;
     }

}

Из этой еще не завершена программа, вот что я понимаю:

Если число после второго вызова функции addNode_AT_END истинно, то что содержит temp2->next в операторе while( temp2->next != NULL )?

Answer 1

Содержит NULL, и это из-за этой строки:

temp1->next = NULL; 

Каждый новый узел имеет указатель next, который вы делаете NULL, выполняя вышеуказанный шаг, и новый узелдобавляется в конец списка, в результате чего конец списка всегда равен NULL.Цикл while проходит до конца списка, и while(temp2->next != NULL) устанавливает условие, которое говорит, пока next из temp2 не станет NULL, сделайте temp2 = temp2->next.

Answer 2

Ваши диаграммы неверны.start = temp2 действительно означает, что указатели start и temp2 указывают на один и тот же узел.На вашей диаграмме показано следующее поле указателя temp2, содержащее адрес начала.Кроме того, после выполнения start->next = temp1 это не означает, что если вы получите какое-либо новое значение узла в temp1 (при следующем вызове функции), start->next будет по-прежнему указывать на новое значение, только что выделенное в temp1.Он будет содержать старое значение, которое было до того, как вы перезаписали его новым.start->next = temp1 просто копирует значение в temp1 т.е.адрес переменной (указатель переменной) следующего компонента узла, на который указывает начало, который равен start->next.После этого между start и temp1 нет связи.

В контексте связанного списка «temp1 ----> temp2» означает поле next узла, адрес которого хранится в temp1, содержит адрес узла с адресом, который был сохранен илиудерживается temp2.Теперь после изменения значения указателя переменная temp2 не меняет поле next узла, хранящегося по адресу, хранящемуся в temp1.temp1->next по-прежнему содержит значение, которое было сохранено ранее.

Следующие ссылки не указывают на имя какой-либо переменной, то есть start->next = temp не сделает следующий узел узла start всегда указывающим налюбой узел temp1 содержит, но он start->next будет содержать адрес, который temp1 хранится во время назначения.

обратите внимание, что выражение «start указывает на temp1» означаетчто адрес

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

сломается, когда temp2->next = NULL, что означает, что temp2 указывает на последний узел списка.В этот момент temp2->next = temp1 связывает вновь выделенный узел после того узла, который в данный момент указан temp2.Это просто добавляет новый узел в конце.

  At the end of the above while loop

                                                              temp2
                                                                |
                                                                V

(start) ----> (n1) ----> (n2) ----> (n3) . . . (n(n-1)) ----> (nn) ----> NULL


   temp2->next = temp1    makes


                                                              temp2
                                                                |
                                                                V

(start) ----> (n1) ----> (n2) ----> (n3) . . . (n(n-1)) ----> (nn) ----> (temp1)--->NULL


 because temp2 holds the address of (nn) therefore linking the new node to the next node of the last node.

ОБНОВЛЕНИЕ

Первый раз:

start = NULL
a new address is allocated and the address stored into temp1 pointer. Also temp->next = NULL
if condition becomes true and temp1 is assigned to start
start = temp1

List state


start = addr1;
 |
 V
(addr1) ----> (NULL)

Второй раз:

a new node is allocated and the address of the new node is stored into `temp1`. Let this address be `addr2`. Now `temp1` contains the value `addr2`

start is NOT NULL, as start has addr1 in it from the last call.So the else part is true and we get the address of the start node `addr1` into temp2.

temp2 = start;

which means temp2 now points to `addr1`

while loop is encountered. The first iteration the condition `temp2->next != NULL` is FALSE. This is because `temp2` points to `addr1` and the next pointer field of `addr1` has NULL from the last time the function is called. Therefore the while loop terminates.

The next statement does `temp2->next = temp1` . `temp2` points to `addr1` address, and the address of the newly allocated node `addr2` contained in `temp1` is assigned into the next field of the node whose address is stored into `temp2`. Which actually assigns the address `addr2` to the next field of the node identified by the address `addr1`.


temp1 = addr2     after allocation

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


after temp2->next = temp1

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

В третий раз:

temp1 = addr3      new node address allocated

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


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


we can see temp2->next = NULL and while condition is false. Note that temp2 contains itself the address addr2, and thus temp2->next is NOT addr2, it is NULL.

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



After linking: temp2->next = temp1;

start = addr1;               temp1         the address addr3 (new node)
 |                             |          is stored in temp1. this address is assigned
 V                             V         to the next node of temp2, replacing NULL
(addr1) ----> (addr2) ----> (addr3) ----> (NULL)      
                 ^                      
                 |
               temp2

Указатели являются средством перемещения / перемещения по списку.Начальный адрес списка содержится в указателе start.Поскольку следующее поле каждого узла указывает на следующий узел, если мы получим узел start, то, следуя следующим полям последовательно, мы сможем посетить каждый узел.temp1 и temp2 являются указателями, с помощью которых выполняются обходы, они действуют как временные указатели, temp1 используется для хранения вновь выделенного узла, а temp2 используется для перемещения по списку, следуя next ссылки до последнего, когда последняя ссылка найдена (обнаружена указателем NULL в следующем поле), ссылка NULL этого последнего узла заменяется вновь выделенным узлом, содержащим temp1.Поскольку теперь узел, удерживаемый temp1, связан / добавлен в конец списка, temp1 используется повторно для хранения другого нового узла.