Круговой Двусвязный Список


После улучшения кода с предложениями на мой предыдущий вопрос. Я реализовал конструктор копирования, задание копирования, конструктор перемещения, перемещение assignmnet. Есть предложение на магистраль узле, но я не знаю, как написать код для этого, и я использовал exit(0) в конце концов, потому что программа не была прекращена. Я хочу улучшить этот код.

#include <iostream>
#include <utility>

template <typename T>
class circular_doubly_linked_list
{
  struct Node
  {
    T data;
    Node * next;
    Node * prev;
    Node(T value) : data(std::move(value)),
                    next(nullptr),
                    prev(nullptr)
                    {}
  };
  Node *head, *tail;

public:
  circular_doubly_linked_list() : head(nullptr), tail(nullptr) {}
  circular_doubly_linked_list(const circular_doubly_linked_list &); //copy constructor
  circular_doubly_linked_list& operator=(const circular_doubly_linked_list& cdll) //copy assignment
  {
    circular_doubly_linked_list  temp(cdll);
    temp.swap(*this);
    return *this;
  }
  circular_doubly_linked_list(circular_doubly_linked_list&&) noexcept; //move constructor
  circular_doubly_linked_list& operator=(circular_doubly_linked_list&& cdll) noexcept //move assignment
  {
    cdll.swap(*this);
    return *this;
  }
  ~circular_doubly_linked_list();

  void append_node(T);
  void delete_node(T);

  friend void swap(circular_doubly_linked_list& lhs, circular_doubly_linked_list& rhs)
  {
    std::swap(lhs.head, rhs.head);
  }

  template <typename U>
  friend std::ostream & operator<<(std::ostream & os, const circular_doubly_linked_list<U> & cdll)
  {
    cdll.print_list(os);
    return os;
  }

private:

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

  void print_list(std::ostream& os = std::cout) const
  {
    Node *tmp = head;
    while(tmp->next != head)
    {
      std::cout << tmp->data << ' ';
      tmp = tmp->next;
    }
    std::cout << tmp->data << '\n';
  }
};

template <typename T>
circular_doubly_linked_list<T>::circular_doubly_linked_list(const circular_doubly_linked_list & cdll)
{
  if(cdll.head == nullptr)
  {
    head = tail = nullptr;
  }
  else
  {
    head = new Node(cdll.head->data);
    Node *curr = head;
    Node *tmp = head;
    Node *obj_curr = cdll.head;
    while(obj_curr->next != cdll.head)
    {
      curr->next = new Node(obj_curr->next->data);
      obj_curr = obj_curr->next;
      curr = curr->next;
      curr->prev = tmp;
      tmp = tmp->next;
    }
    tail = curr;
    curr->next = head;
    head->prev = curr;
  }
}

template <typename T>
circular_doubly_linked_list<T>::circular_doubly_linked_list(circular_doubly_linked_list&& cdll) noexcept
{
  head = tail = nullptr;
  swap(*this, cdll);
}

template <typename T>
void circular_doubly_linked_list<T>::append_node(T value)
{
  Node *node = new Node(std::move(value));

  if(head == nullptr)
  {
    node->next = node;
    node->prev = node;
    head = node;
    tail = node;
  }

  tail = head->prev;
  tail->next = node;
  node->prev = tail;
  node->next = head;
  head->prev = node;
  tail = node;
}

template <typename T>
void circular_doubly_linked_list<T>::delete_node(T value)
{
  Node *node = search(value);
  if(node == nullptr)
  {
    std::cerr << "No such value in the list\n";
    return;
  }
  else
  {
  Node *tmp = head;
  Node *tail = head->prev;
  if(tmp == node)
  {
    tail->next = tmp->next;
    tmp->prev->next->prev = tail;
    head = tail->prev;
    delete tmp;
    return;
  }
  else if(tail == node)
  {
    Node *curr = tail;
    tmp = tail->prev;
    tmp->next = curr->next;
    head->prev = tmp;
    tail = tmp;
    delete curr;
    return;
  }
  else
  {
    while(tmp->next != head)
    {
      if(tmp == node)
      {
        tmp->prev->next = tmp->next;
        tmp->prev->next->prev = tmp->prev;
        delete tmp;
        return;
      }
      tmp = tmp->next;
    }
  }
}

}

template <typename T>
circular_doubly_linked_list<T>::~circular_doubly_linked_list()
{
  Node *tmp = nullptr;
  while(head!= nullptr)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
}

int main()
{
  circular_doubly_linked_list<int> cdll1;
  cdll1.append_node(3);
  cdll1.append_node(4);
  cdll1.append_node(5);
  cdll1.append_node(6);
  cdll1.append_node(7);
  cdll1.append_node(8);
  std::cout << cdll1;
  cdll1.delete_node(6);
  std::cout << cdll1;
  circular_doubly_linked_list<int> cdll2(cdll1); // using copy constructor
  std::cout << "Linked List 2: " << cdll2;
  circular_doubly_linked_list<int> cdll3 = cdll1; //using copy assignment
  std::cout << "Linked List 3: " << cdll3;
  circular_doubly_linked_list<int> cdll4 = std::move(cdll2); //using move constructor
  std::cout << "Linked list 4: " << cdll4;
  exit(0);
}


841
2
задан 31 января 2018 в 08:01 Источник Поделиться
Комментарии
1 ответ

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

Я вижу, что вы предоставляете многочисленными функциями, как основной интерфейс (поиск, печать и т. д.) что должны оставаться за пределами вашего класса.

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

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

Тогда, если я хочу, чтобы найти элемент списка, я напишу:

#include <algorithm>
...
auto pos = std::find(lst.begin(), lst.end(), elem);
...

Или если я хочу, чтобы распечатать список:

for (auto elem : lst) std::cout << elem << " ";

Возможно, вы захотите взглянуть на эту ссылку: https://stackoverflow.com/questions/7758580/writing-your-own-stl-container/7759622#7759622 перед тем как поставить себе задачу, потому что это крайне сложно.

2
ответ дан 31 января 2018 в 10:01 Источник Поделиться