4

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

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;

5
  • 1
    next в структуре node это указатель на следующую такую структуру в цепочке (а не на int). Указатель это по сути адрес блока памяти где лежит структура. зачем делают t->next=t сказать сложно. надо внимательно смотреть если проверки дальнейшие. по сути они этим говорят что следующей за структурой t в цепочке идет она сама, что странно. 3-я строка абослютно не аналогична. она память не выделяет и не создает структур. это node *x=t; t как мы помним адрес структуры, вот этот адрес копируется еще и в x
    – Mike
    10 ноя 2015 в 19:39
  • Точно, ошибся, int заменил на node 10 ноя 2015 в 19:41
  • @dmitrykozyr Там же в книге должны быть какие-то слова, говорящие о том, что эта функция делает. Почему вы спрашиваете здесь вместо того, чтобы обратиться к книге? 10 ноя 2015 в 19:44
  • Спасибо за ответы, теперь более понятно. В книге это несколько раз перечитал, но только еще больше вопросов появилось) 10 ноя 2015 в 19:55
  • 1
    Да, области памяти и указатели очень простая, но сложно объяснимая вещь. Плюс автор книги явно запутывает объявляя link по сути как синоним node *. Предлагаю при чтении этого кода заменить все слова link конструкцией node * может легче понимать будет ...
    – Mike
    10 ноя 2015 в 20:01

2 ответа 2

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 <iostream>

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
  • Спасибо, теперь все намного понятней, буду экспериментировать) 10 ноя 2015 в 20:27
  • @dmitrykozyr Не за что. Спрашивайте еще.:) 10 ноя 2015 в 20:32
1

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.