単独リンクされたリストの検索

Question

私は、同じ引数を与えられたノードのために自分のノードを見ている検索機能を作ろうとしていますが、私はこれを行う方法について私の頭を包んでいるようには見えません。私のノード（要素）は、ポインタnext_、T color_、およびstring name_で構成されています。私は見つけたノードと前のノードとのペアを返す必要があります。見つからないか、前にない場合は、nullのポインタを返します。

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; 
} 

私は自分が何をしているのかわからないので、これは初めてのリストです。私はどんな種類の助けにも感謝し、必要に応じてもっと情報を提供することができます！ ありがとうございました！

Answer 1

あなたは一般的に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); 
} 

をしかし、あなたが本当に最初のノードを無視したくない場合は、（代わりにこれを試してみて、前のノードがnullの場合、呼び出し元に何をすべきかを決定させてください）。

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); 
}