двусвязный список: значение не вставляется спереди
Вот реализация DLinkedList, элемент типа int добавляется к нему с помощью addFront (), но не извлекается с помощью front (). Ошибка не отображается. Не знаю почему ?? Вот полная реализация. Код запускается на xCode4.5.
int main(int argc, const char * argv[])
{
DLinkedList listOne;
if(listOne.empty()){
cout<<"Empty";
}
const int num=23;
listOne.addFront(num);
//Here 0 is returned from front(), while it should be 23;
cout<<listOne.front()<<endl;
return 0;
}
//Node Defination
class DNode { // doubly linked list node
private:
int elem; // node element value
DNode* prev; // previous node in list
DNode* next; // next node in list
friend class DLinkedList; // allow DLinkedList access
};
class DLinkedList { // doubly linked list
public:
DLinkedList(); // constructor
~DLinkedList(); // destructor
bool empty() const; // is list empty?
const int front() const; // get front element
const int back() const; // get back element
void addFront(const int e); // add to front of list
void addBack(const int e); // add to back of list
void removeFront(); // remove from front
void removeBack(); // remove from back
private: // local type definitions
DNode* header; // list sentinels
DNode* trailer;
protected: // local utilities
void add(DNode* v, const int e); // insert new node before v
void remove(DNode* v); // remove node v
};
void listReverse(DLinkedList& L) { // reverse a list
DLinkedList T; // temporary list
while (!L.empty()) { // reverse L into T
int s = L.front(); L.removeFront();
T.addFront(s);
}
while (!T.empty()) { // copy T back to L
int s = T.front(); T.removeFront();
L.addBack(s);
}
}
void DLinkedList::remove(DNode* v) { // remove node v
DNode* u = v->prev; // predecessor
DNode* w = v->next; // successor
u->next = w; // unlink v from list
w->prev = u;
delete v;
}
void DLinkedList::removeFront() // remove from font
{ remove(header->next); }
void DLinkedList::removeBack() // remove from back
{ remove(trailer->prev); }
// insert new node before v
void DLinkedList::add(DNode* v, const int e) {
DNode* u = new DNode; u->elem = e; // create a new node for e
std::cout<<u->elem<<std::endl;
u->next = v; // link u in between v
u->prev = v->prev; // ...and v->prev
v->prev->next = v->prev = u;
}
void DLinkedList::addFront(const int e) // add to front of list
{
add(header->next, e);
}
void DLinkedList::addBack(const int e) // add to back of list
{ add(trailer, e); }
DLinkedList::~DLinkedList() { // destructor
while (!empty()) removeFront(); // remove all but sentinels
delete header; // remove the sentinels
delete trailer;
}
DLinkedList::DLinkedList() { // constructor
header = new DNode; // create sentinels
trailer = new DNode;
header->next = trailer; // have them point to each other
trailer->prev = header;
std::cout<<"DLinkedListConstructor"<<std::endl;
}
bool DLinkedList::empty() const // is list empty?
{ return (header->next == trailer); }
const int DLinkedList::front() const // get front element
{ return header->next->elem; }
const int DLinkedList::back() const // get back element
{ return trailer->prev->elem; }
Решение
Проблема с вашим add функция:
// insert new node before v
void DLinkedList::add(DNode* v, const int e) {
DNode* u = new DNode; u->elem = e; // create a new node for e
std::cout<<u->elem<<std::endl;
u->next = v; // link u in between v
u->prev = v->prev; // ...and v->prev
v->prev->next = v->prev = u;
}
Давайте проследим это до конца. Вы начинаете со следующей ситуации (я назвал узел, который v->prev указывает на p):
┌───────────┐
│ ▼
p ◀──────── v
u
Затем вы установите u->next в v:
┌───────────┐
│ ▼
p ◀──────── v
▲
u─────┘
А потом u->prev в v->prev:
┌───────────┐
│ ▼
p ◀──────── v
▲ ▲
└─────u─────┘
Следующая строка — это проблема. Сначала это назначает u в v->prev:
┌───────────┐
│ ▼
p ┌──── v
▲ ▼ ▲
└─────u─────┘
Затем он назначает тот же указатель v->prev->next, Но v->prev сейчас uтак что вы просто устанавливаете u->next указать на v и это уже делает. Так что без изменений.
Теперь, когда вы пытаетесь получить передний элемент, вы просто получаете элемент v, который является вашим дозорным узлом.
Вам нужно выполнить эти два задания отдельно:
v->prev->next = u;
v->prev = u;
Другие решения
Прежде всего, вы не инициализируете prev а также next указатели для все ваших узлов. Когда вы создаете список, конструктор вашего списка делает:
header = new DNode; // create sentinels
trailer = new DNode;
header->next = trailer; // have them point to each other
trailer->prev = header;
Что значит header->prev а также trailer->next неинициализированы. Эти указатели не инициализируются NULL автоматически, так что будьте осторожны.
Но коренная причина того, что вы наблюдаете, заключается в том, что в вашем add_front() функция, вы вызываете add() функция, которая в конечном итоге делает это:
// Replacing v with header->next, which is the actual argument of the call
...
u->next = header->next; // u->next = trailer
u->prev = header->next->prev; // u->prev = trailer->prev; // Uninitialized!
header->next->prev = u; // trailer->prev = u;
header->next->prev->next = u; // u->next = u
Что явно неверно из-за последнего утверждения и потому, что вы никогда не назначаете header->next = u,
Кстати, я предлагаю вам рассмотреть возможность использования умных указателей вместо сырых указателей, с правильным выбором в соответствии с желаемой семантикой владения. Помимо прочего, интеллектуальные указатели автоматически инициализируются на nullptr,
Код прекрасно работал на Mingw Compiler в Windows и дал 23, а не 0, используя кодовые блоки ….
Тем не менее, я предлагаю внести следующие изменения, так как некоторые компиляторы присваивают значения справа налево, стек вещь ….
void DLinkedList::add(DNode* v, const int e) {
DNode* u = new DNode; u->elem = e; // create a new node for e
std::cout<<u->elem<<std::endl;
u->next = v; // link u in between v
u->prev = v->prev; // ...and v->prev
v->prev->next = u; // do this first......
v->prev = u; // then this.
}