Двойной круговой связанный список.Новый узел не вставляется.C ++ - PullRequest
Новая
       29

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

1 голос
/ 07 мая 2011

Таким образом, этот новый узел должен быть вставлен после последнего узла. Я не могу понять, почему этого не происходит. Примечание: список имеет несколько элементов до вызова этой функции (около 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;

}

1 Ответ

3 голосов
/ 07 мая 2011

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

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

Node* Q = top;
do {
    cout << Q->stId << endl;
    Q = Q->next;
} while (Q != top);
...