Дважды круговой связанный список. Новый узел не вставляется. С++

Таким образом, этот новый узел должен быть вставлен после последнего узла. Я не могу понять, почему этого не происходит. Примечание. В списке есть несколько элементов до вызова этой функции (около 5), поэтому на данный момент он должен работать только для этого случая. Последний узел должен указывать на верхний узел, а указатель top->prev должен указывать на последний узел. Где я ошибся? Я предполагаю, что это неправильно, потому что последний узел никогда не печатает, когда вызывается функция печати

void CircularDLL::insertAfterLast (int id, string name, string email, int age)
{
 Node* N=new Node;

 N->stId=id;
 N->stName=name;
 N->stEmail=email;
 N->stAge=age;

 Node* Q=top;

 while(Q->next!=top)//get to the last node
 {
  Q=Q->next;
 }
 cout<<"Q next is top now"<<endl;
 Q->next=N;
 N->prev=Q;
 N->next=top;
 top->prev=N;

}

c++ linked-list doubly-linked-list circular-list
person Tyler Pfaff    schedule 06.05.2011    source источник
comment
Можете ли вы опубликовать свою функцию печати? Может быть, это то, что неправильно.   -  person Jacob    schedule 07.05.2011
comment
Если это круговой двусвязный список, почему бы не использовать top->prev для перехода к последнему узлу?   -  person Alexey Kukanov    schedule 07.05.2011

Ответы (1)


arrow_upward
3
arrow_downward

Этот код имеет несколько проблем. Во-первых, если вы собираетесь часто выполнять "insertAfterLast", вам следует использовать "top->prev", чтобы получить указатель на последний элемент за постоянное время; в противном случае построение списка потребует квадратичного (O(n^2)) времени. Во-вторых, в любом реальном проекте реализация кругового связанного списка с нуля почти наверняка является плохой идеей — вместо этого вы хотите придерживаться зрелого STL-совместимого контейнера, такого как std::deque или circular_buffer.

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

Node* Q = top;
do {
    cout << Q->stId << endl;
    Q = Q->next;
} while (Q != top);
person Chiara Coetzee    schedule 06.05.2011