скопировать список и вернуть указатель, указывающий на второй список - PullRequest
Новая
       70

скопировать список и вернуть указатель, указывающий на второй список

0 голосов
/ 25 мая 2018

Я настроил свое простое приложение, которое позволяет вам работать со связанными списками.каждый узел имеет значение типа char в качестве данных и число int, которое подсчитывает вхождение каждой информацииМне нужна функция, чтобы скопировать существующий список и вставить его куда-нибудь еще, и, наконец, вернуть адрес первого узла вставленного списка.Как мне это сделать?вот весь мой код: 

#include <iostream>
using namespace std;

struct Snode //Snode class defines a node in a list
{
    char data;
    int count = 1;
    Snode *next = NULL;
    Snode(char a) : data(a) {}
};

class set//set class defines the list
{
private:
    Snode *head;
public:
    set() : head(NULL)//constructor method of the list
    {
        Snode *temp = head;
        while (temp != NULL)
        {
            Snode *next = temp->next;
            delete temp;
            temp = next;
        }
        head = NULL;
    }
    ~set()//destructor method of the list
    {
        Snode *temp = head;
        while (temp != NULL)
        {
            head = head->next;
            delete temp;
        }
    }
    bool isAvailable(char value)//checks if the node is already in the list or not
    {
        Snode *temp = head;
        while (temp != NULL)//untill the end of the list
        {
            if (temp->data == value)//if a similar node is found
                return true;
            else//if temp is not equal check the next node
                temp = temp->next;
        }
        return false;//if no node is found return false
    }

    bool isFirst(char value)//checks if the node is the first node or not
    {
        return(head->data == value);//if it equals to head, it's the first node
    }

    bool isLast(char value)//checks if the node is the last node or not
    {
        Snode *last ;
        return(last->next = NULL);//if its next pointer points the null pointer, it's the last node in the list
    }


    void display()//showing all the nodes
    {
        //creating a variable node to travers available nodes
        Snode *temp = head;
        while (temp != NULL)//travers nodes untill the end of the list
        {
            cout << temp->data << " " << temp->count << "\n"; //output format
            temp = temp->next;//setting the next node as the variable
        }
    }

    void insert(char value)//inserts a new node
    {
        if (head == NULL)//if the list is empty
        {
            //create a new node, set its count to 1 and set it as head of the list
            Snode *temp = new Snode(value);
            temp->count = 1;
            head = temp;
        }
        else//is the list is'nt empty
        { 
            if (isAvailable(value))//if the value is already available
                {
                    //find the existing node and increase its count by 1
                    Snode *temp = head;
                    while (temp->data != value)//check the list to the end
                        temp = temp->next;
                    temp->count += 1;
                }
            else//if there's not an existing node with the given value
            {
                //create a new node with a count of 1 at the end of the list by setting *next equal to NULL
                Snode *temp = new Snode(value);
                temp->count = 1;
                temp->next = NULL;
            }
        }
    }

    int count(char value)//counts the occurrence of a character value by reading the same node's count
    {
        Snode *temp = head;
            while (temp != NULL)//travers nodes untill the end of the list
            {
                if(temp->data==value)
                {
                    cout<<temp->count;
                }
                else
                {
                    cout<<"This character is not in the list";
                }
            }
        return temp->count;
    }

    void deleteFirst(char value)//delete the first node in the list
{
    Snode *temp = head;//create a new node including head's data
    head = head->next;//setting the second node as head
    delete temp;//deleting the first node
}
void deleteLast(char value)//deleting the last node in the list
{
    Snode *current= new head;//creating two new nodes and starting the travers from the first node
    Snode *previous=new Snode();
    while(current->next!=NULL)//continue traversing untill the end of the list
    {
      previous=current;//moving current and previous nodes to the right in order to check the next nodes
      current=current->next;
      if(current->next == NULL)//if the list is finished
      {
          previous->next = NULL;//pointing the previous node's next as NULL, instead of the last node
          delete current;//deleting the last node
      }
    }
}

char remove(char value, struct Snode *temp)//removing a node from the list
{
    if(!isAvailable(value))//if there's no node with the given data
    {

        cout<<"Not available";
        return NULL;
    }

    else//if there is already a node with the same data
    {
        if(temp->count == 1)//if there's a node with one time occurrence
        {
            if(isFirst(value)//if it's equal to the first node
            {
                deleteFirst(value);
            }
            else if(isLast(value))//if it's equal to the last node
            {
                deleteLast(value);
            }
            else//if it's in the middle, neither first nor last
            {
                Snode *current = head;//traversing all nodes
                Snode *previous=new Snode();
                while(current->next=NULL)
                {
                    if(current->data==value)
                    {
                        previous->next = current->next;
                        delete current;
                    }
                    previous=current;
                    current=current->next;           
                }
            }
        }
        else if(temp->count > 1)
        {
            temp->count--;//decrease the count
        }
    }   
}
};

int main()
{
    //defining a mySet as a "set" type
    set mySet;

    //adding values to create nodes
    mySet.insert('c');
    mySet.insert('a');
    mySet.insert('a');
    mySet.insert('c');
    mySet.insert('c');

    //displaying nodes through "value count" format
    mySet.display();

    return 0;
}

1 Ответ

0 голосов
/ 25 мая 2018

Вам необходимо перечислить узлы старого списка, выделить новые узлы для скопированных данных и добавить их в новый список.Лучшее место для этого - конструктор копирования и оператор присваивания класса set.

Кроме того, конструктор класса set по умолчанию выполняет ту работу, которую должен выполнять ваш деструктор.Что не является необходимым, так как в конструкторе нечего удалять.Ваш деструктор не выполняет итерацию по списку правильно.Код, который вы используете в конструкторе по умолчанию, выполняется правильно.Этот код необходимо переместить из конструктора в деструктор.

Ваши другие методы класса set реализованы не очень эффективно (избыточный поиск в списке) или даже в некоторых случаях правильно (совершенно неверная логика,утечки памяти и т. д.).

Вместо этого попробуйте что-нибудь подобное: 

struct Snode
{
    char data;
    int count;
    Snode *next = nullptr;
    Snode(char a, int c = 1) : data(a), count(c) {}
};

class set
{
private:
    Snode *head = nullptr;
    Snode *tail = nullptr;

    void append(char value, int count)
    {
        Snode *temp = new Snode(value, count);

        if (!head)
            head = temp;

        if (tail)
            tail->next = temp;
        tail = temp;
    }    

    void remove(Snode *node, Snode *previous)
    {
        if (previous)
            previous->next = node->next;

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

        if (tail == node)
            tail = previous;

        delete node;
    }

    void swap(set &other)
    {
        Snode *ptr = head;
        head = other.head;
        other.head = ptr;

        ptr = tail;
        tail = other.tail;
        other.tail = ptr;
    }

public:
    set() = default;

    set(const set &src)
    {
        Snode *temp = src.head;    
        while (temp)
        {
            append(temp->data, temp->count);
            temp = temp->next;
        }
    }

    set(set &&src)
    {
        src.swap(*this);
    }

    ~set()
    {
        Snode *temp = head;
        while (temp)
        {
            Snode *next = temp->next;
            delete temp;
            temp = next;
        }
    }

    set& operator=(const set &rhs)
    {
        if (&rhs != this)
        {
            set temp(rhs);
            temp.swap(*this);
        }
        return *this;
    }

    set& operator=(set &&rhs)
    {
        rhs.swap(*this);
        return *this;
    }

    bool isAvailable(char value)
    {
        return (find(value) != nullptr);
    }

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

        Snode *temp = head;
        Snode *prev = nullptr;

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

            prev = temp;
            temp = temp->next;
        }

        return nullptr;
    }

    bool isFirst(char value)
    {
        return ((head) && (head->data == value));
    }

    bool isLast(char value)
    {
        return ((tail) && (tail->data == value));
    }

    void display()
    {
        Snode *temp = head;
        while (temp)
        {
            std::cout << temp->data << " " << temp->count << std::endl;
            temp = temp->next;
        }
    }

    void insert(char value)
    {
        Snode *temp = find(value);
        if (temp)
            temp->count += 1;
        else
            append(value, 1);
    }

    int count(char value)
    {
        Snode *temp = find(value);
        return (temp) ? temp->count : 0;
    }

    void deleteFirst()
    {
        if (head)
            remove(head, nullptr);
    }

    void deleteLast()
    {
        if (head)
        {
            Snode *last = head;
            Snode *previous = nullptr;

            while (last->next)
            {
                previous = last;
                last = last->next;
            }

            remove(last, previous);
        }
    }

    void remove(char value)
    {
        Snode *previous;
        Snode *temp = find(value, &previous);    
        if (temp)
        {
            if (temp->count > 1)
                temp->count -= 1;
            else
                remove(temp, previous);
        }
    }   
};

Тогда вы можете сделать что-то вроде этого: 

int main()
{
    //defining a mySet as a "set" type
    set mySet;

    //adding values to create nodes
    mySet.insert('c');
    mySet.insert('a');
    mySet.insert('a');
    mySet.insert('c');
    mySet.insert('c');

    set myCopiedSet = mySet; // make a copy of the list

    //adding more values to create nodes
    myCopiedSet.insert('a');
    myCopiedSet.insert('b');
    myCopiedSet.insert('b');
    myCopiedSet.insert('c');

    //displaying nodes through "value count" format
    std::cout << "original:" << std::endl;
    mySet.display();    
    std::cout << "copy:" << std::endl;
    myCopiedSet.display();

    return 0;
}

Вы можете упростить set Класс немного дальше, если вы используете двусвязный список вместо односвязного списка: 

struct Snode
{
    char data;
    int count;
    Snode *previous = nullptr;
    Snode *next = nullptr;
    Snode(char a, int c) : data(a), count(c) {}
};

class set
{
private:
    Snode *head = nullptr;
    Snode *tail = nullptr;

    void append(char value, int count)
    {
        Snode *temp = new Snode(value, count);

        if (!head)
            head = temp;

        if (tail)
        {
            temp->previous = tail;
            tail->next = temp;
        }
        tail = temp;
    }

    void remove(Snode *node)
    {
        if (node->previous)
            node->previous->next = node->next;

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

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

        if (tail == node)
            tail = node->previous;

        delete node;
    }

    void swap(set &other)
    {
        Snode *ptr = head;
        head = other.head;
        other.head = ptr;

        ptr = tail;
        tail = other.tail;
        other.tail = ptr;
    }

public:
    set() = default;

    set(const set &src)
    {
        Snode *temp = src.head;
        while (temp)
        {
            append(temp->data, temp->count);
            temp = temp->next;
        }
    }

    set(set &&src)
    {
        src.swap(*this);
    }

    ~set()
    {
        Snode *temp = head;
        while (temp)
        {
            Snode *next = temp->next;
            delete temp;
            temp = next;
        }
    }

    set& operator=(const set &rhs)
    {
        if (&rhs != this)
        {
            set temp(rhs);
            temp.swap(*this);
        }
        return *this;
    }

    set& operator=(set &&rhs)
    {
        rhs.swap(*this);
        return *this;
    }

    bool isAvailable(char value)
    {
        return (find(value) != nullptr);
    }

    Snode* find(char value)
    {
        Snode *temp = head;    
        while (temp)
        {
            if (temp->data == value)
                return temp;    
            temp = temp->next;
        }    
        return nullptr;
    }

    bool isFirst(char value)
    {
        return ((head) && (head->data == value));
    }

    bool isLast(char value)
    {
        return ((tail) && (tail->data == value));
    }

    void display()
    {
        Snode *temp = head;
        while (temp)
        {
            std::cout << temp->data << " " << temp->count << std::endl;
            temp = temp->next;
        }
    }

    void insert(char value)
    {
        Snode *temp = find(value);
        if (temp)
            temp->count += 1;
        else
            append(value, 1);
    }

    int count(char value)
    {
        Snode *temp = find(value);
        return (temp) ? temp->count : 0;
    }

    void deleteFirst()
    {
        if (head)
            remove(head);
    }

    void deleteLast()
    {
        if (tail)
            remove(tail);
    }

    void remove(char value)
    {
        Snode *temp = find(value);
        if (temp)
        {
            if (temp->count > 1)
                temp->count -= 1;
            else
                remove(temp);
        }
    }   
};

В этом случае вы можете значительно упростить класс set, используя STL's std::listвместо контейнера, который является стандартизированной реализацией двойного связанного списка: 

#include <list>
#include <algorithm>

struct Snode
{
    char data;
    int count;
};

class set
{
private:
    std::list<Snode> nodes;

    auto findValue(char value)
    {
        return std::find_if(nodes.begin(), nodes.end(),
            [=](const Snode &n){ return (n.data == value); }
        );
    }

public:
    bool isAvailable(char value)
    {
        return (find(value) != nullptr);
    }

    Snode* find(char value)
    {
        auto iter = findValue(value);
        if (iter != nodes.end())
            return &*iter;
        return nullptr;
    }

    bool isFirst(char value)
    {
        return ((!nodes.empty()) && (nodes.front().data == value));
    }

    bool isLast(char value)
    {
        return ((!nodes.empty()) && (nodes.back().data == value));
    }

    void display()
    {
        for (auto &n : nodes)
            std::cout << n.data << " " << n.count << std::endl;
    }

    void insert(char value)
    {
        Snode *temp = find(value);
        if (temp)
            temp->count += 1;
        else
            nodes.push_back(Snode{value, 1});
    }

    int count(char value)
    {
        Snode *temp = find(value);
        return (temp) ? temp->count : 0;
    }

    void deleteFirst()
    {
        if (!nodes.empty())
            nodes.pop_front();
    }

    void deleteLast()
    {
        if (!nodes.empty())
            nodes.pop_back();
    }

    void remove(char value)
    {
        auto iter = findValue(value);
        if (iter != nodes.end())
        {
            if (iter->count > 1)
                iter->count -= 1;
            else
                nodes.erase(iter);
        }
    }   
};
...