c - 在 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 errors而且它往往会导致令人困惑的大型函数。

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

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