алгоритм поиска узла в связанном списке

Question

Какой алгоритм используется для записи Snode* find и set& operator=( set &rhs) Я просто не могу понять эти два.Я могу прочитать код, но не могу понять, почему они там.Я не могу понять шаги используемого алгоритма.Вещи, которые я уже понял: 1. Snode - это функция, которая получает значение и возвращает узел с теми же данными. Но что делают prev и previous и что такое **previous и почему мы должны создать указатель науказатель?2. set& operator= для переопределения оператора =.но я не могу понять, что он делает после переопределения. и почему мы должны поменять head с temp и rhs наборов.вот код:

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

Answer 1

Как вы уже догадались, find пытается найти Snode, содержащий требуемый символ.Если требуется только это, вы можете игнорировать параметр 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;
}