在節點之前和之後插入

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類，這是一個標準的雙鏈表實現。