c++ - 在链表中查找节点的算法

Question

用来写的算法是什么Snode* find，set& operator=( set &rhs)我就是无法理解这两个。我可以阅读代码，但我无法弄清楚它们为什么在那里。我无法理解所用算法的步骤。我已经想通了： 1. Snode 是一个函数，它获取一个值并返回具有相同数据的节点。但是做什么prev和previous做什么，是什么**previous以及为什么我们应该创建指向指针的指针？2.set& operator=用于覆盖 = 运算符。但我不明白覆盖后它做了什么。为什么我们要交换和集合的heads 。这是代码：temprhs

#include <iostream>
using namespace std;

struct Snode //Snode class defines a node in a list
{
    char data;//a node includes a character
    int count;//an integer to count the occurrence
    Snode *next = NULL;//and a pointer to the next node
    Snode(char data, Snode* next) : data(data), next(next) {}
};

class set
{
private:
    Snode *head;//first node in the list
    Snode *tail;//last node of the list

public:

    set() : head(NULL), tail(NULL)
    {
    }

    set( set &src) : head(NULL), tail(NULL)//copy constructor method
    {
        Snode *temp = src.head;//set head of the second list as temp to travers

        while (temp)//untill the end of the list
        {
            // insert(temp->data);

            Snode *newNode = new Snode(temp->data,NULL);//create a new node with the same data and count
            newNode->count = temp->count;

            //now puts it in the right place
            if (!head)//if head = NULL (if sset is empty)
                head = newNode;//set the new node as the first node

            if (tail)//if tail != NULL (if set isn't empty)
                tail->next = newNode;//set new node as the next node of current tail, so it'll be the tail
            tail = newNode;

            temp = temp->next;//does the same thing for all the nodes of the second list
        }
    }

    ~set()//destructor method
    {
        Snode *temp = head;
        while (temp)//traverse the list and delete each node
        {
            Snode *next = temp->next;
            delete temp;
            temp = next;
        }
    }

    set& operator=( set &rhs)
    {
        if (&rhs != this)
        {
            set temp(rhs);
            Snode *ptr = head;
            head = temp.head;
            temp.head = ptr;
        }
        return *this;
    }

    bool isAvailable(char value)//checks if any node with the same data exists or not
    {
        return (find(value) != NULL);//if find function can't find any, there's no same node
    }

    Snode* find(char value, Snode **previous = NULL)
    {
        if (previous)
            *previous = NULL;

        Snode *temp = head;
        Snode *prev = NULL;

        while (temp)
        {
            if (temp->data == value)
            {
                if (previous)
                    *previous = prev;
                return temp;
            }

            temp = temp->next;
        }

        return NULL;
    }
    bool isFirst(char value)
    {
        return ((head) && (head->data == value));//if head's data is equal to value returns true
    }

    bool isLast(char value)
    {
        return ((tail) && (tail->data == value));//if tail's data is equal to value returns true
    }

    void display()
    {
        Snode *temp = head;
        while (temp)
        {
            cout << temp->data << " " << temp->count+1 << "\n";
            temp = temp->next;
        }
    }

    void insert(char value)//to insert a new value
    {
        Snode *temp = find(value);//if a node with the same data alreay exists
        if (temp)
            temp->count += 1;//increase the count by one
        else
        {
            temp = new Snode(value,NULL);//if if a node with the same data doesn't exist

            if (!head)//if list is empty
                head = temp;

            if (tail)//if list is not empty
                tail->next = temp;
            tail = temp;
        }
    }

    int count(char value)//count the nodes by the counter temp
    {
        Snode *temp = find(value);//travers the set
        return (temp) ? temp->count : 0;//if the list is empty return 0, else return the counter
    }

    void deleteFirst()//deletes the first node
    {
        if (head)//if list isn't empty
        {
            Snode *temp = head;
            head = head->next;//move the head forward
            if (tail == temp)//if loop faced the tail
                tail = NULL;
            delete temp;//delete the data
        }
    }

    void deleteLast()//delete the last node
    {
        if (head)
        {
            Snode *last = head;
            Snode *previous = NULL;

            while (last->next)//move forward untill the node before the last one
            {
                previous = last;
                last = last->next;
            }

            if (previous)//at the end of the list
                previous->next = NULL;
            tail = previous;

            if (head == last)//if there's only one node
                head = NULL;

            delete last;
        }
    }

    void remove(char value)//remove the node with the same data as the entry
    {
        Snode *previous;
        Snode *temp = find(value, &previous);

        if (temp)
        {
            if (temp->count > 1)
                temp->count -= 1;
            else
            {
                if (previous)
                    previous->next = temp->next;

                if (head == temp)
                    head = temp->next;

                if (tail == temp)
                    tail = previous;

                delete temp;
            }
        }
    }   };

标签： c++data-structureslinked-list

Answer 1

正如您已经猜到的那样，find尝试找到Snode包含所需字符的 a。如果仅需要，您可以忽略该previous参数（它将为 NULL），并且previous/prev处理将毫无用处。

但是find用于remove... 为了删除单链表中的一个节点，你必须让前一个指向下一个。因此，您必须浏览列表以跟踪前一个节点。这正是它的使用方式remove：

            if (previous)
                previous->next = temp->next;

赋值运算符使用复制和交换习语的紧密变体。但是由于析构函数只使用该head成员，因此只有该成员被交换：这足以让析构函数temp销毁原始列表的所有节点。

简单tail的应该设置进去，this即使设置进去也没用tmp。正确的实现可能是：

set& operator=( set &rhs)
{
    if (&rhs != this)
    {
        set temp(rhs);
        Snode *ptr = head;
        head = temp.head;
        temp.head = ptr;
        tail = temp.tail;   // no need for a full swap here
    }
    return *this;
}