c++ - C++中的双链表（指针内存访问冲突）

Question

我正在尝试在 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++pointers

Answer 1

如果您仍然卡住，那么让我们看看我们是否可以让您摆脱卡住。虽然 C++ 已经在std::list中提供了双向链表，但它应该是您自己编写的首选列表实现。也就是说，我们知道许多链表的自我实现都是出于教育目的的练习，无论是自学还是作为课堂的一部分。很好，你需要完全理解它们，有很多遗留代码可以利用所有类型的自创列表。

dlist_node如评论中所述，除其他问题外，您最大的问题是在将节点添加到列表时没有分配和初始化节点。您的列表有两个单独的struct，dlist它们包含headandtail指针（通过更封装的方法可以使其成为相同的成员，struct或者声明class您的prevandnext和有效负载（数据）指针的位置，并且在列表上操作的函数将是成员函数)

使用单独的结构很好，并且在结构中同时使用head和tail指针可确保您的列表添加可以在 O(1) 时间内按顺序完成。虽然您的代码已被编辑，但没有理由分配dlist double_linked_list. 你有一个结构，你可以简单地创建一个实例。指针head和tail将指向dlist_node您使用添加到列表中的每个节点分配和初始化的 a 。

关键是head它将始终指向列表中的第一个节点，并且tail始终指向最后一个节点。这为向前和反向迭代列表中的每个节点提供了起点。当您将节点添加（或附加）到列表中时，在为每个涉及的节点正确设置prev和指针之后，您只需相应地更新（如果插入新的第一个节点）或（如果添加到列表的末尾）指针.nextheadtail

当使用简单int的作为列表有效负载时，您可以在添加（附加）节点函数中轻松分配和初始化新节点。但是，随着您的有效负载变得越来越复杂，编写一个函数通常很方便，该createnode()函数将完全初始化节点所需的值作为参数，然后分配并完全初始化节点，成功时返回指向新节点的指针，或者nullptr在分配失败的情况下。这允许您重用您的add()功能，并且只createnode()为每个新列表自定义您的功能。

在查看您的添加和创建节点函数之前，让我们看看您的结构本身。虽然在 C 中，使用typedef为struct dlistor创建别名很方便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()(your 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;
    }

（该数组用于保存节点值，因此您可以对数组进行打乱，然后对打乱的数组进行迭代，以随机顺序删除节点）

您通常需要一个函数来允许您删除特定节点，然后在不再需要列表时删除所有节点，从而为给定或所有节点释放内存。您需要一个函数以正向和反向打印列表。如果您将我链接到的示例修改为使用newanddelete而不是mallocandfree并使用iostreaminstead of 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-empty\n";
        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-empty\n";
        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-empty\n";
        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

内存使用/错误检查

在您编写的任何动态分配内存的代码中，对于分配的任何内存块，您有两个责任：（1）始终保留指向内存块起始地址的指针，（2）它可以在没有时被释放更需要。

您必须使用内存错误检查程序，以确保您不会尝试访问内存或写入超出/超出分配块的边界，尝试读取或基于未初始化值的条件跳转，最后确认释放所有分配的内存。

对于 Linuxvalgrind是正常的选择。每个平台都有类似的内存检查器。它们都易于使用，只需通过它运行您的程序即可。

$ 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)

始终确认您已释放所有已分配的内存并且没有内存错误。

如果您还有其他问题，请仔细查看并告诉我。