我正在尝试在C++中实现双链表。我得到一个我不明白的错误。这是else行分支中的运行时错误：
list->tail->next = new_node;
它说list->tail在不同的内存地址。不幸的是，我有德语版的Visual Studio，所以我不能把它翻译得那么好。该错误被标记为"写访问冲突"。
有人可以解释一下这里发生了什么吗？
#include <iostream>
typedef struct dlist_node dlist_node;
struct dlist_node { // represents one node with its data and with pointers to the next and
dlist_node* next; // previous node
dlist_node* prev;
int data;
};
typedef struct { // represents nodes of the list that one can access
dlist_node* head;
dlist_node* tail;
} dlist;
void dlist_append(dlist* list, int data) { // to append the list with new data/node
dlist_node* new_node = new dlist_node;
new_node->data = data;
new_node->next = new_node->prev = NULL;
if (list->tail == NULL) { // if list is empty
list->head = list->tail = new_node;
}
else {
list->tail->next = new_node; // error appears here
new_node->prev = list->tail;
list->tail = new_node;
}
}
int main() {
dlist* double_linked_list = new dlist;
std::cout << double_linked_list->head;
dlist_append(double_linked_list, 42);
std::cout << double_linked_list->head;
}
如果您仍然卡住，那么让我们看看我们是否可以让您摆脱困境。虽然C++已经在 std：：list 中提供了双链表，但这应该是首选的列表实现，而不是编写自己的列表实现。也就是说，我们知道许多链接列表自我实现都是出于教育目的的练习，无论是自学还是作为课堂的一部分。这很好，你需要完全理解它们，有很多遗留代码利用所有类型的自我发明的列表。
如评论中所述，除其他问题外，您最大的问题是在将节点添加到列表时没有分配和初始化dlist_node节点。您的列表有两个单独的struct，dlist保存head和tail指针(使用更封装的方法可以成为同一struct或class的成员，其中声明了prev和next以及有效负载(数据)指针，并且在列表上运行的函数将是成员函数)
使用单独的结构是可以的，并且在结构中同时使用head和tail指针可以确保您的列表添加可以在 O(1) 时间内按顺序完成。虽然您的代码已被编辑，但没有理由为dlist double_linked_list分配。你有一个结构，你可以简单地创建一个实例。指针head和tail将指向一个dlist_node，您使用添加到列表中的每个节点分配和初始化该。
关键是head将始终指向列表中的第一个节点，而tail将始终指向最后一个节点。这为沿正向和反向迭代列表中的每个节点提供了起点。将节点添加(或追加)到列表时，在为每个涉及的节点正确设置prev和next指针后，只需相应地更新head(如果插入新的第一个节点)或tail(如果添加到列表末尾)指针。
使用简单int作为列表有效负载时，您可以在添加(追加)节点函数中轻松分配和初始化新节点。但是，随着有效负载变得越来越复杂，编写一个createnode()函数通常很方便，该函数将完全初始化节点所需的值作为参数，然后分配并完全初始化节点，在成功时返回指向新节点的指针，或者在分配失败时返回nullptr。这允许您重用add()函数，并且仅为每个新列表自定义createnode()。
在查看添加和创建节点函数之前，让我们先看一下结构本身。而在 C 中，使用typedef为struct dlist或struct dlist_node创建别名很方便，C++这是完全不必要的，并且通常会导致比它解决的问题更多的问题。当您在C++中声明结构时，您只需创建该结构的实例，并可以直接将结构名称作为类型引用，例如
struct dlist_node { /* list node */
int data;
struct dlist_node *prev, *next;
};
struct dlist { /* list wrapper with head & tail pointers */
dlist_node *head, *tail;
};
现在，对于add()(您的append)和createnode()函数，您可以执行以下操作：
/** create new node initialize all members */
dlist_node *createnode (int v)
{
dlist_node *node = new dlist_node; /* allocate node */
if (!node) /* validate allocation (and use try/catch) */
return nullptr;
node->data = v; /* initialize members values */
node->prev = node->next = nullptr;
return node; /* return new node */
}
/** add node at end of list, update tail to end */
dlist_node *add (dlist *l, int v)
{
dlist_node *node = createnode (v); /* allocate node, initialize data */
if (!node) /* validate allocation */
return nullptr;
if (!l->head) /* if 1st node, node is head/tail */
l->head = l->tail = node;
else { /* otherwise */
node->prev = l->tail; /* set prev to tail */
l->tail->next = node; /* add at end, update tail pointer */
l->tail = node;
}
return node; /* return new node */
}
始终验证分配是否成功，并在错误失败时处理错误。
现在要在main()(或需要列表的任何其他范围)中创建一个列表，您只需声明结构的一个实例并将head和tail初始化为nullptr(可以移动到构造函数以便它自动发生)，您可以执行以下操作：
dlist list = { nullptr, nullptr }; /* initialize list pointers nullptr */
创建名为list的列表。要测试列表，请在列表中添加几个节点，向前和向后检查列表，然后以随机顺序删除所有节点，在删除每个节点后检查所有指针，例如
#define NNODES 16
...
dlist list = { nullptr, nullptr }; /* initialize list pointers nullptr */
int a[NNODES]; /* array to shuffle */
for (int i = 0; i < NNODES; i++) { /* fill array with NNODES int */
add (&list, i+1);
a[i] = i+1;
}
(数组用于保存节点值，因此您可以洗牌数组，然后迭代洗牌数组，以随机顺序删除节点)
您通常需要一个函数来允许您删除特定节点，然后在不再需要列表时删除所有节点，从而释放给定或所有节点的内存。您需要一个函数来正向和反向打印列表。如果您修改我链接到的示例以使用new和delete而不是malloc和free并使用iostream而不是stdio.h，您将拥有：
#include <iostream>
#include <random>
#ifndef NNODES
#define NNODES 16
#endif
/*
* non-list misc functions
*/
/** shuffle integer array of size 'n'
* (using fisher-yates method)
*/
void shuffle (int *a, int n)
{
std::random_device rd; /* random seed */
std::mt19937 gen(rd()); /* standard mersenne_twister_engine */
std::uniform_int_distribution<> dist(0, NNODES - 1); /* distribution 0, 15 */
int i, tmp;
while (n-- > 1) {
i = dist(gen);
tmp = a[i];
a[i] = a[n];
a[n] = tmp;
}
}
/*
* list structs and functions
*/
struct dlist_node { /* list node */
int data;
struct dlist_node *prev, *next;
};
struct dlist { /* list wrapper with head & tail pointers */
dlist_node *head, *tail;
};
/** create new node initialize all members */
dlist_node *createnode (int v)
{
dlist_node *node = new dlist_node; /* allocate node */
if (!node) /* validate allocation (and use try/catch) */
return nullptr;
node->data = v; /* initialize members values */
node->prev = node->next = nullptr;
return node; /* return new node */
}
/** add node at end of list, update tail to end */
dlist_node *add (dlist *l, int v)
{
dlist_node *node = createnode (v); /* allocate node, initialize data */
if (!node) /* validate allocation */
return nullptr;
if (!l->head) /* if 1st node, node is head/tail */
l->head = l->tail = node;
else { /* otherwise */
node->prev = l->tail; /* set prev to tail */
l->tail->next = node; /* add at end, update tail pointer */
l->tail = node;
}
return node; /* return new node */
}
/** print all nodes in list */
bool prn (dlist *l)
{
if (!l->head) {
std::cout << "list-emptyn";
return false;
}
for (dlist_node *n = l->head; n; n = n->next)
std::cout << ' ' << n->data;
std::cout.put('n');
return true;
}
/** print all nodes in list in reverse */
bool prnrev (dlist *l)
{
if (!l->tail) {
std::cout << "list-emptyn";
return true;
}
for (dlist_node *n = l->tail; n; n = n->prev)
std::cout << ' ' << n->data;
std::cout.put('n');
return false;
}
/** delete node with value v from list (for loop) */
bool del_node (dlist *l, int v)
{
if (!l->head) {
std::cout << "list-emptyn";
return false;
}
dlist_node **ppn = &l->head; /* pointer to pointer */
dlist_node *pn = l->head; /* pointer to node */
for (; pn; ppn = &pn->next, pn = pn->next) {
if (pn->data == v) {
*ppn = pn->next; /* set node at address to next */
if (pn != l->tail) /* prev is next prev */
(*ppn)->prev = pn->prev;
else /* deleting tail, set tail to prev */
l->tail = pn->prev;
delete pn; /* free current */
pn = nullptr;
break;
}
}
return true;
}
/** delete all nodes in list */
void del_nodes (dlist *l)
{
dlist_node *n = l->head;
while (n) {
dlist_node *victim = n;
n = n->next;
delete victim;
}
l->head = l->tail = nullptr;
}
int main (void) {
dlist list = { nullptr, nullptr }; /* initialize list pointers nullptr */
int a[NNODES]; /* array to shuffle */
for (int i = 0; i < NNODES; i++) { /* fill array with NNODES int */
add (&list, i+1);
a[i] = i+1;
}
shuffle (a, NNODES); /* shuffle array for random removal */
prn (&list); /* print list forward */
prnrev (&list); /* print list reverse */
std::cout.put('n');
for (int i = 0; i < NNODES; i++) { /* remove all nodes in random order */
std::cout << "deleting : " << a[i] << 'n';
del_node (&list, a[i]); /* delete node with random value a[i] */
if (prn (&list)) { /* print list forward if nodes remain */
prnrev (&list); /* print list reverse if nodes remain */
std::cout.put('n'); /* tidy up with a 'n' */
}
}
}
示例使用/输出
$ ./bin/dlist_dlist_node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
deleting : 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
deleting : 9
2 3 4 5 6 7 8 10 11 12 13 14 15 16
16 15 14 13 12 11 10 8 7 6 5 4 3 2
deleting : 12
2 3 4 5 6 7 8 10 11 13 14 15 16
16 15 14 13 11 10 8 7 6 5 4 3 2
deleting : 7
2 3 4 5 6 8 10 11 13 14 15 16
16 15 14 13 11 10 8 6 5 4 3 2
deleting : 16
2 3 4 5 6 8 10 11 13 14 15
15 14 13 11 10 8 6 5 4 3 2
deleting : 5
2 3 4 6 8 10 11 13 14 15
15 14 13 11 10 8 6 4 3 2
deleting : 8
2 3 4 6 10 11 13 14 15
15 14 13 11 10 6 4 3 2
deleting : 14
2 3 4 6 10 11 13 15
15 13 11 10 6 4 3 2
deleting : 4
2 3 6 10 11 13 15
15 13 11 10 6 3 2
deleting : 3
2 6 10 11 13 15
15 13 11 10 6 2
deleting : 13
2 6 10 11 15
15 11 10 6 2
deleting : 2
6 10 11 15
15 11 10 6
deleting : 6
10 11 15
15 11 10
deleting : 10
11 15
15 11
deleting : 11
15
15
deleting : 15
list-empty
内存使用/错误检查
在您编写的任何动态分配内存的代码中，对于分配的任何内存块，您有 2个责任：(1)始终保留指向内存块起始地址的指针，以便 (2) 当不再需要内存块时可以释放它。
必须使用内存错误检查程序来确保不会尝试访问内存或超出/超出分配块边界的写入，不会尝试读取或基于未初始化值的条件跳转，最后确认释放了已分配的所有内存。
对于Linux来说，valgrind是正常的选择。每个平台都有类似的内存检查器。它们都易于使用，只需通过它运行您的程序即可。
$ valgrind ./bin/dlist_dlist_node
==17580== Memcheck, a memory error detector
==17580== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17580== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==17580== Command: ./bin/dlist_dlist_node
==17580==
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
deleting : 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16
16 14 13 12 11 10 9 8 7 6 5 4 3 2 1
...
deleting : 16
12
12
deleting : 12
list-empty
==17580==
==17580== HEAP SUMMARY:
==17580== in use at exit: 0 bytes in 0 blocks
==17580== total heap usage: 19 allocs, 19 frees, 74,664 bytes allocated
==17580==
==17580== All heap blocks were freed -- no leaks are possible
==17580==
==17580== For counts of detected and suppressed errors, rerun with: -v
==17580== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
始终确认已释放已分配的所有内存，并且没有内存错误。
仔细查看，如果您有其他问题，请告诉我。