Реализация связанных списков в C++


Я пытаюсь реализовать связанный список. Я реализовал сортировку с сортировки слиянием, реверсивных и т. д....

LinkedList.cpp

#include <iostream>

template <class T>
struct Node
{
  T data;
  Node * next;
};

template <class T>
class LinkedList
{
public:
  LinkedList() : head(NULL), size(0) {};
  ~LinkedList() { destroyList(); };
  bool addNode(T data);
  bool deleteNode(T data);
  Node<T> * searchNode(T data);
  void printList();
  void reverseList();
  void sortList();
private:
  Node<T> * head;
  int size;
  void destroyList();
  Node<T>* mergeSort(Node<T> * head, int total);
  Node<T>* Merge(Node<T>* left, int lcount, Node<T>* right, int rcount);
  void print(Node<T> * tmp);
};

template <class T>
bool LinkedList<T>::addNode(T data)
{
try
  {
    Node<T> * tmp = new Node<T>();
    tmp->data = data;
    tmp->next = head;
    head = tmp;
    ++size;
    return true;
  }
catch(std::exception & ex)
  {
    return false;
  }
}

template <class T>
bool LinkedList<T>::deleteNode(T data)
{
  Node<T> *curr = head, *prev = NULL;

  while (curr)
  {
    if (curr->data == data) break;

    prev = curr;
    curr = curr->next;
  }

  if (curr)
    {
      if (prev)
        {
          prev->next = curr->next;
        }
      else
        {
          head = curr->next;
        }
      delete(curr);
      --size;
      return true;
    }
  else
    {
      return false;
    }
}

template <class T>
Node<T> * LinkedList<T>::searchNode(T data)
{
  Node<T> * tmp = head;
  while (tmp)
    {
      if (tmp->data == data)
        {
          return tmp;
        }
      tmp = tmp->next;
    }
  return NULL;
}

template <class T>
void LinkedList<T>::print(Node<T> * tmp)
{
  bool printNewLine = (tmp) ? true : false;
  while (tmp)
    {
      std::cout << tmp->data << ",";
      tmp = tmp->next;
    } 

  if (printNewLine)
    {
      std::cout << std::endl;
    }
}

template <class T>
void LinkedList<T>::printList()
{
  Node<T> * tmp = head;
  bool printNewLine = (tmp) ? true : false;
  while (tmp)
    {
      std::cout << tmp->data << "|";
      tmp = tmp->next;
    } 

  if (printNewLine)
    {
      std::cout << std::endl;
    }
}

template <class T>
void LinkedList<T>::destroyList()
{
  Node<T> * tmp = NULL;
  while (head)
    {
      tmp = head;
      head = head->next;
      //std::cout << "deleting data " << tmp->data << std::endl;
      delete(tmp);
    }
}

template <class T>
void LinkedList<T>::reverseList()
{
  Node<T> *curr = head, *prev = head, *save = NULL;

  while (curr)
    {
      save = curr->next;
      curr->next = prev;
      prev = curr;
      curr = save;
    }

  head->next = NULL;
  head = prev;
}

//use merge sort
template <class T>
void LinkedList<T>::sortList()
{
  head = mergeSort(head, size);
}

template <class T>
Node<T>* LinkedList<T>::mergeSort(Node<T> * first, int total)
{
  if (total < 1) { return first; }
  if (total < 2) { first->next = NULL; return first;}

  Node<T> * curr = first;
  int count = total/2;
  while (count--)
    {
      curr = curr->next;
    }


  count = total/2;
  first = mergeSort(first, count);

  curr = mergeSort(curr, total-count);

  return Merge(first, count, curr, total-count);
}

template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int lcount, Node<T>* right, int rcount)
{
  Node<T> * h = new Node<T>();
  h->next = NULL;
  Node<T> * tmp = h;

  while (lcount > 0 && rcount > 0)
    {
      if (left->data < right->data)
        {
          tmp->next = left;
          tmp = tmp->next;
          left = left->next;
          --lcount;
        }
      else if (right->data < left->data)
        {
          tmp->next = right;
          tmp = tmp->next;
          right = right->next;
          --rcount;
        }
      else
        {
          tmp->next = left;
          tmp = tmp->next;
          left = left->next;
          --lcount;

          tmp->next = right;
          tmp = tmp->next;
          right = right->next;
          --rcount;
        }
    }

  while (lcount > 0)
    {
      tmp->next = left;
      tmp = tmp->next;
      left = left->next;
      --lcount;
    }

  while (rcount > 0)
    {
      tmp->next = right;
      tmp = tmp->next;
      right = right->next;
      --rcount;
    }

  tmp = h;
  h = h->next;
  delete(tmp);

  return h;
}

int main()
{
  LinkedList<int> l;
  l.addNode(3);
  l.addNode(2);
  l.addNode(6);
  l.addNode(4);
  l.addNode(3);

  l.printList();
  l.reverseList();
  l.printList();

  l.sortList();
  l.printList();

  l.deleteNode(3);
  l.deleteNode(3);
  l.deleteNode(4);

  l.printList();
  l.reverseList();
  l.printList();

  l.sortList();
  l.printList();

  if (l.searchNode(2))
    {
      std::cout << "2 found \n";
    }

  if (!l.searchNode(5))
    {
      std::cout << "5 not found \n";
    }

  return 0;
}


18298
4
задан 4 сентября 2011 в 02:09 Источник Поделиться
Комментарии
1 ответ

#include <iostream>

template <class T>
struct Node
{
T data;
Node * next;
};

template <class T>
class LinkedList
{
public:
LinkedList() : head(NULL), size(0) {};
~LinkedList() { destroyList(); };

Почему вы делаете destroyList отдельный метод? Почему бы не положить его в деструктор?

  bool addNode(T data);
bool deleteNode(T data);
Node<T> * searchNode(T data);
void printList();
void reverseList();
void sortList();
private:
Node<T> * head;
int size;

Я рекомендую некоторые строки между методами сведения и служебные функции.

  void destroyList();
Node<T>* mergeSort(Node<T> * head, int total);
Node<T>* Merge(Node<T>* left, int lcount, Node<T>* right, int rcount);

Я рекомендую выбрать последовательную схему капитализации. Это должно быть слить не сольют.

  void print(Node<T> * tmp);
};

template <class T>
bool LinkedList<T>::addNode(T data)
{
try
{
Node<T> * tmp = new Node<T>();
tmp->data = data;
tmp->next = head;
head = tmp;
++size;
return true;
}
catch(std::exception & ex)
{
return false;
}

Никогда не делай этого. Вы не должны вообще поймать все исключения. Вы должны ловить только те исключения, которые вас интересуют. Преобразование исключение в возвращаемое значение теряет преимущество исключение. Зачем вы добавили вот эту логику исключение?
}

template <class T>
bool LinkedList<T>::deleteNode(T data)
{
Node<T> *curr = head, *prev = NULL;

Я рекомендую вводить целые слова, а не аббревиатуры.

  while (curr)
{
if (curr->data == data) break;

Использовать при(Сигг && Карр->данные != данных)

    prev = curr;
curr = curr->next;
}

if (curr)
{

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

      if (prev)
{
prev->next = curr->next;
}
else
{
head = curr->next;
}
delete(curr);

Скобочки не нужны

      --size;
return true;
}
else
{
return false;
}
}

template <class T>
Node<T> * LinkedList<T>::searchNode(T data)

Вы действительно находят узел, а затем поиск этого.

{
Node<T> * tmp = head;

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

  while (tmp)
{

Я предлагаю

для(узел * ТМП = руководитель; tпл; tпл = ТМП->далее)

Я думаю, что это сделает код более понятным.

      if (tmp->data == data)
{
return tmp;
}
tmp = tmp->next;
}
return NULL;
}

template <class T>
void LinkedList<T>::print(Node<T> * tmp)

Печать немного странная функция для связанного списка класса. Как правило, вы бы кроме внешнего кода, чтобы справиться с этим.

{
bool printNewLine = (tmp) ? true : false;

Использование типа bool printNewLine = боол(ТМП)';

  while (tmp)
{
std::cout << tmp->data << ",";
tmp = tmp->next;
}

if (printNewLine)

А потом делаю это. Я предлагаю оставить копию исходного параметра и тестирования его здесь.
{
с std::соиь <<с std::епси;
}
}

Это функция еще используется?

template <class T>
void LinkedList<T>::printList()
{
Node<T> * tmp = head;
bool printNewLine = (tmp) ? true : false;
while (tmp)
{
std::cout << tmp->data << "|";

|? Ладно, неважно.

      tmp = tmp->next;
}

if (printNewLine)
{
std::cout << std::endl;
}
}

template <class T>
void LinkedList<T>::destroyList()
{
Node<T> * tmp = NULL;
while (head)
{
tmp = head;
head = head->next;
//std::cout << "deleting data " << tmp->data << std::endl;

Не оставляйте мертвого кода в ваш код.

      delete(tmp);
}
}

template <class T>
void LinkedList<T>::reverseList()
{
Node<T> *curr = head, *prev = head, *save = NULL;

while (curr)
{
save = curr->next;

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

      curr->next = prev;
prev = curr;
curr = save;
}

head->next = NULL;
head = prev;
}

//use merge sort
template <class T>
void LinkedList<T>::sortList()
{
head = mergeSort(head, size);
}

template <class T>
Node<T>* LinkedList<T>::mergeSort(Node<T> * first, int total)
{
if (total < 1) { return first; }
if (total < 2) { first->next = NULL; return first;}

Node<T> * curr = first;
int count = total/2;

Добавить пробелы вокруг операторов

  while (count--)

Я предлагаю отсчет через цикл for
{
тек = тек->далее;
}

  count = total/2;

А не делать этот расчет дважды, я предлагаю сохранить оригинальную версию

  first = mergeSort(first, count);

curr = mergeSort(curr, total-count);

return Merge(first, count, curr, total-count);
}

template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int lcount, Node<T>* right, int rcount)
{
Node<T> * h = new Node<T>();
h->next = NULL;
Node<T> * tmp = h;

Создание узла при слиянии кажется странным...

  while (lcount > 0 && rcount > 0)
{
if (left->data < right->data)
{
tmp->next = left;
tmp = tmp->next;

использовать ТМП = левый

          left = left->next;
--lcount;
}
else if (right->data < left->data)
{
tmp->next = right;
tmp = tmp->next;
right = right->next;
--rcount;
}
else
{
tmp->next = left;
tmp = tmp->next;
left = left->next;
--lcount;

tmp->next = right;
tmp = tmp->next;
right = right->next;
--rcount;

Нет необходимости для этого. Просто пусть один из вышеперечисленных случаев справиться с равным.
}
}

  while (lcount > 0)
{
tmp->next = left;
tmp = tmp->next;
left = left->next;
--lcount;

Этот шаблон становится общим. Думать о рефакторинге эта функция или написания функции.

    }

while (rcount > 0)
{
tmp->next = right;
tmp = tmp->next;
right = right->next;
--rcount;
}

tmp = h;
h = h->next;
delete(tmp);

return h;
}

Редактировать: мой вариант слияния

template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int count_left, Node<T>* right, int count_right)
{
Node<T> * head = NULL;
Node<T> ** current = &head;

while (count_left > 0 || count_right > 0)
{
if( count_right == 0 || (count_left > 0 && left->data < right->data))
{
*current = left;
left = left->next;
--count_left;
}
else
{
*current = right;
right = right->next;
--count_right;
}
current = &(*current)->next;
}
return head;
}

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