Блог

Главная - Вопросы по программированию - Как мне объединить 2 связанных списка, чтобы создать новый список?

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

#c #linked-list #singly-linked-list

#c #связанный список #single-linked-list

Вопрос:

Я пытаюсь взять два связанных списка «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;
            }
        }
    }

Комментарии:

1. Как вы хотите их объединить? Добавить один в конец другого? Или перемешать узлы? И что вы пробовали до сих пор (не создавая список, а действительно пытаясь объединить их)?

2. for(int i = 1; i <= 1; i ) это очень запутанный способ сделать что-то ровно один раз. Удалите цикл.

3. Нарисуйте свои входные списки в виде диаграмм с прямоугольниками и стрелками на бумаге. Затем начните с их заголовков и переставьте стрелки между полями так, как вы хотите, чтобы они были. Конечным результатом является ваш вывод. Подумайте некоторое время, возможно, выпейте чашечку кофе, а затем переведите вашу процедуру в код.

4. for(int i = 1; i <= 1; i ) ? зачем?

Ответ №1:

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

Ответ №2:

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

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

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

Я добавил несколько «классических» методов, чтобы помочь использовать 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 amp; operator=(const List amp; 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 amp; l1, const List amp; 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)