Реверсивный двухсвязный Deque в C - PullRequest
Новая
       19

Реверсивный двухсвязный Deque в C

1 голос
/ 20 июля 2010

У меня возникают проблемы при обращении моего двойного связанного списка deque (только с задним стражем) в C, я подхожу к нему, переключая указатели, и вот код, который у меня есть: 

/* Reverse the deque

 param:  q  pointer to the deque
 pre: q is not null and q is not empty
 post:  the deque is reversed
*/
/* reverseCirListDeque */
void reverseCirListDeque(struct cirListDeque *q)
{
 struct DLink *back = q->backSentinel;
 struct DLink *second = q->backSentinel->prev;
 struct DLink *third = q->backSentinel->next;

 while (second != q->backSentinel->next){
  back->next = second;
  third = back->prev;
  back->next->prev = back;
  back = second;
  second = third;
 }
}

Но, похоже, это не сработало, я тестировал его с декой, которая выглядит примерно так: 1, 2, 3 Вывод: 3, и этот процесс, кажется, портит действительное значение чисел.то есть.2 становится 2.90085e-309 ... Я думаю, что переключение указателя нарушено, но я не могу найти проблему.И хотя это не значит, что мой код верен;хорошо компилируется.

Ответы [ 3 ]

2 голосов
/ 20 июля 2010

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

Сначала вы решили сделать это, поменяв указатели, право?Итак, напишите функцию для замены указателей: 

void swapCirListDequePointers(
    struct cirListDeque** left,
    struct cirListDeque** right)
{
    struct cirListDeque* temp = *left;
    *left = *right;
    *right = temp;
}

Теперь напишите функцию, которая инвертирует указатели в одном узле: 

void swapPointersInCirListDeque(struct cirListDeque* q)
{
    swapCirListDequePointers(&(q->prev),&(q->next));
}

Теперь, рекурсивно сложите это вместе: 

void reverseCirListDeque(struct cirListDeque* q)
{
    if(q == q->backSentinel)
        return;

    swapPointersInCirListDeque(q);

    // Leave this call in tail position so that compiler can optimize it
    reverseCirListDeque(q->prev); // Tricky; this used to be q->next
}

Я не уверен точно, как устроена ваша структура;моя функция предполагает, что ваша очередь круговая, и вы будете вызывать ее на страже.

РЕДАКТИРОВАТЬ: Если ваша очередь не круглая, вы также захотите позвонить swapPointersInCirListDeque(q) на страже, поэтому переместите swapPointersInCirListDeque(q) перед оператором if.

Если после этого вы планируете использовать backSentinel, вы должны также изменить это, поскольку теперь он находится в начале списка.Если у вас есть frontSentinel, вы можете просто добавить swapCirListDequePointers(&(q->frontSentinel),&(q->backSentinel)); к swapPointersInCirListDeque.В противном случае вам придется передать первый узел вместе с q и установить для него q->backSentinel.

1 голос
/ 20 июля 2010

Если это двусвязный список, вам вообще не нужно менять указатели.Просто поменяйте местами полезные данные: 

pointer1 = first
pointer2 = last
while pointer1 != pointer2 and pointer2->next != pointer1:
    temp = pointer1->payload
    pointer1->payload = pointer2->payload
    pointer2->payload = temp
    pointer1 = pointer1->next
    pointer2 = pointer2->prev

Если под обратным стражем вы имеете в виду указатель last (так как в нем нет первого указателя), то вам нужно сделать шаг назад и бросить деку, чтобы найти ее.Однако трудно поверить, что это будет так, поскольку это будет довольно неэффективный deque (который должен быть двусторонней очередью).

0 голосов
/ 20 июля 2010

Вам уже дали пару предложений; вот еще одна возможность: 

// Assumes a node something like:
typedef struct node { 
    struct node *next, *prev;
    int data;
} node;

, а также предполагает наличие пары переменных (на данный момент глобальных) с именами head и tail, которые указывают соответственно на голову и хвост deque. 

void reverse()  {
    node *pos = head;
    node *temp = pos->next;

    head = tail;
    tail = pos;

    while (pos != NULL) {
        node *t = pos->prev;
        pos->prev = pos->next;
        pos->next = t;
        pos = temp;
        if (temp)
            temp = temp->next;
    }   
}

По крайней мере, на данный момент это не предполагает наличие каких-либо часовых - просто NULL-указатели для обозначения концов списка.

Если вы просто храните int s в деке, предложение Паксдиабло является хорошим (за исключением того, что создание двусвязного узла, содержащего только int, является большой тратой). Предполагая, что в действительности вы хранили что-то достаточно большое, чтобы узлы с двойной связью имели смысл, вы также предпочли бы избегать перемещения этих данных больше, чем необходимо, по крайней мере, как общее правило.

...