Слияние двух отсортированных связных списков


Я хочу улучшить этот код. Как ввести всех элементов в связанном списке одновременно? Я не написал код для удаления узла хочу, потому только список слияния для учебных целей.

#include <iostream>
#include <utility>

template<class T>
class LinkedList
{
  struct Node
  {
    T data;
    Node * next = nullptr;
    Node()          : data(), next(nullptr) {}
    Node(T&& value) : data(std::move(value)), next(nullptr) {}
  };

  Node *head;
public:
  LinkedList() : head(nullptr) {}
  LinkedList(const LinkedList& ll) = delete; //copy constructor
  LinkedList& operator=(const LinkedList& ll) = delete; //copy assignment
  ~LinkedList()
  {
    Node *tmp = nullptr;
    while(head)
    {
      tmp = head;
      head = head->next;
      delete tmp;
    }
    head = nullptr;
  }

   void insert(T&& value)
   {
    Node *node = new Node(std::move(value));
    Node *tmp = head;
    if(tmp == nullptr)
    {
      head = node;
    }
    else
    {
      while(tmp->next != nullptr)
      {
        tmp = tmp->next;
      }
      tmp->next = node;
    }
  }

  void mergeSortedList(LinkedList<T>& ll2)
  {
    Node *node = new Node();
    node->next = nullptr;
    Node *tmp = nullptr;
    tmp = node;

    Node *head1 = head;
    Node *head2 = ll2.head;

    while(head1 != nullptr && head2 != nullptr)
    {
      if(head1->data <= head2->data)
      {
        tmp->next = head1;
        tmp = tmp->next;
        head1 = head1->next;
      }
      else
      {
        tmp->next = head2;
        tmp = tmp->next;
        head2 = head2->next;
      }
    }
    while(head1 != nullptr && head2 == nullptr)
    {
      tmp->next = head1;
      tmp = tmp->next;
      head1 = head1->next;
    }
    while(head2 != nullptr && head1 == nullptr)
    {
      tmp->next = head2;
      tmp = tmp->next;
      head2 = head2->next;
    }
    tmp = tmp->next;
    delete tmp;

    // head of the new list
    head = node->next;
  }

  void printList()
  {
    Node *node = head;
    if(node == nullptr)
    {
      std::cout << "Empty List \n";
    }
    while(node != nullptr)
    {
      std::cout << node->data << " ";
      node = node->next;
    }
    std::cout << "\n";
  }
};

int main()
{
  LinkedList<int> ll1;
  ll1.insert(5);
  ll1.insert(10);
  ll1.insert(18);
  ll1.insert(25);
  std::cout << "List 1 : ";
  ll1.printList();

  LinkedList<int> ll2;
  ll2.insert(6);
  ll2.insert(8);
  ll2.insert(11);
  ll2.insert(20);
  ll2.insert(23);
  ll2.insert(28);
  ll2.insert(40);
  std::cout << "List 2 : ";
  ll2.printList();

  ll1.mergeSortedList(ll2);
  std::cout << "Merged List : ";
  ll1.printList();
}


629
1
задан 5 февраля 2018 в 09:02 Источник Поделиться
Комментарии
2 ответа

Накл.:


  • (Мнение:) функции-члены не должны содержать имя класса, потому что это излишне. Вместо того, чтобы использовать что-то вроде printToStdOut и sortedMergeFrom.

  • Там ужасно много var = var->next; на протяжении всего занятия. Хотя это только одна строка кода, стоит их учет в advance функция вот так:

    #include <cassert>
    ...
    static void advance(Node*& node)
    {
    assert(node != nullptr);
    node = node->next;
    }

    Это позволяет нам проверять каждый раз, что узел не nullptr. Это также легче для визуального анализа advance(tmp) или advance(node) чем tmp = tmp->next. Обратите внимание, что используется ссылка на указатель (т. е. изменяет указатель вне функции собственного объема), поэтому будьте осторожны, чтобы не пройти head в него напрямую.


  • Большая часть кода в insert функция на самом деле становится последним узлом в списке. Это может быть вынесена в отдельную функцию.

  • printList должно быть const.

  • printList может быть немного аккуратней: узел переменная нужна только если голова не пустая. (Он также выводит дополнительную строку для пустых списков). Как правило, он лучше всего для лечения особых случаев в начале функции, и возвращать рано:

    void printToStdOut() const
    {
    if (head == nullptr)
    {
    std::cout << "Empty List \n";
    return;
    }

    Node* node = head;

    while (node != nullptr)
    {
    std::cout << node->data << " ";
    advance(node);
    }

    std::cout << "\n";
    }


Слияния:

Это звучит, как вы хотите сделать в месте слияния, а также избежать создания каких-либо дополнительных узлов. Вы 90% пути там.

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

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

Рефакторинг и немного переименовать, дает следующее:

void sortedMergeFrom(LinkedList<T>& list2)
{
Node *source1 = head;
Node *source2 = list2.head;

Node *merged = /* take the "smallest" from the two sources... */; // previously "node" - we actually only need a pointer, not an allocated node
Node *current = merged; // previously "tmp" - the "tail" of the new list, onto which we add stuff

while (source1 != nullptr && source2 != nullptr)
{
if (source1->data <= source2->data)
{
current->next = source1;
advance(source1);
}
else
{
current->next = source2;
advance(source2);
}

advance(current);
}

// if we have extra nodes in either list, they're already connected, so we only need one assignment:
// (we don't bother advancing the source or current pointers here...)
if (source1 != nullptr)
current->next = source1;

if (source2 != nullptr)
current->next = source2;

head = merged;
list2.head = nullptr;
}

Выбирая первый узел как-то неловко. Он становится намного проще, если мы рассматриваем особые случаи (nullptr руководитель в каждом списке) во-первых, и вынесем идею "брать" указатель из источника и продвижения этого источника:

static Node* take(Node*& node)
{
Node* result = node;
advance(node);
return result;
}

void sortedMergeFrom(LinkedList<T>& list2)
{
if (list2.head == nullptr)
return; // nothing to do!

if (head == nullptr)
{
head = list2.head;
list2.head = nullptr;

return; // take everything from list2
}

Node *source1 = head;
Node *source2 = list2.head;

Node *merged = (source1->data <= source2->data) ? take(source1) : take(source2);
Node *current = merged;

while (source1 != nullptr && source2 != nullptr)
{
if (source1->data <= source2->data)
current->next = take(source1);
else
current->next = take(source2);

advance(current);
}

if (source1 != nullptr)
current->next = source1;

if (source2 != nullptr)
current->next = source2;

head = merged;
list2.head = nullptr;
}

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

2
ответ дан 5 февраля 2018 в 05:02 Источник Поделиться

Конструктор узел

Кажется странным, что мы можем только представить значений rvalue в качестве аргумента в конструктор. Я бы ожидать, чтобы иметь возможность перейти на копию тоже.

Обычный способ разрешить принять T по стоимостии построить data от этого значения:

Node(T value = T()) : data(std::move(value)) {}

Обратите внимание, два других изменения: я добавил По умолчанию аргумент, поэтому нам не нужно писать конструктор по умолчанию, и я опустил инициализации nextкак мы написали соответствующую по умолчанию инициализатором для него.

Конструктор список

Если мы предоставляем инициализатор для headнам не нужно писать конструктор по умолчанию.

Мы могли бы принять список элементов при создании связанного списка. Это будет выглядеть примерно так:

LinkedList() = default;
LinkedList(std::initializer_list<T> elements)
{
for (auto& e: elements)
insert(std::move(e));
}

Указатель владения

Мы должны быть абсолютно ясно, что каждый объект, созданный с new имеет только один владелец, который знает, когда объект больше не находится в использовании и будет delete его в этой точке. При перемещении узлов из одного списка в другой, важно, что право собственности переходит - если оба списка, думаю, что они являются владельцем узла, он будет дважды удален, и если ни списков нет, то будет утечка.

Мы можем написать код, чтобы сделать это вручную, но проще и менее подверженным ошибкам в #include <memory> и затем сделать использование смарт-указатель типов, которые предназначены для нас.

3
ответ дан 5 февраля 2018 в 02:02 Источник Поделиться