我想做一个双链表 . 函数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节点......我该怎么办?非常感谢
1 回答
绘图总是有助于这些数据结构 . 你目前有什么:
你正确设置了
t
的next
:t->set_next(n);
. 缺少的是它下面的箭头,它是:n->set_prev(t)
.通常,在处理双向链表时,由于双链表的属性,对
set_next
的调用应始终(大部分时间)伴随着对set_next
's argument. It'的set_prev
的调用:x->next == y
暗示y->prev == x
,y->prev == x
暗示x->next == y
.