在鏈表中查找值的遞歸方法

Question

template<class Type> 
int StringList<Type>::find(Type value) 
{ 
int count = 0; 

// Start of linked list 
Node<Type> *current = head; 

// Traverse list until end (NULL) 
while (current != NULL) 
{ 
    // Increase counter if found 
    if (current->data == value) 
    { 
     count++; 
    } 

    // If not, move to the next node 
    current = current->next; 
} 

cout << value << " was found " << count << " times" << endl; 

return 0; 





// same function but using Recursive method 





// Start of linked list 
Node<Type> *current = head; 
int count = 0; 

// Thinking this is the base case, since its similar to the while loop 
if (current == NULL) 
{ 
    return 0; 
} 

// same as the while loop, finding the value increase the count, or in this case just prints to console 
if ((current->data == value)) 
{ 
    cout << "Found match" << endl; 
    return 0; 
} 
else 
{ // If it didnt find a match, move the list forward and call the function again 
    current = current->next; 
    return find(value); 
} 

} 

函數應該找到搜索到的值並返回鏈接列表中某個值的次數。

如何將第一個使用while循環的方法轉換爲執行相同的事情但使用遞歸的東西？

Answer 1

爲了使用遞歸，你需要改變你的查找功能的簽名（或添加新的功能與不同的簽名）取一個節點指針作爲參數：

template<class Type> 
int StringList<Type>::find(Type value, Node<Type> *where) 
{ 
    if (where != nullptr) 
    { 
    // Do things 
    } 
} 

然後，當您遍歷列表時，您將where->next傳遞給函數。一旦您點擊列表的末尾，並顯示nullptr值，堆棧將展開。

遞歸的一個關鍵方面是所使用的函數或方法只需處理容器的單個節點。然後它自己調用下一個要處理的節點，直到沒有更多的節點。爲了實現這個功能，該功能需要節點作爲參數進行處理，這是當前代碼遇到問題的地方。

請記住，遞歸的優雅和簡單不是免費的。每個方法對自身的調用都會消耗堆棧，所以如果一個足夠大的容器會導致進程崩潰，那麼會導致進程崩潰。

Answer 2

對於初學者，而不是返回類型int最好是使用一個無符號類型例如像size_t

您可以用下面的辦法。定義兩種方法。第一個是一個公共非靜態方法find像

template<class Type> 
size_t StringList<Type>::find(const Type &value) const 
{ 
    return find(head, value); 
} 

第二一項所定義被定義具有兩個參數的私有靜態方法等

template<class Type> 
static size_t StringList<Type>::find(Node<Type> *current, const Type &value) 
{ 
    return current == nullptr ? 0 : (current->data == value) + find(current->next, value); 
} 

Answer 3

我如何可以把第一種方法，它使用一個while循環，進入 這是做同樣的事情，但使用遞歸？

以下內容將更接近你想要的。你真的應該提供一個[MCVE] ......缺乏這些力量會對你的代碼產生許多猜測和假設。

// It looks like StringList is a class (I ignored template issues), 
// and it appears that your class holds 'anchors' such as head 
// StringList is probably the public interface. 
// 
// To find and count a targetValue, the code starts 
// at the head node, and recurses through the node list. 
// I would make the following a public method. 
// 
int StringList::findAndCountTargetValue(int targetValue) 
    { 
     int retVal = 0; 

     if (nullptr != head)   // exists elements to search? 
     retVal = head->countTV(targetValue); // recurse the nodes 

     // else no match is possible 

     return(retVal); 
    } 


// visit each node in the list 
int Node::countTV(const int targetValue) 
    { 
     int retVal = 0; // init the count 

     if (data != targetValue) // no match 
     { 
     if(nullptr != next)   // more elements? 
      retVal += next->countTV() // continue recursive count 
     } 
     else 
     { 
     std::cout << "Found match" << std::endl; // for diag only 

     retVal += 1; // because 1 match has been found 

     if(nullptr != next)   // more elments 
      retVal += next->countTV(); // continue recursive count 
     } 

     return (retVal); // always return value from each level 
    }