Двусвязные списки в C++


Пожалуйста, просмотрите код:

#include <iostream>
using namespace std;

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

template <class T>
class DoublyLinkedList
{
public:
  DoublyLinkedList() : head(NULL), tail(NULL) {}
  DoublyLinkedList(const DoublyLinkedList<T> & dll);
  ~DoublyLinkedList();
  void addNode(T data);
  //void insertNodeBefore(int data, int before);
  //void insertNodeAfter(int data, int after);
  void deleteNode(T data);
  template <class U>
  friend std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll);
private:
  Node<T> * head;
  Node<T> * tail;
};

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

  return os;
}

template <class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
  Node<T> * tmp = NULL;
  while (head)
    { 
      tmp = head;
      head = head->next;
      delete tmp;
    }
  head = tail = NULL;
}

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

  Node<T> * tmp = head;
  if (tmp == NULL)
    {
      head = tail = t;
    }
  else
    {
      while (tmp->next != NULL)
        {
          tmp = tmp->next;
        }

      tmp->next = t;
      t->prev = tail;

      tail = t;
    }
}

template <class T>
void DoublyLinkedList<T>::deleteNode(T data)
{
  Node<T> * tmp = head;
  while (tmp && tmp->data != data)
    {
      tmp = tmp->next;
    }

  if (tmp)
    {
      if (tmp->prev && tmp->next) // no change to head or tail
        {
          tmp->prev->next = tmp->next;
          tmp->next->prev = tmp->prev;
        }
      else if (tmp->prev) // change to tail
        {
          tmp->prev->next = tmp->next;
          tail = tmp->prev;
        }
      else if (tmp->next) // change to head
        {
          tmp->next->prev = tmp->prev;
          head = tmp->next;
        }

      delete tmp;
    }
}

template <class T>
DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T> & dll)
{
  Node<T> * tmp = dll.head;
  while (tmp)
    {
      this->addNode(tmp->data);
      tmp = tmp->next;
    }
}

int main()
{
  DoublyLinkedList<int> dll;

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

  cout << dll << endl;
  DoublyLinkedList<int> dll2(dll);
  cout << dll2 << endl;

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

  cout << dll << endl;
  cout << dll2 << endl;

  return 0;
}


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


  1. Рассмотреть вопрос о замене узла с:

    typedef Node<T> node_t;

    ...

    node_t node;


  2. Рассмотреть вопрос о внесении ваш STL-совместимым реализации. Если бы я был пользователем этого класса, первое, что я хотел спросить "как я могу перебрать этот список?". Двусвязный списки-это здорово, когда добавлять элементы в середину, как мне это сделать? (это про операции как метод insertbefore(), insertAfter()). Как же я разберусь? Как я могу проверить, если элемент находится в списке? Как мне найти используя предикат?

  3. Почему вы называете метод deleteNode если это единственный аргумент имеет тип Т? Это больше findNodeByValueAndDeleteIt(Т).

  4. Насчет оператора присваивания? Вы должны либо объявить его закрытым (если вы не поддерживаете его), или это конкретно реализовать в зависимости от семантики вы хотите поддержать (глубокое копирование (скорее всего, что вы хотите), ссылка, коровы и т. д.):

    YourList<int> a; // do something with a

    YourList<int> b; // do something with b

    a = b; // what is "a" here? what if I add nodes to a? will it affect b?

    // imagine, scope ends here, dtor for b is called, everything's fine

    // dtor for a is called - here you're going to crash, since

    // both a and b were using the same memory and this memory is already

    // free, since b's dtor has already been called at this point


  5. Для таких методов, как аннулировать операцию addnode(Т-данные) - зачем вам передавать данные по значению? Поскольку вы храните значения элемента по значению, в любом случае вы собираетесь назвать свою копию-конструктор. Копия-конструктор требуется константная ссылка, так что вы должны рассмотреть вопрос о замене операцию addnode с недействительными операцию addnode(Т const и& данных).

  6. с помощью пространства имен std; - это только для суда , а не с std::соиь в основной()?

Ничего не проверили, от "алгоритмической" точки зрения, только c++.

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

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

1
ответ дан 17 октября 2011 в 12:10 Источник Поделиться