我正在尝试创建一个双向链表。函数 push(int x) 应该向列表中添加一个节点并建立正确的链接。我使用:
class Node {
public:
int value;
Node* next;
Node* prev;
public:
Node() {}
void set_value(int x) { value = x; }
void set_next(Node* x) { next = x; }
void set_prev(Node* x) { prev = x; }
Node* get_next() { return next; }
Node* get_prev() { return prev; }
};
class deque {
public:
Node* head;
Node* tail;
public:
deque() { head = NULL; tail = NULL; }
void push(int x) {
Node* n = new Node();
n->set_value(x);
n->set_next(NULL);
n->set_prev(NULL);
Node* t = head; //link to the next node
if (t == NULL) {
head = n;
} else {
while (t->get_next() != NULL) {
t = t->get_next();
}
t->set_next(n);
}
}
};
正如我测试的那样,将一个节点连接到下一个节点的部分工作正常,但我在将节点连接到前一个节点时遇到了一些问题。想到的是第一个的变体:
Node* t = tail;
if (t == NULL) {
tail = n;
} else {
while (t->get_prev() != NULL) {
t = t->get_prev();
}
t->set_prev(n);
}
但是通过使用这个,尾节点总是当前的n节点,如果只有节点n是队列中的唯一节点......我该怎么办?非常感谢
最佳答案
绘图总是有助于处理此类数据结构。你目前拥有的:
您正确设置了 t
的 next
:t->set_next(n);
。缺少的是它下面的箭头,它是:n->set_prev(t)
。
一般来说,在处理双向链表时,对 set_next
的调用应该总是(大多数时候)伴随着对 上的
的参数。这是因为双向链表的属性:set_prev
的调用>set_next
x->next == y
implies y->prev == x
和 y->prev == x
暗示 x->next == y
。
关于c++ - 双向链表类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28136109/