Проблема Добавление элемента в конец двусвязного списка

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

#include<iostream>
using namespace std;

class doubleLinkedList
{
private:
class node
{
public:
int data;
node* next;
node* prev;
node(int x)
{
data = x;
next = NULL;
prev = NULL;
}
};
public:
node* head;
node* tail;
int count;doubleLinkedList();        //default constructor
~doubleLinkedList();      //destructor

void displayForward();    //display items from front to back
void displayBackward();   //display items from back to front

void addFront(int);      //add item to front of linked list
void addBack(int);       //add item to back of linked list

int removeFront();       //remove item from front of linked list
int removeBack();        //remove item from back of linked list
};

//constructor
doubleLinkedList::doubleLinkedList(){
head = tail = NULL;
count = 0;
}//destructor
doubleLinkedList::~doubleLinkedList(){
node* current = head;

while(current != NULL)
{
node* previous = current;
current = current->next;
delete previous;
}

head = tail = NULL;
count = 0;
}//display items in linked list from front to back
void doubleLinkedList::displayForward(){
node* pCurrent = head;
while (pCurrent != NULL)
{
cout << pCurrent->data << " ";
pCurrent = pCurrent->next;
}
cout << count;
}//display items in linked list from back to front
void doubleLinkedList::displayBackward(){
node* pCurrent = tail;
while (pCurrent != NULL)
{
cout <<pCurrent->data << " ";
pCurrent = pCurrent->prev;
}
cout << count;
}//add item to front of linked list
void doubleLinkedList::addFront(int x){

node* n = new node(x);
n->next = head;
n->prev = NULL;

if (head != NULL)
head->prev = n;
head = n;
count++;

if (tail == NULL)
tail = n;
}

void doubleLinkedList::addBack(int x){
node* n = new node(x);

n->next = NULL;
n->prev = tail;
tail = n;

count++;
}

//////////////////// Мой тестовый код: ///////////////////

int main()
{
doubleLinkedList list;

list.addBack(40);
list.addBack(50);
list.addBack(60);
list.addFront(30);
list.addFront(20);
list.addBack(70);
list.addBack(80);
list.addFront(10);

list.displayForward();  //10 20 30 8   (the 8 value is the count/size i'm keeping track of)
cout << endl;
list.displayBackward(); //80 70 60 50 40 8
cout << endl;

system("pause");
return 0;
}

Мой вывод должен отображать 10 20 30 40 50 60 70 80
и 80 70 60 50 40 30 20 10
но вместо этого мой displayForward отображает элементы, которые я добавил в Front, а мой displayBackward отображает элементы, которые я добавил в Back.

0

Решение

Вы забыли установить указатели старых хвостов на следующий хвост. Таким образом, при просмотре списка ближайший к последнему узлу все равно будет указывать на NULL.

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

Итак, вы добавили 40, 50, 60 к «концу», так что указатель хвоста был установлен и обновлен соответствующим образом, но голова не была создана, пока вы не добавили 30 к списку, продолжая добавлять элементы вперед, указатели были обновлены соответственно, но в результате голова и хвост фактически не были связаны.

void doubleLinkedList::addBack(int x){
node* n = new node(x);

if (head == nullptr)
head = n; //this was your main problem!

if (tail != nullptr)
tail->next = n;

n->next = nullptr;
n->prev = tail;
tail = n;

count++;
}

Поскольку вы, кажется, пишете код на C ++, я советую вам привыкнуть к использованию nullptr вместо NULL.

http://www.codeproject.com/Articles/570638/Ten-Cplusplus11-Features-Every-Cplusplus-Developer

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]