Единый связанный список, проблема с вставкой узла от самого низкого до самого высокого значения узла - PullRequest
Новая
       10

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

2 голосов
/ 20 июня 2019

Я пытаюсь создать связанный список при изучении языка C ++ и реализовать функцию вставки узла от низшего к высшему.Я следовал некоторым учебникам в Интернете и учебникам.

У меня есть структура для настройки узла связанного списка следующим образом: 

struct Node {
 private:
  int _data;
  Node *_next = nullptr;
 public:
  Node () : _data ((int) (NULL)), _next (nullptr) { /* */ };
  explicit Node (int &value) : _data (*&value), _next (nullptr) { /* */ };
  friend class LL;
};

Мой класс LL: 

class LL {
 private:
  Node *first;
 public:
  LL () : first (nullptr)
  { /* */ };
  void PrintList ();
  void Push_front (int x);
  void Push_back (int x);
  void Delete (int x);
  void Clear ();
  void Reverse ();
  void LTH(int x);
};

Тогда моя функция класса от низшего к наибольшему:

void LL::LTH(int x)
{
  Node *current = this->first;
  Node *newNode = new Node (x);
  if (this->first == NULL || (current->_data) >= newNode->_data)
    {
      newNode->_next = this->first;
      this->first  = new Node (x);
    }
  else
    {
      current = this->first;
      while (current->_next!=NULL &&
             current->_next->_data < newNode->_data)
        {
          current = current->_next;
        }
      newNode->_next = current->_next;
      current->_next = new Node (x);
    }
}

Мой LL: PrintList () 

void LL::PrintList ()
{

  if (this->first == nullptr)
    {
      std::cout << "List is empty.\n";
      return;
    }

  Node *current = this->first;
  while (current != nullptr)
    {
      std::cout << current->_data << " ";
      current = current->_next;
    }
  std::cout << std::endl;
}

Мой основной 

LL list;
// Changed to for-loop, original is reading binary data random integers
for (int i = 0; i < 20; i++)
  {
    list.LTH(i);
  }

list.PrintList ();

Затем выводится от низшего к высшему, но пропускается через некоторые узлы: 

// Linked-List Nodes
41, 34, 74, 87, 33, 25, 69, 75, 85, 30, 79, 61, 38, 49, 73, 64, 57, 95, 61, 86

// Output: LL:LTH() (Lowest -> Highest)
25, 30, 38, 49, 57, 61, 86

// It's Missing (XX)
XX, XX, XX, XX, XX, 25, XX, XX, XX, 30, XX, 61, 38, 49, XX, XX, 57, XX, XX, 86

Ответы [ 2 ]

2 голосов
/ 20 июня 2019

Я начал с кода, приведенного в учебном руководстве, связанном с вашим вопросом, и внес некоторые изменения. Обратите внимание, что это не более «современный» способ реализации этого, но он может стать отправной точкой для понимания некоторых задействованных механизмов. 

#include <iostream>
#include <initializer_list>

class LinkedList;

class ListNode
{
    int data_ = 0;
    ListNode *next_ = nullptr;
public:
    ListNode() = default;
    ListNode(int a)
        : data_(a) {};
    // I added this constructor, it should ease the insertions
    ListNode(int a, ListNode *n)
        : data_(a), next_(n) {};

    friend class LinkedList;
};

class LinkedList{
private:
    ListNode *first_ = nullptr;
public:
    LinkedList() = default;
    // I didn't want to write down your example as a bunch of list.add(42)...
    LinkedList(std::initializer_list<int> lst)
    {
        for (auto i : lst)
            add(i);   
    }
    // Just to make the code more readable
    bool is_empty() const noexcept
    {
        return first_ == nullptr;
    }
    // Only a small set of function are implemented
    void add(int a);
    void print();
    void clear();
    // The tutorial didn't implement a destructor, but you should study about RAII
    ~LinkedList()
    {
        clear();
    }
};

int main()
{
    LinkedList a {
        41, 34, 74, 87, 33, 25, 69, 75, 85, 30, 79, 61, 38, 49, 73, 64, 57, 95, 61, 86
    };

    a.print();
}

void LinkedList::add(int a)
{
    if (is_empty())
    {
        first_ = new ListNode(a);
    }
    else if (first_->data_ >= a)
    {
        first_ = new ListNode(a, first_);   
    }
    else
    {
        ListNode *current = first_;
        while ( current->next_  &&  current->next_->data_ < a )
        {
            current = current->next_;
        }
        current->next_ = new ListNode(a, current->next_);
    }
}

void LinkedList::print()
{
    if (is_empty())
    {
        std::cout << "List is empty.\n";
    }
    else
    {
        std::cout << first_->data_;
        for ( ListNode *current = first_->next_; current != nullptr; current = current->next_)
        {
            std::cout << ", " << current->data_;
        }
        std::cout << '\n';
    }
}

void LinkedList::clear()
{
    for (ListNode *current = first_, *next; current; current = next)
    {
        next = current->next_;
        delete current;
    }
    first_ = nullptr;
}

Это тестируемое здесь , вывод beeing 

25, 30, 33, 34, 38, 41, 49, 57, 61, 61, 64, 69, 73, 74, 75, 79, 85, 86, 87, 95
1 голос
/ 20 июня 2019

Это не проверено, но, по-моему, должно работать. 

void LL::LTH(int x)
{
    Node* newNode = new Node (x);
    Node* lowest = this->first;

    // if smaller than the first one, add it to the beginning.
    if(lowest->_data > newNode->_data) {
        newNode->_next = lowest;
        this->first = newNode;        
    } else {  
        // Loop until at the right position.
        lowest = lowest->_next;
        while (lowest->_next!=NULL && lowest->_data < newNode->_data) {
            lowest = lowest->_next;
        }

        // If not on last, ensure to keep track of the next.
        if(lowest->_next != NULL) {
          newNode->_next = lowest->_next;                   
        }

        // insert at the current position.
        lowest->_next = newNode; 
    }
}
...