У меня проблема со структурой данных, связанная с двусвязным циклическим списком в 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 поставляется.
В посте много ненужного кода. Пожалуйста, постарайтесь свести это к минимально воспроизводимому примеру
сокращение вашего кода до минимума значительно облегчит вам чтение кода и его отладку. И если вы сократили его до минимума и все еще не можете обнаружить проблему, у вас есть хороший повод опубликовать здесь.
добавление ...
не делает пример воспроизводимым. Код, который сейчас находится в вопросе, не компилируется и, следовательно, не выдает неправильный вывод.
mre — это код, который другие могут скопировать и вставить, чтобы скомпилировать его и увидеть тот же результат, что и вы.
вы можете уделять столько времени, сколько вам нужно. Часто, когда их просят сделать mre, пользователи нервничают и портят собственный вопрос. Скорее вам следует сделать шаг назад, зайти в редактор, отредактировать код, скомпилировать его, посмотреть выходные данные, посмотреть, сохраняется ли проблема, повторять это до тех пор, пока проблема не исчезнет, а затем вернуться на одну итерацию назад (чтобы проблема снова возникла). ), опубликуйте этот код. Это может занять несколько часов. Никто не говорил, что программирование будет простым: P. Но оно того стоит, потому что чаще всего во время этого процесса вы сами обнаружите проблему.
Например, в вашей программе вы не используете InsertFront
, поэтому его следует удалить. Также попробуйте более короткий список, чем 10 элементов, и более короткий цикл, чем 15 элементов. Все, что вы можете сделать, чтобы уменьшить объем кода или упростить проблему, сохраняя при этом воспроизведение ошибки, поможет.
Понял, всем спасибо. Делаем MRE сейчас.
@benhpark Если бы мне пришлось догадываться, я бы сказал, что ваш дополнительный узел добавляется при создании списка (т. е. в конструкторе списка). Похоже, ваш код предполагает, что head
никогда не бывает nullptr
, так что же происходит, когда создается список?
Вы разрываете круговую цепочку при каждом вставке. Смотрите добавленные комментарии:
// [...]
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-cpp
Спасибо! Я буду смотреть в него.
Ваш код итератора не учитывает узел head
.
Извините, не могли бы вы уточнить, что вы подразумеваете под кодом итератора?
Я удивлен, кажется, мне нужно объяснить DCListNode<Type>* DCListIterator<Type>::Next()
.
@benhpark Internalpointers.com/post/writing-custom-iterators-modern-cpp