2

嘿 Stackoverflow 我正在做我的作业，我正在尝试反转一个没有哨兵的循环链接双端队列。这是我的数据结构：

struct DLink {

 TYPE value;

 struct DLink * next;

 struct DLink * prev;
};

struct cirListDeque {

 int size;
 struct DLink *back;
};

这是我扭转双端队列的方法：

void reverseCirListDeque(struct cirListDeque* q) {

struct DLink* current;

struct DLink* temp;



temp = q->back->next;

q->back->next = q->back->prev;

q->back->prev = temp;



current = q->back->next;

while(current != q->back) {

    temp = current->next;

    current->next = current->prev;

    current->prev = temp;



    current = current->next;

}

}

但是，当我运行它并在其上放置值 1、2 和 3（在这种情况下，TYPE 只是 int 的别名）并反转它时，我得到 2、1、3。有没有人对我可能在做什么有任何想法错误的？

提前致谢。

4

4 回答 4

2

无论何时使用抽象数据类型——列表、队列、双端队列等，只要涉及指针，将数据结构及其指针绘制到纸上的图表中确实很有帮助。标记一切。然后编码你所看到的。这真的让它变得容易多了。我从大学开始就没有使用过双端队列，但请确保您没有混淆 prev、next 和 back，因为这可能是问题所在。还要确保在取消引用它们之前检查空指针。

希望这会有所帮助，而不会直接给出答案。你的教授可能会欣赏这一点。;-)

于 2010-04-30T20:53:14.420 回答
1 
current = q->back->next;

while(current != q->back->next)
{
    /* This code will never run, cause you guaranteed right before the while
     * that current == q->back->next .
     */
}

更新：您现在需要做的是，一旦您反转了所有指针（从您的结果来看，这似乎现在可以工作），将您的“后退”指针设置为 back->prev。

于 2010-04-30T20:27:05.673 回答
1

不是您问题的直接答案，但回到学校，我发现Data Display Debugger对调试此类问题非常有用。

于 2010-04-30T20:58:14.727 回答
0

最简单和最快的方法是只改变你对队列方向的解释。

方向将存储在 cirListDeque 中，并且您从节点到节点的移动将在了解队列当前方向的情况下完成。

于 2010-04-30T20:56:28.347 回答