Проблема вывода двунаправленного списка(а также возможна проблема в методе Swap(), хочу заменить в нём элемент, на новый)
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *prev, *next;
};
class List
{
Node *head, *tail;
int count;
public:
List ();
~List ();
Node *GetElem (int);
void DellAll ();
void Dell (int pos);
void Insert (int pos = 0);
void TailAdd (int n);
void HeadAdd (int n);
void Print (int pos);
Node *Swap (int pos, Node * elem);
void Print ();
};
List::List ()
{
head = tail = NULL;
count = 0;
}
List::~List ()
{
DellAll ();
}
void
List::HeadAdd (int n)
{
Node *temp = new Node;
temp->prev = NULL;
temp->data = n;
temp->next = head;
if (head != 0)
temp->prev = temp;
if (count == 0)
head = tail = NULL;
else
head = temp;
count++;
}
void
List::TailAdd (int n)
{
Node *temp = new Node;
temp->next = NULL;
temp->data = n;
temp->prev = tail;
if (tail != 0)
temp->next = temp;
if (count == 0)
head = tail = temp;
else
tail = temp;
count++;
}
void
List::Insert (int pos)
{
if (pos == 0)
{
cout << "Enter a position";
cin >> pos;
}
if (pos < 1 || pos > count + 1)
{
return;
}
if (pos == count + 1)
{
int data;
cout << "Enter a new data:";
cin >> data;
TailAdd (data);
return;
}
else if (pos == 1)
{
int data;
cout << "Enter a new data:";
cin >> data;
HeadAdd (data);
return;
}
int i = 1;
Node *Ins = head;
while (i < pos)
{
Ins = Ins->next;
i++;
}
Node *PrevIns = Ins->prev;
Node *temp = new Node;
cout << "Enter a new data:";
cin >> temp->data;
if (PrevIns != 0 && count != 1)
PrevIns->next = temp;
temp->next = Ins;
temp->prev = PrevIns;
Ins->prev = temp;
count++;
}
void
List::Print ()
{
if (count != 0)
{
Node *temp = head;
cout << "( ";
while (temp->next != 0)
{
cout << temp->data << ", ";
temp = temp->next;
}
cout << temp->data << " )\n";
}
}
void
List::Dell (int pos)
{
if (pos == 0)
{
cout << "Enter a position";
cin >> pos;
}
if (pos < 1 || pos > count)
{
return;
}
int i = 1;
Node *Del = head;
while (i < pos)
{
Del = Del->next;
i++;
}
Node *PrevDel = Del->prev;
Node *AfterDel = Del->next;
if (PrevDel != 0 && count != 1)
PrevDel->next = AfterDel;
if (AfterDel != 0 && count != 1)
AfterDel->prev = PrevDel;
if (pos == 1)
head = AfterDel;
if (pos == count)
tail = PrevDel;
delete Del;
count--;
}
void
List::DellAll ()
{
while (count != 0)
Dell (1);
}
void
List::Print (int pos)
{
if (pos < 1 || pos > count)
{
return;
}
Node *temp;
if (pos <= count / 2)
{
temp = head;
int i = 1;
while (i < pos)
{
temp = temp->next;
i++;
}
}
else
{
temp = tail;
int i = 1;
while (i <= count - pos)
{
temp = temp->prev;
i++;
}
}
cout << pos << " element: ";
cout << temp->data << endl;
}
Node *
List::GetElem (int pos)
{
Node *temp = head;
if (pos < 1 || pos > count)
{
return 0;
}
int i = 1;
while (i < pos && temp != 0)
{
temp = temp->next;
i++;
}
if (temp == 0)
return 0;
else
return temp;
}
Node *
List::Swap (int pos, Node * elem)
{
Node *temp = head;
if (pos < 1 || pos > count)
{
return 0;
}
int i = 1;
while (i < pos && temp != 0)
{
temp = temp->next;
i++;
}
if (temp == 0)
return 0;
else
temp = elem;
return temp;
}
int
main ()
{
List L;
const int n = 10;
int a[n] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < n; i++)
if (i % 2 == 0)
L.HeadAdd (a[i]);
else
L.TailAdd (a[i]);
cout << "List L:\n";
L.Print ();
cout << endl;
cin.get ();
return 0;
}
Ответы (1 шт):
Вывод у вас правильный. Ошибки у вас при добавлении элементов в список.
В функции добавления в начало вы создаете элемент, а потом начинаете творить непотребное. Если список не пустой, первый элемент закольцовывается сам на себя. При том, что при проходе по списку окончание прохода у вас проверяется на значение NULL. Далее если в списке не было элементов - вы просто выкидываете только что созданный элемент в никуда.
List::HeadAdd (int n)
{
Node *temp = new Node; // создали элемент, всё хорошо
temp->prev = NULL;
temp->data = n;
temp->next = head;
if (head != 0) // первый элемент закольцовывается сам на себя
temp->prev = temp;
if (count == 0)
head = tail = NULL; // потеря только что созданного элемента
else
head = temp;
То же самое в функции TailAdd() - последний элемент закольцовывается сам на себя. В принципе так тоже можно, но тогда при проходе по списку, нужно проверять конец списка по признаку p->next == p. Но зачем? Проще искать NULL
List::TailAdd (int n)
{
Node *temp = new Node;
temp->next = NULL;
temp->data = n;
temp->prev = tail;
if (tail != 0)
temp->next = temp; // закольцовка на себя
В функции Dell() вы не полностью отработали ситуацию удаления первого и последнего элемента.
List::Dell (int pos)
{
....
Node *PrevDel = Del->prev;
Node *AfterDel = Del->next;
if (PrevDel != 0 && count != 1)
PrevDel->next = AfterDel;
if (AfterDel != 0 && count != 1)
AfterDel->prev = PrevDel;
// а если это первый элемент списка? - вы забыли о AfterDel->prev
// а если это последний элемент списка? - вы забыли о PrevDel->next
if (pos == 1)
head = AfterDel;
if (pos == count)
tail = PrevDel;
Функция Swap() тоже странная какая-то. По сути, вам нужно поменять между собой значения элементов. Сами элементы менять не надо, указатели переприсваивать не надо. А у вас в конце трэш - вы просто одному указателю присваиваете другой. Если это был элемент не из списка, то вы просто теряете всё, что было в списке после присваиваемого. А если меняете два элемента из списка между собой - то теряете всё, что было между ними. И т.д., то есть получаете множество спецэффектов. Ну и условие if (temp == 0) return 0; никогда не выполняется, т.к. уже сделана проверка на попадания элемента в диапазон списка.
Node *
List::Swap (int pos, Node * elem)
{
temp = // находим искомый элемент списка
if (temp == 0)
return 0; // никогда не выполняется
else
temp = elem; // дичь !!!
return temp;
}
Ну и несколько замечаний по коду.
У вас много где повторяется код по вводу позиции или значения. Раз код повторяется - вынесите его в отдельную функцию. И потом осуществлять ввод элемента и добавлять элемент в список - две разные сущности, по-нормальному их следует осуществлять последовательно, а не одну в другой. Т.е. сначала отработали ввод элемента или позиции, а потом выполняете функцию вставки.
List::Insert (int pos)
{
if (pos == 0)
{
cout << "Enter a position";
cin >> pos;
}
if (pos == count + 1)
{
int data;
cout << "Enter a new data:";
cin >> data;
С точки зрения производительности кода в функции DellAll() проще пройти циклом по списку и удалить все элементы, чем каждый раз вызывать Dell(), выполняя кучу проверок и переприсваивания указателей.