Методы Push_front и push_back для связанного списка, кажется, удаляют узел - PullRequest
Новая
       51

Методы Push_front и push_back для связанного списка, кажется, удаляют узел

0 голосов
/ 08 июля 2019

Я пишу класс с именем Playlist, который выполняет различные операции на PlaylistNodes. Я посмотрел в Интернете и попытался реализовать методы push_back и push_front, но безуспешно. 

PlaylistNode *PlaylistNode::insert_next(PlaylistNode *p) {
    PlaylistNode *tmp = nullptr;

    tmp = this->next;
    this->next = p;
    p->next = tmp;

    return p;
}

Playlist::Playlist() {
    head = new PlaylistNode;
    prevToCurr = head;
    tail = head;
    size = 0;
}

Playlist *Playlist::push_back(PlaylistNode *p) {
    PlaylistNode *tmp;

    tmp = tail;
    tmp->insert_next(p);
    tail = p;

    prevToCurr = tail;

    size++;
    return this;
}

Playlist *Playlist::push_front(PlaylistNode *p) {
    size++;

    PlaylistNode *tmp = head;
    head = p;
    head->insert_next(tmp);

    return this;
}

Когда я бегу: 

play.push_front(node1);
play.push_front(node2);
play.push_front(node2);

затем распечатайте связанный список, я получу только 2 узла: 

ID 44: song2
ID 33: song1

Ответы [ 2 ]

1 голос
/ 08 июля 2019

Ваш метод инициализации (конструктор) не выполняет то, что должен.При построении этого типа списка голова и хвост должны указывать на ноль, поскольку список пуст.Я не уверен, что делает «prevToCurr», но я не думаю, что списки используют что-то подобное, поэтому я бы избавился от этого: 

Playlist::Playlist() {
    head = null;
    tail = null;
    size = 0;
}

Для простоты обработайте push_front () в 2 случаях: когдасписок пуст, и когда в списке есть узлы.

  1. Если список пуст, все, что вам нужно сделать, это сделать так, чтобы голова и хвост указывали на новый узел.
  2. Когда списокне пусто, вы указываете предыдущую точку заголовка на новый узел и обновляете заголовок списка.

будет выглядеть так: 

Playlist *Playlist::push_front(PlaylistNode *p) {
    if (size == 0) {
        head = p;
        tail = p;
    }
    else {
        head->insertNext(p);
        head = p;
    }
    size++;
    return this;
}

Ваш метод push_back () будетреализован почти так же, как push_front, обновляя хвост вместо головы и делая новый хвост, указывающий на старый, я уверен, что вы можете понять это.

Вы не даете достаточно информации, поэтому ясобираюсь угадать ваш PlaylistNode :: insertNext устанавливает следующий узел.В этом случае, то, что вы делаете здесь, это устанавливает следующий указатель на узел, указанный в качестве аргумента: 

PlaylistNode *PlaylistNode::insert_next(PlaylistNode *p) {
    this->next = p;
    return this;
}

Это должно работать более или менее, если вы правильно создаете свои PlaylistNodes (ненажмите на один и тот же узел 2 раза, в результате вы получите узел, указывающий рядом с собой, как указано в комментариях).

0 голосов
/ 08 июля 2019

Как отмечено в комментариях, это трудно понять без всего кода, поэтому мы должны сделать вывод. Работая в обратном направлении от того, что могло вызвать это, мы предполагаем, что узел, переданный в push_front, имеет нулевой указатель next. Тогда ваша insert_next функция примет нулевой указатель этого нового узла и неправильно обновит указатель next вставленного узла на нулевой, независимо от того, что было раньше.

...