在节点之前和之后插入

Question

我有以下两个函数，它们根本不会更改我的链表。我说明了如果给定节点为空，我然后检查给定节点是头还是尾，最后插入需要的位置并更正节点指向的位置。我一定错过了一小部分，但我不知道是什么。有任何想法吗？谢谢！

 // insert the new object after the node p 
void DoublyLinkedList::insertAfter(DListNode &p, int newobj) { 
    if(isEmpty()) { 
     throw EmptyDLinkedListException("Empty Doubly Linked List"); 
    } 


    DListNode *newNode = new DListNode(); 
    newNode->obj = newobj; 
    newNode->prev = &p; 
    newNode->next = p.next; 

    if (p.next != NULL) { 
     p.next->prev = newNode; 
    } 

    p.next = newNode; 


    if(&trailer == &p){ 
     trailer = *newNode; 
    } 
} 


// insert the new object before the node p 
void DoublyLinkedList::insertBefore(DListNode &p, int newobj){ 

    if(isEmpty()) { 
     throw EmptyDLinkedListException("Empty Doubly Linked List"); 
    } 


    DListNode *newNode = new DListNode(); 
    newNode->obj = newobj; 
    newNode->prev = p.prev; 
    newNode->next = &p; 

    if(&header == &p){ 
     header = *newNode; 

    } 

    if (p.prev != NULL) { 
     p.prev->next = newNode; 
    } 
} 

我有一个列表，最初是：

100 90 80 70 60 50 40 30 20 10 10 20 30 40 50 60 70 80 90 100 

我然后实现insertAfter功能的嵌入式15后80：

cout << "On list2 insert 15 after 80. " << endl; 
DListNode location = *dll2.getFirst()->next->next; 
dll2.insertAfter(location, 15); 
cout << "list2: " << dll2 << endl << endl; 

根据调试器，所有东西都指向正确的位置，但是上述函数ca的结果LL：

On list2 insert 15 after 80. 
list2: 100 90 80 70 60 50 40 30 20 10 10 20 30 40 50 60 70 80 90 100 

奇怪的是，当我实现insertAfter然后的insertBefore，如：

// add tests for insertAfter 
    cout << "On list2 insert 15 after 80. " << endl; 
    DListNode location = *dll2.getFirst()->next->next; 
    dll2.insertAfter(location, 15); 
    cout << "list2: " << dll2 << endl << endl; 

    //insertBefore 
    cout << "On list2 insert 9 before 80. " << endl; 
    dll2.insertBefore(location, 9); 
    cout << "list2: " << dll2 << endl << endl; 

的输出中是这样的：

On list2 insert 15 after 80. 
list2: 100 90 80 70 60 50 40 30 20 10 10 20 30 40 50 60 70 80 90 100 

On list2 insert 9 before 80. 
list2: 100 90 9 80 15 70 60 50 40 30 20 10 10 20 30 40 50 60 70 80 90 100 

这说明9之前插入并在后面插入了15，但是当函数结束时，析构函数中存在分段错误，表示正在删除的节点未分配。

Answer 1

链接列表是一个指针列表。您的列表中的header和trailer字段需要为DListNode*指针，而不是DListNode对象实例。如果他们不是指针，他们是无用的列出管理。

您的代码未正确更新围绕p节点的节点。即使您必须更新header或trailer字段，您仍然必须更新其他节点。但你没有这样做。

通过引用传递节点也是不习惯的，但无论如何你都是这样做的。我不想早些时候说这些，但你应该通过指针来传递它们。

你的代码应该看起来更像是这样的：

private: 
    DListNode *header, *trailer; 

... 

void DoublyLinkedList::insertAfter(DListNode *p, int newobj) 
{ 
    DListNode *newNode = new DListNode(); 
    newNode->obj = newobj; 
    newNode->prev = p; 
    newNode->next = p->next; 

    if (p->next != NULL) { 
     p->next->prev = newNode; 
    } 

    p->next = newNode; 

    if (trailer == p) { 
     trailer = newNode; 
    } 
} 

void DoublyLinkedList::insertBefore(DListNode *p, int newobj) 
{ 
    DListNode *newNode = new DListNode(); 
    newNode->obj = newobj; 
    newNode->prev = p->prev; 
    newNode->next = p; 

    if (p->prev != NULL) { 
     p->prev->next = newNode; 
    } 

    if (header == p) { 
     header = newNode; 
    } 
} 

话虽这么说，我劝你在前面的问题，一旦你了解双链表是如何工作的，你应该扔掉所有这些代码而只是使用STL std::list类，这是一个标准的双链表实现。