1

我第一次使用链表，必须创建一个可以在双向链表末尾插入节点的函数。到目前为止我有

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    tail->next = newNode;
    tail = newNode;
    ++node_count;
}

Node 类接受要存储的值、要指向的下一个指针的值以及按该顺序指向的前一个指针的值。每当我尝试在此处插入节点时，都会收到一条错误消息，提示存在未处理的异常，并且在写入位置 0x00000008 时存在访问冲突。

我不完全确定这里出了什么问题，但我认为这与根据错误消息取消引用空指针有关。我真的很感激解决这个问题的一些帮助。

编辑：

我应该早点澄清，tail 是指向列表中最后一个节点的指针。Tail->next 访问最后一个节点的下一个变量，在函数运行之前，它指向 NULL，但在它执行之后应该指向创建的新节点。

4

3 回答 3

8

tail最初指向哪里？如果它为 NULL，那么您将在尝试插入第一个元素时取消引用空指针。

如果您tail在取消引用之前进行测试会有所帮助吗？

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    ++node_count;
}

Iftail为 null 并且offsetof(Node, next)为 8 可以解释访问冲突，因为tail->next地址为 0x00000000 + 8，即 0x00000008，因此分配给tail->next将尝试在该地址写入内存，这正是您看到的错误。

于 2012-10-09T00:21:47.620 回答
1

如果不知道插入操作之前列表的状态（顺便说一下，实际上是追加而不是插入），很难判断导致错误的原因。

您很有可能没有处理附加到空列表的初始情况。基本算法是（空列表由 NULL 头指针指示，其他一切都不确定）：

def append (entry):
    # Common stuff no matter the current list state.

    node = new Node()
    node->payload = entry
    node->next = NULL

    # Make first entry in empty list.

    if head = NULL:
        node->prev = NULL
        head = node
        tail = node
        return

    # Otherwise, we are appending to existing list.

    next->prev = tail
    tail->next = node
    tail = node
于 2012-10-09T00:20:07.253 回答
1

假设您的 LinkedList 既有头又有尾，不妨试试：

void LinkedList::insertAtTail(const value_type& entry) 
{
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    if (!head)
        head = newNode;
    ++node_count;
}

只是在黑暗中拍摄

于 2012-10-09T00:25:20.253 回答