C 中的反转双链双端队列

Question

我在 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，这个过程似乎弄乱了数字的实际值。 IE。 2 变成 2.90085e-309...我认为指针切换混乱，但我找不到问题。即使这并不意味着我的代码是正确的；它编译得很好。

Answer 1

像双端队列这样的链接结构很容易进行递归，因此在处理链接结构时我倾向于采用递归风格。这也允许我们增量地编写它，以便我们可以轻松地测试每个函数。像你的函数一样循环有很多缺点：你可以很容易地引入 fencepost 错误 并且它倾向于令人困惑的大函数。

首先，您决定通过交换指针来做到这一点，对吗？因此，编写一个函数来交换指针：

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 设置为该节点。

Answer 2

如果它是双向链表，则根本不需要更改任何指针。只需交换有效负载：

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 指针（因为没有第一个指针可用），那么您需要向后退一步抛出双端队列才能找到它。然而，很难相信会出现这种情况，因为这将是一个相当低效的双端队列（它应该是一个双端队列）。

Answer 3

已经向您提供了一些建议；还有另一种可能性：

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

并且还假设有两个名为 head 和 tail 的变量（目前为全局变量），分别指向双端队列的头部和尾部。

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 存储在双端队列中，Paxdiablo 的建议是一个很好的建议（除了创建一个双向链接节点来仅保存 int 是一种巨大的浪费）。假设实际上您存储的数据足够大，以使双链接节点有意义，那么您还希望避免不必要地移动该数据，至少作为一般规则。