Круговой реализация связанных списков в C++


Я хочу улучшить этот код.

#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) {}
  };
  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_at_begin(T);
  void insert_at_end(T);
  void delete_node(T);
  void print_list();

private:
  struct Node *search(T value)
  {
    Node *node = head;
    while(node->next != head)
    {
      if(node->data == value)
        return node;

      node = node->next;
    }
    std::cerr << "No such element in the List \n";
    return nullptr;
  }
};

template <class T>
void circular_linked_list<T>::insert_at_begin(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;
  head = node;
}

template <class T>
void circular_linked_list<T>::insert_at_end(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>::delete_node(T value)
{
  Node *node = search(value);
  Node *tmp = head;
  Node *tail = head;
  while(tail->next != head)
  {
    tail = tail->next;
  }

  if(tmp == node)
  {
    head = tmp->next; //deleting first element
    tail->next = head;
  }
  else
  {
    while(node != nullptr)
    {
      if(tmp->next == node)
      {
        tmp->next = node->next;
        return;
      }
      tmp = tmp->next;
    }
  }
  delete tmp;
}

template <class T>
void circular_linked_list<T>::print_list()
{
  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;
  cll1.insert_at_end(2);
  cll1.insert_at_end(3);
  cll1.insert_at_end(4);
  cll1.insert_at_begin(1);
  cll1.insert_at_begin(0);
  cll1.print_list();
  cll1.delete_node(2);
  cll1.print_list();
}


3231
0
задан 29 января 2018 в 09:01 Источник Поделиться
Комментарии
1 ответ

Дизайн

С односвязанный список O(n) чтобы найти конец (предполагая, что вы храните начале). Поэтому его часто приятно отслеживать как начало и конец списка в объекте списка.

Лично я бы пошел с двусвязным списком (следующий/предыдущий). Таким образом, вы можете хранить только головой, но и широкий хвост (на круговой список) - это просто получение ссылки до головы.

// Head of a list
list->head

// Tail of a list (doubly linked)
list->head->prev;

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

Так от этого длинного описания два изменения, которые я сделал бы.


  1. Двусвязный список следующий/предыдущий

  2. Добавление узла дозорного.

Комментарий Код

Перемещать и копировать

Я вижу вы удалили операций копирования/перемещения. Хорошо, если вы еще работаете через него. Но в конце концов вам понадобится для их реализации. Это на самом деле довольно просто, когда вы освоите трюки (идиомы).

Как простой ручной helpping:

circular_linked_list(const circular_linked_list& cll)
// This you need to implement in full.
// I leave the details to you (but a full deep copy of the list is needed).

// The assignment operator is easy.
// It is implemented in terms of the copy constructor.
// And the swap operation.
circular_linked_list& operator=(const circular_linked_list& cll)
{
circular_linked_list copy(cll); // Make a copy.
swap(copy); // Call the swap method.
return *this;
// Small improvement can be made (look up copy and swap idiom).
}

// Move is easily implemented using a swap.
circular_linked_list(circular_linked_list&& cll) noexcept // dont forget the noexcept
// Dont forget to initialize the members correctly.
{
// Swapping implements the requirements of move.
// It also provided deferred deletion (which is a nice side affect)
// allowing potential reuse of memory. But usually the object
// will be correctly and normally destroyed.
// It also provides the strong exception guarantee.
swap(cll);
}

circular_linked_list& operator=(circular_linked_list&& cll) noexcept
{
swap(cll);
return *this;
}

void swap(circular_linked_list& other) noexcept
{
using std::swap;
// Implement the swap of all members for other into this.
}

friend void swap(circular_linked_list& lhs, circular_linked_list& rhs)
{
lhs.swap(rhs);
}

Не нужно здесь явный конструктор.

  struct Node
{
T data;
Node * next;
Node(T value) : data(std::move(value)), next(nullptr) {}
};

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

  Node* node = new Node{ 12, nullptr };

Но вы можете изучить альтернативных конструкторов.

  // copy Cosntruct node.
Node(T const& value); // Pass by const reference and copy in
Node(T&& value); // Pass by r-value ref and move in
template<typename... P>
Node(P&&... args); // Pass using the arguments that constructor
// T allowing construction in place.

Печать

Это нормально.

  void print_list();

Но в C++ мы обычно печати с помощью operator<<. Так приятно определить этот оператор для вашего класса. Также std::cout находятся не только трансляцию вы можете печатать тоже (файлы/строки две, что выскочить, но многое эмулируется как потоки).

  void print_list(std::ostream& str = std::cout) const;
friend std::ostream& operator<<(std::ostream& str, circular_linked_list const& data)
{
data.print_list(str);
return str;
}

Вполне хороший поиск.

  struct Node *search(T value)
{
Node *node = head;
while(node->next != head)
{
if(node->data == value)
return node;

node = node->next;
}

Но это может быть проще написать как для петли:

    for(Node *node = head; node->next != head; node = node->next)
{
if(node->data == value) {
return node;
}
}

Вставить

Обе операции вставки имеют много общего кода.
Было бы лучше, если бы вы вынести общий код в отдельную функцию.

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

Быстрый выход из удалить.

Если это возвращается nullptr тогда есть ли смысл продолжать?

  Node *node = search(value);

Много дополнительной работы в удалить.
Я не думаю, что вам на самом деле нужен хвост.

Ошибка в печати.

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

Деструктор может быть упрощена.

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

template <class T>
circular_linked_list<T>::~circular_linked_list()
{
Node* last = nullptr;
Node* next
for(Node* loop = head; loop != last; loop = next) {
last = head;
next = head->next;
delete loop;
}
}

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