单链表搜索

Question

我正在尝试创建一个搜索功能，该功能将通过我的节点查找具有相同给定参数的节点，但我似乎无法理解如何执行此操作。我的节点（元素）由指针 next_、T color_ 和字符串 name_ 组成。我需要 return 与我找到的节点和前一个节点配对。如果未找到或没有以前的，则为 nullpointer。

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 和一般的指针。

此外，“如果未找到或没有以前的，return 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);
}

单链表搜索

Singly Linked Lists search

c++

nodes

singly-linked-list