代码之家 › 专栏 › 技术社区 › ABC

单个链接列表,存在节点插入最低到最高节点值的问题

linked-list data-structures c++

ABC · 技术社区 · 7 年前

我试图在学习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

0 回复 | 直到 7 年前

Bob__ 7 年前

我从你问题中链接的教程中的代码开始,做了一些修改。请注意,这并不是更“现代”的实现方法,但它可能是理解一些相关机制的起点。

#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;
}

它是可测试的 here ,输出值

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

Vuwox 7 年前

这是没有测试,但我认为它应该工作。

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; 
    }
}