鏈接列表：當列表中的值不在列表中時，remove（）和search（）方法無法正常工作

Question

所以我試圖在C++中創建一個Template Link List類。一切都很完美，包括remove（）和search（），除了當我調用兩個方法的值不在LinkList中時。理想情況下，我希望方法在發現該值不在列表中後返回，但是，我覺得這些方法仍然繼續，並嘗試刪除或進一步搜索值，因爲當我運行可執行文件時， 「Segementation Fault（核心轉儲）」錯誤。如果在空列表上調用方法，程序將輸出正確的錯誤。

該列表單獨與頭部鏈接，並且使用「智能節點」（即，包含它們自己的方法來補充匹配的類方法的節點而不是不包含方法並且需要類方法的「啞節點」創建指向節點的臨時指針並遍歷列表）。

這裏是search（）和remove（）的實現。當然，我可以提供，如果需要更多的代碼：

//==========================REMOVE================================ 

template <class T> 
void TLinkedList<T> :: remove(T value){ 
    if(!head){        //if there is no head 
    std::cerr << "Error: List is Empty" << std::endl; // The list is empty 
    return; 
    } 
    if(head->data == value){ 
    listSize--;  //decremenets listSize since a node is removed 
    node * temp = head; 
    head = head->next; 
    delete head; 
    return; 
    } 
    else{ 
    if(head->remove(value)){ //If something was removed as a result of the node's remove() 
     listSize--; 
     return;     //decrement listSize since something was removed 
    } 
    else{      //else if nothing removed 
     std::cerr << "Error : Value not in list" << std::endl; 
     return; 
    } 
    } 
} 

template <class T> 
bool TLinkedList<T> :: node :: remove(T value){ //returns a bool. If something was removed, returns true. If nothing was removed, returns false 
    if(next-> data == value){ 
    node * temp = next; 
    next = next->next; 
    delete temp; 
    return true; //something removed 
    } 
    if(!next){ 
    return false; 
    } 
    else{ 
    return next -> remove(value); 
    } 
} 


//==============SEARCH=================== 
template <class T> 
T TLinkedList<T> :: search(T value){ 
    if(!head){ 
    std::cerr << "Error: List is empty" << std::endl; 
    return 0; 
    } 
    if(head->data == value){ //If head's data is the value searched for 
    return head->data;  //return head's data 
    } 
    else{ 
    return head->search(value); 
    } 

} 

template <class T> 
T TLinkedList<T> :: node :: search(T value){ 
    if(data == value){ 
    return data; 
    } 
    if(!next){ 
    std::cerr << "Error: Value not in list" << std::endl; 
    return 0; 
    } 
    else{ 
    return next->search(value); 
    } 
} 

所以，對於一個main（），如：

int main(){ 

    TLinkedList ll; 
    ll.prepend(5); //adds 5 to list 
    ll.remove(4); // value of 4 not in list 
    // OR ll.search(4); 
    return 0; 
} 

的CERR不會發生和「分段錯誤（核心轉儲）'給出了錯誤。

任何幫助，非常感謝。謝謝！

編輯：另外，在search（）方法中，您可能會注意到我返回0;當發生錯誤時。該實現是在遇到錯誤時試圖停止該方法;理想情況下，我寧願搜索不返回任何東西，如果遇到錯誤

Answer 1

讓我們從你的方法刪除開始包含幾個錯誤。考慮在第一種方法void TLinkedList<T> :: remove(T value); 在此代碼段刪除列表

if(head->data == value){ 
    listSize--;  //decremenets listSize since a node is removed 
    node * temp = head; 
    head = head->next; 
    delete head; 
    return; 
    } 

的頭必須

if(head->data == value){ 
    listSize--;  //decremenets listSize since a node is removed 
    node * temp = head; 
    head = head->next; 
    delete temp; // <== 
    return; 
    } 

在功能bool TLinkedList<T> :: node :: remove(T value);你不檢查數據成員是否接下來就是等於0。所以這個代碼是未定義行爲

if(next-> data == value){ <== next can be equal to 0 

你應該改變這些條件

if(!next){ 
    return false; 
    } 
    if(next-> data == value){ 
    node * temp = next; 
    next = next->next; 
    delete temp; 
    return true; //something removed 
    } 

順序作爲來回方法搜索我會定義它們以下列方式

template <class T> 
TLinkedList<T>::node * TLinkedList<T>::search(const T &value) const 
{ 
    return (head == nullptr ? nullptr : head->search(value)); 
} 

template <class T> 
TLinkedList<T> :: node * TLinkedList<T>::node::search(const T &value) const 
{ 
    if (data == value) return this; 

    return (next == nullptr ? nullptr : next->search(value)); 
} 

Answer 2

按照我的意見上方，這就是你的搜索功能應該是這樣的：

//==============SEARCH=================== 
template <class T> 
T TLinkedList<T>::search(T value){ 
    if(!head){ 
     std::cerr << "Error: List is empty" << std::endl; 
     return 0; 
    } 
    else if(head->data == value){ //If head's data is the value searched for 
     return head->data;  //return head's data 
    } 

    typename TLinkedList<T>::node *temp = head->search(value); 
    if (temp) 
     return temp->data; 
    return 0; 
} 

節點::搜索

​​

TLinkedList ::除去（T）

//==========================REMOVE================================ 

template <class T> 
void TLinkedList<T> :: remove(T value){ 
    if(!head) {        //if there is no head 
     std::cerr << "Error: List is Empty" << std::endl; // The list is empty 
     return; 
    } 
    else if(head->data == value){ 
     listSize--;  //decremenets listSize since a node is removed 
     node *tmp = head; 
     head = head->next; 
     delete tmp; 
     return; 
    } 

    node *tmp = head->search(value); 

    if (tmp != nullptr) { 
     listSize--;  //decremenets listSize since a node is removed 
     node *tmp2 = tmp; 
     tmp = tmp->next; 
     delete tmp2; 
    } 
    else std::cerr << "Error : Value not in list" << std::endl; 
} 

Answer 3

該代碼是在幾個地方斷裂。這裏是我發現的那些：

1. 如果第一個節點將被刪除，刪除新的頭，而不是第一個節點。你可能意味着使用的

   delete temp; 
   

   代替

   delete head; 
   

2. 如果只有一個在不值相匹配列表中的節點，該...::node::remove()功能將訪問一個不存在的節點。您需要檢查next是否指向某些值得訪問的值。實際上，由於最終列表中只有一個元素的尾部，這就解釋了其中一個崩潰。你可能想要的東西像

   if (!next) { /* error goes here */ } 
   else if (next->value == value) { /* successful return goes here */ } 
   else { /* recursion goes here */ } 
   

3. 的...::node::search()功能有同樣的問題，解釋你的其他的崩潰。這個函數似乎有一個相當無意義的接口，但是：您搜索一個值，如果找到一個值，則返回搜索值。否則0返回，這意味着所有類型T您可以使用search()方法需要有一個構造函數接受0。這似乎是一個相當苛刻的限制。您可能想要將迭代器返回到找到的對象或迭代器到列表的末尾。

請注意，遞歸的管理列表方法在C++中肯定不會奏效。函數寫入的方式允許尾遞歸，但是我不認爲C++有任何尾部迴避實際實現的方法，即遍歷長列表時，你可以很容易地用完堆棧空間。

Answer 4

據我所見，錯誤可能來自您的preprend()方法。此外，正如其他人在其帖子中所說的，您的實施缺乏檢查和安全性。

爲什麼不使用已存在的STL或Boost鏈表，並且一般符合目的？