1

我无法在 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...我认为指针切换搞砸了，但我找不到问题。即使这并不意味着我的代码是正确的；它编译得很好。

4

3 回答 3

2

像双端队列这样的链接结构很容易递归，所以在处理链接结构时我倾向于使用递归风格。这也允许我们以增量方式编写它，以便我们可以轻松地测试每个功能。像你的函数那样循环有很多缺点：你可以很容易地引入栅栏错误，并且它往往会导致令人困惑的大型函数。

首先，您决定通过交换指针来做到这一点，对吧？所以写一个函数来交换指针：

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

于 2010-07-20T03:54:12.410 回答
1

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

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

于 2010-07-20T03:31:03.040 回答
0

您已经收到了一些建议；这是另一种可能性：

// 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 指针来表示列表的结尾。

如果您只是将ints 存储在双端队列中，Paxdiablo 的建议是一个很好的建议（除了创建一个双链接节点来仅保存 anint是一种巨大的浪费）。假设实际上您存储了足够大的东西以使双链接节点有意义，那么您也更愿意避免在不必要的情况下移动该数据，至少作为一般规则。

于 2010-07-20T04:05:07.233 回答