C++獲得單節點鏈表中匹配節點的前一個節點

開始：這是作業問題的一部分，所以請隨時提示答案或指向正確的方向而不是直接回答。C++獲得單節點鏈表中匹配節點的前一個節點

我建立在C++中的所要求的功能之一的單個鏈接表是void remove(const T& key)其中如果值匹配傳遞到功能的鍵的給定節點被去除。

我目前的想法是，我必須首先找到要刪除的節點，找到要刪除的節點之前的節點，然後找到要刪除的節點之後的節點。從那裏我可以刪除需要刪除的節點，並將前一個節點設置爲指向刪除的節點之後的節點。

以下是相關功能：

LinkedList.h

//Returns the node with passed in value key 
ListNode<T>* find(const T& key) { 
    ListNode<T>* currentNode = _head; 
    while(currentNode != NULL && currentNode->data() != key){ 
     currentNode = currentNode->next(); 
    } 
    return currentNode; 
} 

//Returns the node before the key 
ListNode<T>* findPreviousNode(const T& key){ 
    ListNode<T>* previousNode; 
    ListNode<T>* currentNode = _head; 

    while(currentNode != NULL && currentNode->data() != key){ 
     previousNode = currentNode; 
     currentNode = currentNode->next(); 
    } 
    return previousNode; 
} 

// Removes and deletes the first node in the linked list that has data 
// equal to the key 
void remove(const T& key) { 
    ListNode<T>* nodeToDelete = find(key); 
    ListNode<T>* previousNode = findPreviousNode(key); 
    ListNode<T>* nextNode = nodeToDelete->next(); 
    delete nodeToDelete; 
    previousNode->setNext(nextNode); 

}

我已經廣泛使用我find(const T& key)功能和它的作品，所以我認爲這個問題是在我findPreviousNode功能，但是當我通過代碼走它似乎工作正常。

在我看來，previousNode總是會有最後一個選中的元素，當找到匹配時它會返回尚未更新的previousNode，因此它仍然包含直接位於匹配節點之前的節點，但是這顯然不是， t正確，我不知道爲什麼。當我運行的代碼，我收到了

分段錯誤（核心轉儲）

錯誤信息

這裏有一些pastebins與整個代碼：

LinkedList.h http://pastebin.com/b4miZBzA

main.cpp（調用測試函數的方法）http://pastebin.com/0QGtUhjC

來源

2017-02-24 kalenpw

可能會有幫助：http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list – user4581301

你很明顯缺少很多邊緣案例。您的find()函數未處理找不到密鑰的情況。在那種情況下，它返回null，爲此findPreviousNode()返回previousNode的垃圾值。

假設find()返回指向頭部的指針。然後你的findPreviousNode()再次返回未初始化的以前的節點指針。

嘗試處理代碼中的邊緣情況。

你的remove()功能應該工作正常，假設這些處理。因爲你正在運行兩個不必要的循環，所以你可以通過從findPreviousNode()返回適當的值來真正改善運行時間，因此你可以在運行時保存。

來源

2017-02-24 05:15:23 Phoenix

如果找不到值，則find（）的指令將返回NULL，但現在我確實知道findPreviousNode（）如何嘗試獲取一個空值。我會盡力解決這個問題，看看是否能解決任何問題。 – kalenpw

閱讀我答案中的最後一行，並嘗試將其用於Code Enefficiency問題。 – Phoenix

爲什麼我不需要運行find（）函數？這是必需的，所以我可以刪除相應的節點 – kalenpw

從您在問題中發佈的代碼中，您看起來像是有正確的想法。

兩個小技巧：

防禦性編程。檢查nodeToDelete和previousNode是否不爲NULL。目前，如果未找到密鑰，則最終會取消引用NULL指針，這可能是導致分段錯誤的原因。
效率。爲什麼遍歷列表兩次（一次在'find'中，一次在'findPrevious'中），當你可以遍歷一次並獲得兩個值時？即結合find（）和findPrevious（）函數來減少程序必須執行的工作量。

來源

2017-02-24 05:14:00 nibot

for 1我相信這是我工作的問題上。對於編碼2，我肯定覺得效率低下，但因爲有時我需要節點和其他時間的前一個節點，我把它分成兩個函數，因爲我不能改變方法參數來包含一個布爾值或東西來表明我是否想要返回前一個或當前的 – kalenpw

C++獲得單節點鏈表中匹配節點的前一個節點

回答

相關問題