Как объединить или объединить 2 связанных списка, чтобы создать новый список? - PullRequest
Новая
       14

Как объединить или объединить 2 связанных списка, чтобы создать новый список?

0 голосов
/ 27 марта 2019

Я пытаюсь взять два связанных списка «list_1» и «list_2», а затем объединить их и поместить в «list_3». Я создал два списка и не могу понять, как их объединить. Код, который я добавил, - это то, как я создал свои списки. Довольно плохо знаком с указателями и связанными списками, поэтому любая помощь будет принята с благодарностью, спасибо! 

struct node
{
    int data;
    node *next;
};

class List
{
    public:
        node *head, *tail;
    List()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        for(int i = 1; i <= 1; i++)
        {
            node *temp = new node;
            temp -> data = n;
            temp -> next = NULL;

            if(head == NULL)
            {
                head = temp;
                tail = temp;
            }
            else{
                tail -> next = temp;
                tail = tail -> next;
            }
        }
    }

Ответы [ 2 ]

1 голос
/ 27 марта 2019

Вы должны "перемонтировать" их.head списка B следует перевести в tail списка A, чтобы можно было удалить объект List из списка B, но его члены не будут удалены.Введите новый метод merge(List* list) параметр, и там измените this->tail на list->head и обновите this->tail, чтобы он стал list->tail.

0 голосов
/ 27 марта 2019

Как объединить или объединить 2 связанных списка, чтобы создать новый список

просто используйте add_node итерации по двум спискам для объединения

здесь предложение, где объединяет , изменяет текущий список, легко добавить новый конструктор, получающий два списка в аргументах или статический метод объединения и т. Д., Если вы предпочитаете эти способы

Я добавил несколько «классических» методов, чтобы помочь и иметь возможность использовать valgrind без утечек памяти, а также поместил Список атрибутов Приватный , поскольку их публично не очень хороший способ 

#include <iostream>

struct node
{
  int data;
  node * next;

  node(int v) : data(v), next(nullptr) {}
};

class List
{
  private:
    node *head, *tail;

  public:
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    List & operator=(const List & l) {            
      clear();

      const node * n = l.head;

      while (n != nullptr) {
        add_node(n->data);
        n = n->next;
      }
      return *this;
    }
    // + copy constructor, move etc

    void clear() {
       while (head != nullptr) {
         tail = head->next;
         delete head;
         head = tail;
       }
       head = tail = nullptr;
    }

    void add_node(int n)
    {
      node * temp = new node(n);

      if(head == NULL)
      {
        head = temp;
        tail = temp;
      }
      else
      {
        tail -> next = temp;
        tail = tail -> next;
      }
    }

    void combine(const List & l1, const List & l2) {
      *this = l1;

      node * n = l2.head;

      while (n != nullptr) {
        add_node(n->data);
        n = n->next;
      }
    }

    void pr() const {
      const node * n = head;

      while (n != nullptr) {
        std::cout << n->data << ' ';
        n = n->next;
      }
      std::cout << std::endl;
    }
};

int main()
{
  List l1, l2, l3;

  l1.add_node(1);
  l1.add_node(2);
  l1.add_node(3);

  l2.add_node(4);
  l2.add_node(5);

  l3.add_node(33);
  l3.pr();
  l3.combine(l1, l2);
  l3.pr();
}

Компиляция и исполнение: 

/tmp % g++ -pedantic -Wextra -Wall c.cc
/tmp % ./a.out
33 
1 2 3 4 5

Исполнение под valgrind 

/tmp % valgrind ./a.out
==8413== Memcheck, a memory error detector
==8413== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==8413== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==8413== Command: ./a.out
==8413== 
33 
1 2 3 4 5 
==8413== 
==8413== HEAP SUMMARY:
==8413==     in use at exit: 0 bytes in 0 blocks
==8413==   total heap usage: 11 allocs, 11 frees, 176 bytes allocated
==8413== 
==8413== All heap blocks were freed -- no leaks are possible
==8413== 
==8413== For counts of detected and suppressed errors, rerun with: -v
==8413== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)
...