Изменения однонаправленного списка таким образом, что все четные числа появляются перед нечетных чисел


Я хочу улучшить этот код с использованием STL или лучше логики. Я не написал код для функции удаления или copy constructor или move constructor. Моя цель научиться обмен четных и нечетных элементов.

#include <iostream>
#include <utility>
#include <cassert>

class LinkedList
{
  struct Node
  {
    int data;
    Node * next = nullptr;
    Node(int value)   : data(std::move(value)), next(nullptr) {}
  };
  Node *head;

public:
  LinkedList() : head(nullptr) {}
  ~LinkedList()
  {
    Node *tmp = nullptr;
    while (head)
    {
      tmp = head;
      head = head->next;
      delete tmp;
    }
    head = nullptr;
  }

  void insert(int);
  void exchangeEvenOdd();
  void printList() const;

private:
  static void advance(Node*& node)
  {
    assert (node != nullptr);
    node = node->next;
  }

  Node* getLastNode()
  {
    Node *node = head;
    while (node->next != nullptr)
           node = node->next;

    return node;
  }

  bool isOdd(int num)
  {
    if (num % 2 != 0)
        return true;
    else
        return false;
  }
};

void LinkedList::insert(int value)
{
 Node *node = new Node(std::move(value));
 Node *tmp = head;
 if (tmp == nullptr)
 {
   head = node;
 }
 else
 {
   tmp = getLastNode();
   tmp->next = node;
 }
}

void LinkedList::exchangeEvenOdd()
{
  Node *node = nullptr;
  Node *lastNodeToTest = getLastNode();
  Node *tail = lastNodeToTest;

  while (isOdd(head->data) == true)
  {
    node = head;
    advance(head);
    tail->next = node;
    advance(tail);
  }

  Node *tmp = head;
  Node *curr = head;

  while (tmp->next != lastNodeToTest)
  {
    if (isOdd(curr->next->data) == true)
    {
      node = curr->next;
      curr->next = node->next;
      tail->next = node;
      advance(tail);
    }
    else
    {
      //advance "curr" and "tmp" only when next node to it is even
      advance(curr);
      advance(tmp);
    }
  }

  if (isOdd(curr->next->data) == true && tmp->next == lastNodeToTest)
  {
    node = lastNodeToTest;
    curr->next = lastNodeToTest->next;
    tail->next = lastNodeToTest;
    advance(tail);
  }
  tail->next = nullptr;
  lastNodeToTest = nullptr;
  node = nullptr;
}

void LinkedList::printList() const
{
  if (head == nullptr)
  {
    std::cout << "Empty List \n";
    return;
  }

  Node *node = head;

  while (node != nullptr)
  {
    std::cout << node->data << " ";
    advance(node);
  }

  std::cout << "\n";
}

int main()
{
  LinkedList ll1;
  ll1.insert(1);
  ll1.insert(2);
  ll1.insert(3);
  ll1.insert(4);
  ll1.insert(5);
  ll1.insert(6);
  ll1.insert(7);
  std::cout << "Original List : ";
  ll1.printList();

  ll1.exchangeEvenOdd();
  std::cout << "New List : ";
  ll1.printList();
}


342
0
задан 7 февраля 2018 в 02:02 Источник Поделиться
Комментарии
1 ответ

Есть две разные вещи в коде: реализация односвязного списка, и алгоритм, чтобы сделать даже цифры появляются перед нечетных чисел в списке.

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

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

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
first = std::find_if_not(first, last, p);
if (first == last) return first;

for(ForwardIt i = std::next(first); i != last; ++i){
if(p(*i)){
std::iter_swap(i, first);
++first;
}
}
return first;
}

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

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

Быстрый и грязный способ заключается в реализации алгоритма непосредственно на верхней части списка узлов, учитывая, что они обеспечивают необходимую функциональность через data и next.

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

4
ответ дан 7 февраля 2018 в 03:02 Источник Поделиться