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

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

Ответ

Как вы сами написали, создается кольцевой список. А это означает, что последний элемент списка указывает на первый элемент списка. Так сказать, все встали в круг и взялись за руки.:)
В этих предложениях
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 указывает на первый элемент списка. Потому данное предложение при первой итерации цикла как раз и переходит на первый элемент списка.
Экспериментируйте с программой из книги и смотрите, что получается!