справка по отладке - поменяйте местами 2 узла списка двойных ссылок - PullRequest
Новая
       0

справка по отладке - поменяйте местами 2 узла списка двойных ссылок

0 голосов
/ 29 ноября 2011

Не могли бы вы помочь мне отладить этот код, чтобы поменять местами два узла списка двойных ссылок? Я не могу понять, что я делаю неправильно: (

вот код: 

dll* swap_node(dll *head , dll *node1 , dll *node2) {
   dll *tmp;
   int flag=0;

   if(node1->prev!=NULL) {
       node1->prev->next=node2;
   } else {
       flag=1;
   }
   if(node1->next!=NULL) {
       node1->next->prev=node2;
   }

   if(node2->prev!=NULL) {
       node2->prev->next=node1;
   }
   if(node2->next!=NULL) {
       node2->next->prev=node1;
   }

   tmp=node1->next;
   node1->next=node2->next;
   node2->next=tmp;

   tmp=node1->prev;
   node1->prev=node2->prev;
   node2->prev=tmp;

   if(flag==1) {
       head=node2;
   }
   return head;
}

Заранее спасибо

Ответы [ 2 ]

1 голос
/ 29 ноября 2011

Ваша логика не будет работать,

  1. Если node2 - первый элемент в двусвязном списке
  2. Если node1 и node2 смежны.

Пожалуйста, уточните обновленную логику, приведенную ниже. 


dll* swap_node(dll *head , dll *node1 , dll *node2) 
{ 
    dll* previous_to_node1 = NULL;
    dll* next_to_node1 = NULL;
    dll* previous_to_node2 = NULL;
    dll* next_to_node2 = NULL;

    if ((node1 == NULL) || (node2 == NULL))
         return 0;

    previous_to_node1 = node1->previous;
    next_to_node1 = node1->next;
    previous_to_node2 = node2->previous;
    next_to_node2 = node2->next;

    if (previous_to_node1 != NULL) previous_to_node1->next = node2;
    if (next_to_node1 != NULL) next_to_node1->previous = node2;
    if (pevious_to_node2 != NULL) previous_to_node2->next = node1;
    if (next_to_node2 != NULL) next_to_node2->previous = node1;

    node1->next=next_to_node2;    
    node1->previous=previous_to_node2;
    node2->next=next_to_node1;
    node2->previous=previous_to_node1;

    if (previous_to_node1 == NULL) 
    {
        return node2;
    }
    else if(previous_to_node2 == NULL)
    {
        return node1;
    }

    return head;
}
1 голос
/ 29 ноября 2011

Предположим, node1->next == node2 && node2->prev == node1. Теперь давайте проследим: 

if(node1->next!=NULL)
{
   node1->next->prev=node2;
}

Теперь node2->prev указывает на node2 само! 

if(node2->prev!=NULL)
{
    node2->prev->next=node1;
}

Теперь node2->next указывает на node1, что пока нормально.

Напомним, что node1->next по-прежнему указывает на node2, а node2->next указывает на node1. 

tmp=node1->next;  // == node2
node1->next=node2->next; // == node1 (!)
node2->next=tmp;  // == node2

Итак, node1->next указывает на node1, а node2->next на node2. Совершенно неправильно.

Напомним, что node2-> prev указывает на node2, хотя node1->prev является правильным. 

tmp=node1->prev; // correct
node1->prev=node2->prev; // == node2
node2->prev=tmp; // correct

То есть node1->prev указывает на node2, что правильно.

Но node1->next и node2->next все еще не правы!

Как это решить? Это не однострочник, потому что есть пара особых случаев.

Возможно, обнаружите особый случай, который я описал, и получите для него отдельный код (и не забывайте об этом другом особом случае).

Написание этого кода оставлено читателю в качестве упражнения;)

...