單鏈接列表搜索

-2

我試圖做一個搜索功能，將通過我的節點看一個具有相同的參數給出，但我似乎無法包裝我的頭周圍如何做到這一點。我的節點（Element）由一個指針next_，T color_和string name_組成。我需要返回一個配對與我找到的節點和前一個節點。如果沒有找到或沒有之前，則爲空指針。單鏈接列表搜索

template<typename T> 
pair<Element<T>*, Element<T>*> PAL<T>::find(string name){ 
    pair<Element<T>*, Element<T>*> *result = nullptr; 
    Element<T>* x = nullptr; 
    Element<T>* y = nullptr; 
    for (Element<T> *n = back_; n != nullptr; n = n -> next_){ 
     if (n -> name_ == name){ 
      Element<T>* x = Element<T>(n -> name_, n -> color_); 
      result.first = x; 
      result.second = y; 
      break; 
     } 
     Element<T>* y = Element<T>(n -> name_, n -> color_); 
    } 
    return result; 
}

這是我第一次做這些列表，所以我不知道我在做什麼。我很感激任何幫助，如果需要，我可以提供更多信息！謝謝！

來源

2017-04-25 Alex

我有什麼意義嗎？：/ – Alex

老實說，我會開始通過包裝你的頭圍繞一個*多*更簡化的鏈接列表（沒有模板）的東西微不足道的嘗試之前。有跡象表明更重要的是（指針管理）在這裏發揮作用，並且你不需要模板管理來增加不適。 – WhozCraig

您正在使用'nullptr'的事實表明您正在使用C++ 11或更高版本，它具有單鏈接['std :: forward_list']（http://en.cppreference.com/w/cpp/容器/ forward_list）類在STL中。我建議你考慮使用它，而不是手動實現這種東西。但是，你真的需要一個**單**鏈表？因爲使用** double **鏈表（如['std :: list']（http://en.cppreference.com/w/cpp/container/list））會更容易。 –

您正在誤用std::pair以及一般指針。

此外，「如果沒有找到或沒有以前，返回null」，即第二個要求並沒有真正意義上的通用搜索功能！你真的想忽略列表中的第一個節點嗎？

如果是這樣，嘗試更多的東西是這樣的：

template <typename T> 
struct Element 
{ 
    Element* next_; 
    T color_; 
    std::string name_; 
}; 

template <typename T> 
class PAL 
{ 
public: 
    //... 
    std::pair<Element<T>*, Element<T>*> find(std::string name); 

private: 
    Element<T> *head_; // pointer to FIRST element 
}; 

template <typename T> 
std::pair<Element<T>*, Element<T>*> PAL<T>::find(std::string name) 
{ 
    Element<T> *previous = nullptr; 

    for (Element<T> *node = head_; node != nullptr; node = node->next_) 
    { 
     if (node->name_ == name) 
     { 
      if (previous != nullptr) 
       return std::make_pair(node, previous); 

      break; 
     } 

     previous = node; 
    } 

    return std::make_pair<Element<T>*>(nullptr, nullptr); 
}

或者：

template <typename T> 
std::pair<Element<T>*, Element<T>*> PAL<T>::find(std::string name) 
{ 
    if (head_ != nullptr) 
    { 
     Element<T> *previous = head_; 

     for (Element<T> *node = head_->next; node != nullptr; node = node->next_) 
     { 
      if (node->name_ == name) 
       return std::make_pair(node, previous); 

      previous = node; 
     } 
    } 

    return std::make_pair<Element<T>*>(nullptr, nullptr); 
}

但是，如果你真的不想忽略第一個節點，那麼試試這個來代替（讓主叫方決定如果前一個節點爲空，該怎麼辦）：

template <typename T> 
std::pair<Element<T>*, Element<T>*> PAL<T>::find(std::string name) 
{ 
    Element<T> *previous = nullptr; 

    for (Element<T> *node = head_; node != nullptr; node = node->next_) 
    { 
     if (node->name_ == name) 
      return std::make_pair(node, previous); 

     previous = node; 
    } 

    return std::make_pair<Element<T>*>(nullptr, nullptr); 
}

來源

2017-04-25 03:46:19

哦，男人，我只是讓我的生活變得複雜！非常感謝：D 老實說，這樣更容易理解。 – Alex

單鏈接列表搜索

回答

相關問題