Замена двух узлов в двусвязном списке

Мне нужно написать программу, которая будет по существу сортировать узлы в связанном списке. У меня есть 5 функций, которые нужно написать для этого задания, и я застрял на одной из них. У меня возникли проблемы с заменой двух узлов местами. Заголовок функции следующий:

void swap (struct lnode** head, struct lnode* n1, struct lnode* n2)

Я добился того, чтобы это работало правильно, пока два узла не находятся рядом друг с другом. Нам предоставлен файл list.h, и мы должны использовать две функции evictNode(struct lnode** head, struct lnode* node) и void insertNode (struct lnode** head, struct lnode* prevNode, struct lnode* nodeToBeInserted). Эти функции также обрабатывают переназначение указателей next и previous. Я просто не совсем уверен, как поменять местами узлы, если они находятся рядом друг с другом. Я пытался нарисовать это, но не смог осмыслить это.

Кстати, с остальными узлами я работаю с помощью следующего кода:

evictNode(head, n1);
evictNode(head, n2);
insertNode(head, n1prev, n2);
insertNode(head, n2prev, n1);

РЕДАКТИРОВАТЬ: попытки

struct lnode* temp = n2;
insertNode(head,n1prev,temp)
evictNode(head, n2)

где struct lnode* n1prev = nodeGetPrev(n1) есть две функции, возвращающие предыдущий / следующий указатели


c doubly-linked-list
person Matt Altepeter    schedule 08.10.2012    source источник
comment
Измените свой вопрос, включив сюда то, что вы пробовали.   -  person nhahtdh    schedule 09.10.2012

Ответы (1)


arrow_upward
1
arrow_downward

Я сделаю это следующим образом:

struct lnode* tmp = nodeGetPrev(n1);
/*
 * Remove n1 and insert it before n2
 * note to calling nodeGetPrev(n2) after removing n1
 */
evictNode( head, n1 );
insertNode( head, nodeGetPrev(n2), n1 );
/* If n2 were before n1 and we insert n1 before n2, swap is done */
if( tmp != n2 ) {
    evictNode( head, n2 );
    insertNode( head, tmp, n2 );
}
person BigBoss    schedule 09.10.2012
comment
Большое тебе спасибо. Сработало отлично! - person Matt Altepeter; 09.10.2012