head->next 不为空
head->next is not null
我不明白为什么我的一项列表“_head->next”没有被设置为 null (nullptr)。我会混淆我的尾巴和头部指针吗？这是一个双向链表。大多数其他指针都可以工作，但是这个 error/bug 在遍历列表时会抛出段错误。
#pragma once
class dlist {
public:
dlist() { }
struct node {
int value;
node* next;
node* prev;
};
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert(node* prev, int value){
//if empty
if(prev == nullptr)
{
//create node/prepare to insert into head ptr
_head = new node{value, _head, nullptr};
if(_tail == nullptr)
{
_tail = _head;
_tail->next = nullptr;
}
//set head
if(_head->next != nullptr)
{
_head->prev = _head;
_head->next = nullptr;
//_head->next->next = nullptr;
//above doesn't work
}
}
//if not empty
else
{
//create and set new node
node* node1 = new node{value, prev->next, nullptr};
prev->next = node1;
//check if null, to make sure inserting after a filled "space"
if(node1->next != nullptr)
{
node1->next->prev = node1;
//set to end or tail
if(prev == _tail)
{
_tail = node1;
_tail->next = nullptr;
}
}
}
}
private:
node* _head = nullptr;
node* _tail = nullptr;
};
考虑到您发布的初始代码以及您使用 prev 作为 insert.
的参数时的歧义，这有点难以理解
首先，insert 是 dlist 的成员函数，可以直接访问 _head 和 _tail。您不需要 insert 的 node* 参数，因为您对链表唯一关心的是检查 _head 是否为 nullptr 和 allocating/assigning value 对于 _head，或者你将迭代直到你的 iter->next 是 nullptr 并将分配的节点作为 iter->next 设置 _tail 添加到新分配的节点。
坦率地说，您现有的大部分代码都让我摸不着头脑。另外，class的默认值是private，所以一般只需要指定public个成员即可。
将逻辑放在一起，您可以执行以下操作：
class dlist {
struct node {
int value;
node* next;
node* prev;
};
node* _head = nullptr;
node* _tail = nullptr;
public:
dlist() { }
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert (int value)
{
node *newnode = new node {value, nullptr, nullptr};
if (_head == nullptr)
_head = newnode;
else {
node* iter = _head;
for (; iter->next; iter = iter->next) {}
newnode->prev = iter;
_tail = iter->next = newnode;
}
}
};
当你在class中分配内存时，为了防止像筛子一样泄漏内存，你还需要声明一个析构函数，它会在class的实例时释放你分配的内存=] 超出范围。不需要什么花哨的东西，只需从 _head 迭代到列表末尾和 delete 节点即可。
(注意： 在保存对下一个节点的引用之前，您不能 delete 对当前节点的引用，因此请使用一个单独的、适当命名的victim节点执行delete)
你可以这样做：
~dlist() {
node* iter = _head;
while (iter) {
node* victim = iter;
iter = iter->next;
delete victim;
}
}
将它放在一起并向 print 添加几个函数并反转或 rprint 列表，您可以执行以下操作：
#include <iostream>
using namespace std;
class dlist {
struct node {
int value;
node* next;
node* prev;
};
node* _head = nullptr;
node* _tail = nullptr;
public:
dlist() { }
~dlist() {
node* iter = _head;
while (iter) {
node* victim = iter;
iter = iter->next;
delete victim;
}
}
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert (int value)
{
node *newnode = new node {value, nullptr, nullptr};
if (_head == nullptr)
_head = newnode;
else {
node* iter = _head;
for (; iter->next; iter = iter->next) {}
newnode->prev = iter;
_tail = iter->next = newnode;
}
}
void print () {
for (node* iter = _head; iter; iter = iter->next)
cout << " " << iter->value;
cout << "\n";
}
void rprint() {
for (node* iter = _tail; iter; iter = iter->prev)
cout << " " << iter->value;
cout << "\n";
}
};
int main (void) {
dlist list;
int tmp;
while (cin >> tmp)
list.insert(tmp);
list.print();
list.rprint();
}
例子Use/Output
$ echo "2 3 4 6 8 10" | ./bin/dlist
2 3 4 6 8 10
10 8 6 4 3 2
内存Use/Error检查
在您编写的任何动态分配内存的代码中，您对分配的任何内存块负有 2 责任：(1) 始终保留指针或引用到内存块的起始地址，因此，(2) 它可以在不再需要时释放。
您必须使用内存错误检查程序来确保正确使用您分配的内存，并确认您释放了所有已分配的内存。
对于Linux valgrind是正常的选择。每个平台都有类似的内存检查器。它们都很简单易用，只需运行你的程序就可以了。
$ echo "2 3 4 6 8 10" | valgrind ./bin/dlist
==18878== Memcheck, a memory error detector
==18878== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==18878== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==18878== Command: ./bin/dlist
==18878==
2 3 4 6 8 10
10 8 6 4 3 2
==18878==
==18878== HEAP SUMMARY:
==18878== in use at exit: 0 bytes in 0 blocks
==18878== total heap usage: 9 allocs, 9 frees, 77,968 bytes allocated
==18878==
==18878== All heap blocks were freed -- no leaks are possible
==18878==
==18878== For counts of detected and suppressed errors, rerun with: -v
==18878== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
始终确认您已释放所有分配的内存并且没有内存错误。
我强烈建议不要再在 C++ 中使用 C-style 指针 。 C++ 具有 智能指针 可以为您完成所有内存管理。
将您的节点更改为：
class node {
node(int value) : value{value} {}
int value;
std::shared_ptr<node> next;
std::weak_ptr<node> prev;
};
一旦 copy/instance 不再存在，shared_ptr 将删除它持有的对象（它使用一个简单的计数器）。 weak_ptr 确保您没有循环引用，这意味着您的节点永远不会被删除。
同样在您的 dlist class 中相应地更改成员：
std::shared_ptr<node> _head;
std::weak_ptr<node> _tail;
然后将您的 getter 更改为：
std::shared_ptr<node> head() const { return _head; }
std::shared_ptr<node> tail() const { return _tail.lock(); }
weak_ptr::lock() 将增加它所属的 shared_ptr 计数器和 return 一个新的 shared_ptr，然后可以在没有丢失对象风险的情况下访问它。如果对象已经被删除，它将 return en empty shared_ptr.
然后像这样更改您的插入方法：
void insert (int value)
{
std::shared_ptr<node> newnode = std::make_shared<node>(value);
if (_tail) {
newnode->prev = _tail;
_tail->next = newnode;
_tail = newnode;
}
else {
_head = newnode;
_tail = newnode;
}
}
如果列表为空，这会将 _head 和 _tail 设置为 newnode，或者将其添加到您的列表末尾。
在此处阅读有关 shared_ptr and weak_ptr 的更多信息。
//编辑：如果您想清除列表，只需执行 _head = nullptr;。这将导致 shared_ptr 减少它的引用计数器并删除它持有的 node （如果计数器变为 0），从而删除该节点中的 shared_ptr<node> next; 等等。一旦 _tail 所属的 shared_ptr 被解构，_tail 将自动为 empty。为绝对确保您的 dlist class 处于干净的空状态，您仍应调用 _tail = nullptr;，因为代码的其他部分可以将 shared_ptr 保存到任何节点，从而使 _tail 在您的列表 class 中保持活动状态，除非您明确清除它。
我不明白为什么我的一项列表“_head->next”没有被设置为 null (nullptr)。我会混淆我的尾巴和头部指针吗？这是一个双向链表。大多数其他指针都可以工作，但是这个 error/bug 在遍历列表时会抛出段错误。
#pragma once
class dlist {
public:
dlist() { }
struct node {
int value;
node* next;
node* prev;
};
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert(node* prev, int value){
//if empty
if(prev == nullptr)
{
//create node/prepare to insert into head ptr
_head = new node{value, _head, nullptr};
if(_tail == nullptr)
{
_tail = _head;
_tail->next = nullptr;
}
//set head
if(_head->next != nullptr)
{
_head->prev = _head;
_head->next = nullptr;
//_head->next->next = nullptr;
//above doesn't work
}
}
//if not empty
else
{
//create and set new node
node* node1 = new node{value, prev->next, nullptr};
prev->next = node1;
//check if null, to make sure inserting after a filled "space"
if(node1->next != nullptr)
{
node1->next->prev = node1;
//set to end or tail
if(prev == _tail)
{
_tail = node1;
_tail->next = nullptr;
}
}
}
}
private:
node* _head = nullptr;
node* _tail = nullptr;
};
考虑到您发布的初始代码以及您使用 prev 作为 insert.
首先，insert 是 dlist 的成员函数，可以直接访问 _head 和 _tail。您不需要 insert 的 node* 参数，因为您对链表唯一关心的是检查 _head 是否为 nullptr 和 allocating/assigning value 对于 _head，或者你将迭代直到你的 iter->next 是 nullptr 并将分配的节点作为 iter->next 设置 _tail 添加到新分配的节点。
坦率地说，您现有的大部分代码都让我摸不着头脑。另外，class的默认值是private，所以一般只需要指定public个成员即可。
将逻辑放在一起，您可以执行以下操作：
class dlist {
struct node {
int value;
node* next;
node* prev;
};
node* _head = nullptr;
node* _tail = nullptr;
public:
dlist() { }
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert (int value)
{
node *newnode = new node {value, nullptr, nullptr};
if (_head == nullptr)
_head = newnode;
else {
node* iter = _head;
for (; iter->next; iter = iter->next) {}
newnode->prev = iter;
_tail = iter->next = newnode;
}
}
};
当你在class中分配内存时，为了防止像筛子一样泄漏内存，你还需要声明一个析构函数，它会在class的实例时释放你分配的内存=] 超出范围。不需要什么花哨的东西，只需从 _head 迭代到列表末尾和 delete 节点即可。
(注意： 在保存对下一个节点的引用之前，您不能 delete 对当前节点的引用，因此请使用一个单独的、适当命名的victim节点执行delete)
你可以这样做：
~dlist() {
node* iter = _head;
while (iter) {
node* victim = iter;
iter = iter->next;
delete victim;
}
}
将它放在一起并向 print 添加几个函数并反转或 rprint 列表，您可以执行以下操作：
#include <iostream>
using namespace std;
class dlist {
struct node {
int value;
node* next;
node* prev;
};
node* _head = nullptr;
node* _tail = nullptr;
public:
dlist() { }
~dlist() {
node* iter = _head;
while (iter) {
node* victim = iter;
iter = iter->next;
delete victim;
}
}
node* head() const { return _head; }
node* tail() const { return _tail; }
void insert (int value)
{
node *newnode = new node {value, nullptr, nullptr};
if (_head == nullptr)
_head = newnode;
else {
node* iter = _head;
for (; iter->next; iter = iter->next) {}
newnode->prev = iter;
_tail = iter->next = newnode;
}
}
void print () {
for (node* iter = _head; iter; iter = iter->next)
cout << " " << iter->value;
cout << "\n";
}
void rprint() {
for (node* iter = _tail; iter; iter = iter->prev)
cout << " " << iter->value;
cout << "\n";
}
};
int main (void) {
dlist list;
int tmp;
while (cin >> tmp)
list.insert(tmp);
list.print();
list.rprint();
}
例子Use/Output
$ echo "2 3 4 6 8 10" | ./bin/dlist
2 3 4 6 8 10
10 8 6 4 3 2
内存Use/Error检查
在您编写的任何动态分配内存的代码中，您对分配的任何内存块负有 2 责任：(1) 始终保留指针或引用到内存块的起始地址，因此，(2) 它可以在不再需要时释放。
您必须使用内存错误检查程序来确保正确使用您分配的内存，并确认您释放了所有已分配的内存。
对于Linux valgrind是正常的选择。每个平台都有类似的内存检查器。它们都很简单易用，只需运行你的程序就可以了。
$ echo "2 3 4 6 8 10" | valgrind ./bin/dlist
==18878== Memcheck, a memory error detector
==18878== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==18878== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==18878== Command: ./bin/dlist
==18878==
2 3 4 6 8 10
10 8 6 4 3 2
==18878==
==18878== HEAP SUMMARY:
==18878== in use at exit: 0 bytes in 0 blocks
==18878== total heap usage: 9 allocs, 9 frees, 77,968 bytes allocated
==18878==
==18878== All heap blocks were freed -- no leaks are possible
==18878==
==18878== For counts of detected and suppressed errors, rerun with: -v
==18878== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
始终确认您已释放所有分配的内存并且没有内存错误。
我强烈建议不要再在 C++ 中使用 C-style 指针 。 C++ 具有 智能指针 可以为您完成所有内存管理。
将您的节点更改为：
class node {
node(int value) : value{value} {}
int value;
std::shared_ptr<node> next;
std::weak_ptr<node> prev;
};
一旦 copy/instance 不再存在，shared_ptr 将删除它持有的对象（它使用一个简单的计数器）。 weak_ptr 确保您没有循环引用，这意味着您的节点永远不会被删除。
同样在您的 dlist class 中相应地更改成员：
std::shared_ptr<node> _head;
std::weak_ptr<node> _tail;
然后将您的 getter 更改为：
std::shared_ptr<node> head() const { return _head; }
std::shared_ptr<node> tail() const { return _tail.lock(); }
weak_ptr::lock() 将增加它所属的 shared_ptr 计数器和 return 一个新的 shared_ptr，然后可以在没有丢失对象风险的情况下访问它。如果对象已经被删除，它将 return en empty shared_ptr.
然后像这样更改您的插入方法：
void insert (int value)
{
std::shared_ptr<node> newnode = std::make_shared<node>(value);
if (_tail) {
newnode->prev = _tail;
_tail->next = newnode;
_tail = newnode;
}
else {
_head = newnode;
_tail = newnode;
}
}
如果列表为空，这会将 _head 和 _tail 设置为 newnode，或者将其添加到您的列表末尾。
在此处阅读有关 shared_ptr and weak_ptr 的更多信息。
//编辑：如果您想清除列表，只需执行 _head = nullptr;。这将导致 shared_ptr 减少它的引用计数器并删除它持有的 node （如果计数器变为 0），从而删除该节点中的 shared_ptr<node> next; 等等。一旦 _tail 所属的 shared_ptr 被解构，_tail 将自动为 empty。为绝对确保您的 dlist class 处于干净的空状态，您仍应调用 _tail = nullptr;，因为代码的其他部分可以将 shared_ptr 保存到任何节点，从而使 _tail 在您的列表 class 中保持活动状态，除非您明确清除它。