Почему в конце двусвязного циклического связанного списка в C++ стоит нуль?

У меня проблема со структурой данных, связанная с двусвязным циклическим списком в C++.

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

main.cpp

#include <iostream>
#include "DCList.h"

int main() {
    
    DCList<int> intList;

    // Insert elements
    std::cout << "Inserting elements 1 to 5 to the back of the list:\n";
    for (int i = 1; i <= 5; i++) {
        intList.InsertBack(i);
    }
    std::cout << "List: " << intList << std::endl;

    // Test circular nature
    std::cout << "\nTesting circular nature (printing 10 elements):\n";
    DCListIterator<int> circularIt(intList);
    for (int i = 0; i < 10; ++i) {
        std::cout << circularIt.getData() << " ";
        circularIt.Next();
    }
    std::cout << std::endl;

    return 0;
}

DCList.h

#ifndef DCLIST_H
#define DCLIST_H

#include <iostream>

//forward declarations
template <class Type> class DCList;
template <class Type> class DCListIterator;

template <class Type>
class DCListNode {
    friend class DCList<Type>;
    friend class DCListIterator<Type>;
    
    template <class T>
    friend std::ostream& operator<<(std::ostream& os, const DCList<T>& list);

  private:
    Type data;
    DCListNode *next;
    DCListNode *prev;

  public:
    DCListNode(Type element = Type(), DCListNode *n = nullptr, DCListNode *p = nullptr) 
        : data(element), next(n), prev(p) {}
};

template <class Type>
class DCList {
    friend class DCListIterator<Type>;
    
    template <class T>
    friend std::ostream& operator<<(std::ostream& os, const DCList<T>& list);

  public:
    DCList();

    void InsertFront(const Type &item);
    void InsertBack(const Type &item);
    void Insert(DCListNode<Type>* p, DCListNode<Type>* x);

  private:
    DCListNode<Type> *head;  // Head node
};

template <class Type>
class DCListIterator {
  public:
    DCListIterator(const DCList<Type> &l); //constructor
    Type getData() const;
    DCListNode<Type>* Next();
   
  private:
    const DCList<Type> &list;
    DCListNode<Type> *current;
};

// Declaration of the operator<< function
template <class Type>
std::ostream& operator<<(std::ostream& os, const DCList<Type>& list);

#include "DCList.tpp"

#endif // DCLIST_H

DCList.tpp

#include <stdexcept>

template <class Type>
DCList<Type>::DCList() {
    head = new DCListNode<Type>();
    head->next = head->prev = head;  // Circular structure
}

template <class Type>
void DCList<Type>::InsertBack(const Type &item) {
    DCListNode<Type>* newNode = new DCListNode<Type>(item);
    Insert(newNode, head);
}

template <class Type>
void DCList<Type>::Insert(DCListNode<Type>* p, DCListNode<Type>* x) {
    p->next = x;
    p->prev = x->prev;
    x->prev->next = p;
    x->prev = p;
}

// Definition of the operator<< function
template <class Type>
std::ostream& operator<<(std::ostream& os, const DCList<Type>& list) {
    DCListNode<Type>* current = list.head->next;
    if (current == list.head) {
        return os << "Empty List";
    }
    while (current != list.head) {
        os << current->data;
        if (current->next != list.head) {
            os << " <-> ";
        }
        current = current->next;
    }
    return os;
}

// DCListIterator implementations
template <class Type>
DCListIterator<Type>::DCListIterator(const DCList<Type> &l) : list(l), current(l.head->next) {}

template <class Type>
Type DCListIterator<Type>::getData() const {
    return current->data;
}

template <class Type>
DCListNode<Type>* DCListIterator<Type>::Next() {
    current = current->next;
    return current;
}

Проблема возникает в основной функции при тестировании циклического характера:

std::cout << "\nTesting circular nature (printing 10 elements):\n";
DCListIterator<int> circularIt(intList);
for (int i = 0; i < 10; ++i) {
    std::cout << circularIt.getData() << " ";
    circularIt.Next();
}

Ожидаемый результат

Inserting elements 1 to 5 to the back of the list:
List: 1 <-> 2 <-> 3 <-> 4 <-> 5

Testing circular nature (printing 10 elements):
1 2 3 4 5 1 2 3 4 5

но фактический результат

Inserting elements 1 to 5 to the back of the list:
List: 1 <-> 2 <-> 3 <-> 4 <-> 5

Testing circular nature (printing 10 elements):
1 2 3 4 5 0 1 2 3 4

Как показано выше, список завершается дополнительным нулем в конце списка. Что-то не так с моей структурой данных? Если да, то как я могу исправить это, чтобы переключиться с 5 на 1?

Редактировать: MRE поставляется.

В посте много ненужного кода. Пожалуйста, постарайтесь свести это к минимально воспроизводимому примеру

463035818_is_not_an_ai 31.07.2024 08:50

сокращение вашего кода до минимума значительно облегчит вам чтение кода и его отладку. И если вы сократили его до минимума и все еще не можете обнаружить проблему, у вас есть хороший повод опубликовать здесь.

463035818_is_not_an_ai 31.07.2024 08:52

добавление ... не делает пример воспроизводимым. Код, который сейчас находится в вопросе, не компилируется и, следовательно, не выдает неправильный вывод.

463035818_is_not_an_ai 31.07.2024 08:57

mre — это код, который другие могут скопировать и вставить, чтобы скомпилировать его и увидеть тот же результат, что и вы.

463035818_is_not_an_ai 31.07.2024 08:58

вы можете уделять столько времени, сколько вам нужно. Часто, когда их просят сделать mre, пользователи нервничают и портят собственный вопрос. Скорее вам следует сделать шаг назад, зайти в редактор, отредактировать код, скомпилировать его, посмотреть выходные данные, посмотреть, сохраняется ли проблема, повторять это до тех пор, пока проблема не исчезнет, ​​а затем вернуться на одну итерацию назад (чтобы проблема снова возникла). ), опубликуйте этот код. Это может занять несколько часов. Никто не говорил, что программирование будет простым: P. Но оно того стоит, потому что чаще всего во время этого процесса вы сами обнаружите проблему.

463035818_is_not_an_ai 31.07.2024 09:00

Например, в вашей программе вы не используете InsertFront, поэтому его следует удалить. Также попробуйте более короткий список, чем 10 элементов, и более короткий цикл, чем 15 элементов. Все, что вы можете сделать, чтобы уменьшить объем кода или упростить проблему, сохраняя при этом воспроизведение ошибки, поможет.

john 31.07.2024 09:03

Понял, всем спасибо. Делаем MRE сейчас.

benhpark 31.07.2024 09:08

@benhpark Если бы мне пришлось догадываться, я бы сказал, что ваш дополнительный узел добавляется при создании списка (т. е. в конструкторе списка). Похоже, ваш код предполагает, что head никогда не бывает nullptr, так что же происходит, когда создается список?

john 31.07.2024 09:11
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
9
74
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Вы разрываете круговую цепочку при каждом вставке. Смотрите добавленные комментарии:

// [...]
void DCList<Type>::InsertBack(const Type &item) {
    DCListNode<Type>* newNode = new DCListNode<Type>(item); // newNode prev and next are nullptr
    Insert(newNode, head);
}

template <class Type>
void DCList<Type>::Insert(DCListNode<Type>* p, DCListNode<Type>* x) {
    p->next = x;
    p->prev = x->prev; // x->prev is nullptr
    // p->prev is now nullptr, breaking the cycle
// [...]

Позже это приводит к UB, поскольку вы несколько разыменовываете nullptr, что с вашим уровнем компилятора и оптимизации демонстрирует неожиданное поведение, которое вы наблюдаете.

Несвязано: ваш итератор должен соответствовать идиоматическому способу определения итераторов в C++, чтобы можно было использовать iterator_traits.

Вот, что почитать: Internalpointers.com/post/writing-custom-iterators-modern-cp‌​p

YSC 31.07.2024 10:22

Спасибо! Я буду смотреть в него.

benhpark 31.07.2024 10:29

Ваш код итератора не учитывает узел head.

Извините, не могли бы вы уточнить, что вы подразумеваете под кодом итератора?

benhpark 31.07.2024 10:09

Я удивлен, кажется, мне нужно объяснить DCListNode<Type>* DCListIterator<Type>::Next().

greybeard 31.07.2024 10:14

Другие вопросы по теме