Список круговые связаны


Пожалуйста, ознакомьтесь с этим:

#include <iostream>
using namespace std;

template <class T>
struct Node
{
  T data;
  Node * next;
  Node(T data) : data(data), next(NULL) {}
};

template <class T>
class CircularLinkedList
{
public:
  CircularLinkedList() : head(NULL) {}
  ~CircularLinkedList();
  void addNode(T data);
  void deleteNode(T data);
  template <class U>
  friend std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll);
private:
  Node<T> * head;
};

template <class T>
CircularLinkedList<T>::~CircularLinkedList()
{
  if (head)
    {
      Node<T> * tmp = head;
      while (tmp->next != head)
        {
          Node<T> * t = tmp;
          tmp = tmp->next;
          delete(t);
        }
      delete tmp;
      head = NULL;
    }
}

template <class T>
void CircularLinkedList<T>::addNode(T data)
{
  Node<T> * t = new Node<T>(data);

  if (head == NULL)
    {
      t->next = t;
      head = t;
      return;
    }

  Node<T> * tmp = head;
  while (tmp->next !=  head)
    {
      tmp = tmp->next;
    }

  tmp->next = t;
  t->next = head;
}

template <class T>
void CircularLinkedList<T>::deleteNode(T data)
{
  Node<T> * tmp = head;
  Node<T> * prev = NULL;
  while (tmp->next !=  head)
    {
      if (tmp->data == data) break;
      prev = tmp;
      tmp = tmp->next;
    }

  if (tmp == head)
    {
      while (tmp->next != head)
        {
          tmp = tmp->next;
        }
      tmp->next = head->next;
      delete head;
      head = tmp->next;
    }
  else
    {
      prev->next = tmp->next;
      delete tmp;
    }
}

template <class U>
std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll)
{
  Node<U> * head = cll.head;
  if (head)
    {
      Node<U> * tmp = head;
      while (tmp->next != head)
        {
          os << tmp->data << " ";
          tmp = tmp->next;
        }
      os << tmp->data;
    }
  return os;
}

int main()
{
  CircularLinkedList<int> cll;

  cll.addNode(1);
  cll.addNode(2);
  cll.addNode(3);
  cll.addNode(4);
  cll.addNode(5);

  cout << cll << endl;

  cll.deleteNode(3);
  cll.deleteNode(1);
  cll.deleteNode(5);

  cout << cll << endl;

  return 0;
}


28225
4
задан 7 сентября 2011 в 05:09 Источник Поделиться
Комментарии
3 ответа

)

Мой первый комментарий вы должны начать смотреть на смарт-указатели.
Они, безусловно, упрощают код.

Второй комментарий: посмотрите на контейнеры STL.
Контейнеры в C++ следовать определенной схеме. Идея заключается в том, что мы хотим использовать алгоритмы на контейнеры взаимозаменяемы и, следовательно, контейнеры следуйте этим соглашениям, чтобы сделать их легко использовать со стандартными алгоритмами.

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

Четвертый комментарий: предпочитаю быть передачи параметров по константной ссылке. Для простых объектов, таких как целые числа, он не будет иметь никакого значения. Но у вас есть templatised код и T может быть любым типом. Таким образом, передача по значению будет вызывать копия (которые могут быть дорогими).

Рассматривая приведенный выше код:
Сложность добавлением узла составляет o(Н). Поддерживая голову и указатель на хвост вы можете изменить это, чтобы иметь сложность O(1). т. е. эта петля становится ненужным.

Node<T> * tmp = head;
while (tmp->next != head)
{
tmp = tmp->next;
}

У вас есть выход оператора с std::поток & оператора<<(с std::поток & ОС, константный CircularLinkedList & ХЛЛ) было бы неплохо, если бы вы симметричного ввода оператора. В этой ситуации вам нужно беспокоиться о размер списка (или добавить специальный символ завершения). Поэтому создание оператора ввода будет влиять на ваш дизайн оператор вывода.

6
ответ дан 7 сентября 2011 в 02:09 Источник Поделиться

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

например,

int main() {
CircularLinkedList<int> cll;

cll.addNode(5);
cout << cll << endl;
cll.deleteNode(5);
cout << cll << endl;
return 0;
}

1
ответ дан 31 мая 2012 в 06:05 Источник Поделиться

Кроме того, для простоты я бы оставил ссылку на последний добавленный элемент (назовем его хвост может быть не так как он круговой, но опять же сжато с головой). Таким образом, вставки будет O(1) вместо o(n), который имеет смысл, так как вы знаете, вы будете добавить его в списке последним, прямо перед головой. Затем вы могли бы сделать:

if (head == NULL) {
head = t;
head->next = head;
return;
}

tail->next = t;
t->next = head;

в add_node.

1
ответ дан 31 мая 2012 в 07:05 Источник Поделиться