Как вы перемещаетесь между узлами связанного списка?

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;
    }
 }

Ниже приведена схема после двух последовательных вызовов вышеуказанной функции.

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 ed) равен 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.

Answer 2

Я не понимаю, что тебя беспокоит.Во время любого вызова while () цикл будет проходить через все узлы в списке до тех пор, пока он не достигнет конца, а затем установить указатель в последнем на вновь выделенный узел (temp1).

temp1 и temp2указатели.они не хранят данные узла, они хранят адрес в памяти, где хранятся данные.поэтому в конце первой итерации после startPTR = temp1 startPTR указывает на тот же адрес, на который указал temp1.не имеет значения, находится ли там temp1, так как теперь startPTR указывает на узел.в конце второго вызова temp2->next=temp1 (в этот момент temp2 == startPTR) поле next узла указывает на вновь выделенное temp1

Answer 3

Все довольно просто.Цикл while переместит temp2 к последнему элементу.Затем созданный вами узел, на который указывает temp1, назначается следующим узлом temp2