Циклический список для представления людей

#cpp #указатели #списки

Только начал разбираться со списками. Один момент в упор не понимаю. В книге Седжвика
"Алгоритмы на С++" есть такой пример создания циклического списка для представления
людей, расставленных в круг:

struct node {
    int item;
    node *next;

    node(int x, node *t){
        item = x;
        next = t;
    }
};

int main() {
    typedef node *link;
    link t = new node(1, 0);
    t->next = t;    
    link x = t;

    for (int i = 2; i < 5; i++)
        x = (x->next = new node(i, t));

    while (x != x->next){
        for (int i = 1; i < 5; i++)
            x = x->next;
        x->next = x->next->next;
    }

    cout << x->item << endl;

    delete t;   
    return 0;
}


Что делает этот блок:

link t = new node(1, 0);
t->next = t;
link x = t;


1 строка: создается указатель на экземпляр класса node, инициализируются его поля
и выделяется память;

2 строка: аналогично (*t).next = t; В классе node есть поле next - указатель на node,
которому присваивается t - указатель на экземпляра класса node? Можете объяснить, зачем
это делается?

3 строка: аналогична строке link x = new node(1, 0); - первой строке?

P.S. И что означает x->next = x->next->next;? Следующему элементу в списке присваивается
значение, хранящееся после следующего элемента списка:

(*x).next = (*(*x).next)).next;
    

Ответы

Ответ 1

Как вы сами написали, создается кольцевой список. А это означает, что последний элемент
списка указывает на первый элемент списка.
Так сказать, все встали в круг и взялись за руки.:)

В этих предложениях

link t = new node(1, 0);
t->next = t;    


создается первый элемент списка

link t = new node(1, 0);


который указывает сам на себя

t->next = t;    


Затем в цикле создаются еще три элемента

link x = t;
for (int i = 2; i < 5; i++)
    x = (x->next = new node(i, t));


Каждый раз при добавлении нового элемента его поле next указывает на первый элемент

new node(i, t)


Указатель этого созданного элемента присваивается полю next предыдущего элемента,
а переменная x получает значение созданного указателя.

Можно вставить отладочную печать

#include 

struct node 
{
    int item;
    node *next;

    node(int x, node *t){
        item = x;
        next = t;
    }
};

int main()
{
    typedef node *link;

    link t = new node( 1, 0 );
    t->next = t;    
    link x = t;

    for ( int i = 2; i < 5; i++ )
    {
        x = ( x->next = new node( i, t) );
    }        

    do
    {
        x = x->next;
        std::cout << "current: " << ( void * )x 
                  << ", value: " << x->item
                  << ", next: " << ( void * )x->next
                  << std::endl;
    } while ( x->next != t );

    return 0;
}


И получить примерно следующий вывод на консоль

current: 0x9cc570, value: 1, next: 0x9cc590
current: 0x9cc590, value: 2, next: 0x9cbda0
current: 0x9cbda0, value: 3, next: 0x9cbdc0
current: 0x9cbdc0, value: 4, next: 0x9cc570


Как видно, последний элемент в списке указывает на первый элемент в списке, который
имеет адрес 0x9cc570

В этой тестовой программе цикл do-while начинается с предложения

x = x->next;


потому что перед этим в другом цикле при создании элементов x - это указатель последнего
созданного элемента и его поле next указывает на первый элемент списка. Потому данное
предложение при первой итерации цикла как раз и переходит на первый элемент списка.

Экспериментируйте с программой из книги и смотрите, что получается!


Ответ 2

Если записать этот код нормально, то будет

node* t = new node(1, nullptr); // создаем новый элемент с типом node,
// в его конструктор передаем 1 (поле item) и нулевой указатель (поле next)
t->next = t; // делаем так чтобы поле next указывало на самого себя


Мы не можем написать node* t = new node(1, t);, потому что в момент вызова конструктора
переменная t еще не заполнена.