Разделить список круговые связан на две половинки


Я хочу улучшить этот код. Я хочу ввести все значения в связанном списке, в то время как circular_linked_list<int> cll1(5, 10, 18, 25);

#include <iostream>
#include <utility>

template <class T>
class circular_linked_list
{
  struct Node
  {
    T data;
    Node * next;
    Node(T&& value) : data(std::move(value)), next(nullptr) {}
    /*
    //to enter any number of arguments
    template <typename... Args>
    Node(Args&&... args) : data(std::forward<Args>(args)...), next(nullptr)
                         {}
                         */
  };
  Node *head;

public:
  circular_linked_list() : head(nullptr) {}
  circular_linked_list(const circular_linked_list& cll) = delete; //copy constructor
  circular_linked_list(circular_linked_list&& cll) = delete; //move constructor
  circular_linked_list& operator=(const circular_linked_list& cll) = delete; //copy assignment
  circular_linked_list& operator=(circular_linked_list&& cll) = delete; //move assignment
  ~circular_linked_list();

  void insert_node(T&&);

  /*
  template <typename... Args>
  void insert_node(Args&&... args)
   { ..
     code
     ..
   } */

  Node *split_list()//Returns the mid-node
  {
    Node *slow_ptr = head;
    Node *fast_ptr = head;

    //If odd number of nodes then fast_ptr->next = head
    //If even number of nodes then fast_ptr->next->next = head
    while(fast_ptr->next != head && fast_ptr->next->next != head)
    {
      fast_ptr = fast_ptr->next->next;
      slow_ptr = slow_ptr->next;
    }
    return slow_ptr;
  }

  void print_split_lists();
  void print_list(Node*);
  void print_list()
  {
    print_list(head);
  }
};

template <class T>
void circular_linked_list<T>::insert_node(T&& value)
{
  Node *node = new Node(std::move(value));
  if(head == nullptr)
  {
    node->next = node;
    head = node;
    return;
  }
  Node *tmp = head;
  while(tmp->next != head)
  {
    tmp = tmp->next;
  }
  tmp->next = node;
  node->next = head;
}

template <class T>
void circular_linked_list<T>::print_split_lists()
{
  Node *head1 = nullptr;
  Node *head2 = nullptr;
  Node *mid_node = split_list();
  Node *tail = head;

  while(tail->next != head)
  {
    tail = tail->next;
  }

  if(head->next != head)
  {
  head2 = mid_node->next;
  }

  tail->next = head2;

  head1 = head;
  mid_node->next = head1;
  std::cout << "First half of list \n";
  print_list(head1);
  std::cout << "Second half of list \n";
  print_list(head2);
}

template <class T>
void circular_linked_list<T>::print_list(Node *head)
{
  Node *tmp = head;
  while(tmp->next != head)
  {
    std::cout << tmp->data << ' ';
    tmp = tmp->next;
  }
  std::cout << tmp->data << '\n';
}

template <class T>
circular_linked_list<T>::~circular_linked_list()
{
  Node *tmp = nullptr;
  Node *tail = head;
  while(tail->next != head)
  {
    tail = tail->next;
  }
  tail->next = nullptr;

  while(head != nullptr)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
}

int main()
{
  //circular_linked_list<int> cll1(5, 10, 18, 25);
  circular_linked_list<int> cll1;
  cll1.insert_node(2);
  cll1.insert_node(3);
  cll1.insert_node(4);
  cll1.insert_node(1);
  cll1.insert_node(0);
  cll1.print_list();
  cll1.print_split_lists();
}


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

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

Именования

Первое, что я бы сделать, чтобы улучшить этот код будет исправить именования. Это почти всегда хороший первый шаг для проверки кода, но в данном случае, я думаю, очень важно, поскольку некоторые ваши методы обманчивым именем, подразумевая, что они что-то там не. Например, split_list() метод не разбивает список. Вместо этого он находит средний узел в списке. Это должно быть нечто вроде get_middle_node(). У вас даже комментарий рядом с ним, говоря, что он делает нечто иное, чем его имя. Это большая подсказка, что он назван неправильно.

Внутри метода, есть 2 указателя по имени slow_ptr и fast_ptr. Мне пришлось прочитать код около 5 раз, прежде чем я понял, что "скорая" указатель увеличиваем на 2 и "медленные" указатель увеличиваем на 1. Имена даже не имеет смысла, так как указателей нет скорости. Они оба получат доступ к своим данным в том же количестве времени! Я бы переименовать их в что-то вроде advance_by_1 и advance_by_2. И я бы, наверное, и оставить свой комментарий, объясняя, что, когда advance_by_2 ударяет в голову, advance_by_1 будет указывать на середину узла, потому что это довольно умный способ нахождения среднего узла. Я не думаю, что он настолько умен, что вы не должны делать это, но я думаю, что вы должны уточнить с комментарием.

Имя print_split_lists() это точно, но я был смущен, потому что я думала, что абонент будет в конечном итоге получить обратно 2 списки, или что метод должен быть принят второй список, или что-то. Метод на самом деле не разделить список - это делает какие-то временные переменные, которые действуют как 2 списка, и затем печатает их. И если я не ошибаюсь, она оставляет список в плохом состоянии. Что смущает меня. Что будет в случае использования там, где я хочу напечатать один список в 2 списках, но потом на самом деле не в конечном итоге с 2 списки? Это похоже на метод, который не нужен. Я думал, что вы захотите иметь способ, чтобы разделить лист на 2 (и вернуть 2 списки), а потом просто позвонить print_list на каждый из этих 2 новые списки.

Вы спросите:


Как я могу написать функцию, которая возвращает два списка и как использовать его в main() функция?

Есть несколько способов справиться с этим. Вы можете:


  1. Написать функцию, которая находит средний узел, создает новый список со второй половины старый список, и устанавливает старый список, чтобы быть в первой половине

  2. Написать функцию, которая создает 2 новые списки и заполняет их с 1-й и 2-й половины первоначального списка, соответственно.

Предположим теперь, что Вариант 1 является приемлемым. Я бы сделал это так (не проверял) :

void circular_linked_list::split_list_at_middle(circular_linked_list& secondHalf)
{
Node* tail = find_tail_node();
Node* mid = find_middle_node();

// Move the second half of the list into a new list
second_half.head = mid->next;
tail->next = second_half.head;

// Set our list to only be the first half
mid->next = head;
}

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

Затем в main()вы назвали это так:

circular_linked_list secondHalf;
originalList.split_list_at_middle(secondHalf);
std::cout << "First half of list \n";
originalList.print_list();
std::cout << "Second half of list \n";
secondHalf.print_list();

Производительности

Одним из основных недостатков связанных списков с произвольным доступом. Если вам нужно найти nго узла, нужно перебрать n узлы, чтобы добраться туда. Поэтому найти средний узел всегда потребует перебора (длина списка) / 2 узлов. И обнаружив, что узел хвост всегда требует перебора (длина списка) узлов. Если вы не знаете, что вам нужно сделать эти 2 вещи и подготовиться к нему.

Одним из распространенных способов сделать список вставки очень быстро (за O(1)), чтобы сохранить не только head узел, но tail узел. (Некоторые люди просто держат tail узел, а затем вернуть head узел, который просто возвращает tail->next. Не стоит размениваться на мой взгляд, но вы можете не соглашаться.) Теперь вставка в конец списка просто включает:

newNode->next = tail->next; // or just head
tail->next = newNode;

Нет поиска в списке на конец первого.

Так почему мы не можем сделать то же самое с серединой узла? Если вы держите midNode указатель и отслеживать длину списка, вы можете сделать что-то подобное. Каждый раз, когда вы делаете вставки, увеличивает длину счетчика. Каждый раз, когда вы делаете исключения, то уменьшаем его. Когда длина прилавка даже во время вставки, увеличивать midNode указатель к точке в midNode->next. Если вы хотите сохранить ее актуальной во время удаления, вы должны иметь двунаправленный связанный список, или вы должны пройти список и найти предыдущий узел. Часто бывает так, что нужно ходить в списке, чтобы найти узел, чтобы удалить, так что это не слишком обременительным. Это немного сложнее удалить, потому что вы должны знать, является ли узел удалении впереди или после середины узла. Но получается, что ваш класс не фактическое ручка удалений!

Ручка Удалений

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

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