我正在用 C++ 实现双向链表。在插入之前,我的打印节点功能运行良好,但在我插入到前面之后,打印永远不会结束。
例如,我有节点 1, 2, 3 数据,我将数据插入到前面 5。然后我尝试打印,它只显示 5, 1, INFINITE LOOP 甚至没有去第三个节点 2 .
这是我的结构。
struct dl_node
{
int data;
struct dl_node* prev;
struct dl_node* next;
dl_node(dl_node* prev, dl_node* next, int data)
{
// here, prev is the parameter
// this->prev is from an object
this->prev = prev;
this->next = next;
this->data = data;
}
// constructor, without pointer parameter
explicit dl_node(int data)
{
this->prev = this;
this->next = this;
this->data = data;
}
};
这是我的插入函数。
// "push-front" operation
dl_node* insert_node(dl_node* head, int data)
{
if (nullptr == head)
return new dl_node(data);
auto insertion
= new dl_node(head->prev, head, data);
// previous node of this insertion is head's prev
// next node of this insertion is head
insertion->prev->next = insertion;
insertion->next->prev = insertion;
return insertion;
}
这是我的初始化。
struct dl_node* head = new dl_node(NULL);
struct dl_node* node_1 = new dl_node(NULL);
struct dl_node* node_2 = new dl_node(NULL);
head ->data = 1;
head ->next = node_1;
node_1->prev = head;
node_1->data = 2;
node_1->next = node_2;
node_2->prev = node_1;
node_2->data = 3;
node_2->next = nullptr;
这是我的插入。
// we insert to FRONT
head = insert_node(head, 5);
这是我的打印循环。
struct dl_node* current_node_2 = head;
while ( current_node_2 != nullptr )
{
cout << current_node_2->data << ", ";
current_node_2 = current_node_2->next;
}
// 5, 1, I get infinite loop from here....
有人知道吗?
最佳答案
问题是您的默认 dl_node
构造函数将 prev
和 next
都设置为 this
。
当您调用 insert_node(head, 5)
时,您会得到以下状态:
insertion->prev = head->prev; // assigned in constructor, but head->prev == head
insertion->next = head;
insertion->prev->next = insertion;
insertion->next->prev = insertion;
但是insertion->prev == head->prev
,我们知道head->prev == head
,所以
insertion->prev->next = insertion
减少到:
head->next = insertion;
所以你最终得到一个如下所示的列表:
insertion -> head -> insertion -> ...
您应该更改默认构造函数以将 next
和 prev
都设置为 NULL。同样在您的插入函数中,您应该在取消引用之前检查 insertion->prev
和 insertion->next
是否为非 NULL。
关于c++ - 双向链表插入无限循环... C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18411300/