C++双向链表排序 |21xrx.com

C++双向链表排序

2023-06-22 13:39:41 深夜i 22 0

C++ 双向链表排序

C++双向链表是一种高效的数据结构，可以在插入、删除和查询操作中提供快速的响应时间。然而，如果链表中的数据没有经过排序，则可能会在查询操作中造成一定的麻烦。因此，对于大规模的链表应用，一种好的实践是在数据插入时对链表进行排序，这可以在查询操作中显著提高效率。

C++双向链表的排序可以通过多种不同的算法来实现，比如冒泡排序、插入排序、快速排序等。其中，选择一种合适的排序算法主要取决于链表的大小和性能需求。我们在这里选择插入排序算法作为双向链表排序的实现，因为在平均情况下，插入排序的复杂度为O(N^2)，然而，对于已经基本有序的数据，复杂度可以降至O(N)。

下面是C++双向链表排序的示例代码：

#include <iostream>
using namespace std;
class Node {
public:
  int data;
  Node* prev;
  Node* next;
  Node(int d)
    data = d;
    prev = next = nullptr;
  
};
class DoublyLinkedList {
public:
  Node* head;
  DoublyLinkedList() head = nullptr;
  void addNode(int data);
  void display();
  void sortList();
};
void DoublyLinkedList::addNode(int data) {
  Node* newNode = new Node(data);
  if (head == nullptr)
    head = newNode;
  
  else {
    Node* curr = head;
    while (curr->next != nullptr)
      curr = curr->next;
    
    curr->next = newNode;
    newNode->prev = curr;
  }
}
void DoublyLinkedList::display() {
  Node* curr = head;
  while (curr != nullptr)
    cout << curr->data << " ";
    curr = curr->next;
  
  cout << endl;
}
void DoublyLinkedList::sortList() {
  if (head == nullptr)
    return;
  
  Node* curr = head->next;
  while (curr != nullptr) {
    Node* key = curr;
    Node* prev = curr->prev;
    while (prev != nullptr && prev->data > key->data) {
      prev->next = key->next;
      if (key->next != nullptr)
        key->next->prev = prev;
      
      key->prev = prev->prev;
      key->next = prev;
      if (prev->prev != nullptr)
        prev->prev->next = key;
      
      prev->prev = key;
      prev = key->prev;
    }
    curr = curr->next;
  }
}
int main() {
  DoublyLinkedList dll;
  dll.addNode(42);
  dll.addNode(10);
  dll.addNode(88);
  dll.addNode(73);
  dll.addNode(4);
  dll.addNode(16);
  dll.addNode(25);
  dll.display();
  dll.sortList();
  dll.display();
  return 0;
}

在这段代码中，我们首先定义了Node类和DoublyLinkedList类，分别表示双向链表的节点和链表本身。其中，Node类包含了数据及其前向和后向指针，DoublyLinkedList类包含了链表头指针，以及添加、显示和排序链表的方法。

在实现排序时，我们使用了嵌套循环，其中外部循环指向链表中的每个节点，内部循环则向前遍历链表，将当前节点插入到正确的位置。具体实现方法如下：

1.外部循环从链表的第二个节点开始，指向curr指针，它用于向后遍历链表中的每个节点。

2.在内部循环中，我们需要找到当前节点的前一个节点。我们将prev指针初始化为当前节点的前驱节点，然后在prev指针向前遍历链表的过程中，查找合适的插入位置。

3.如果prev指针所指向的节点大于当前节点，那么就需要将当前节点插入到prev节点的前面。为此，我们需要更新prev节点和当前节点之间的连接，以及当前节点和前后指针所指向的节点之间的连接。

4.一旦当前节点被插回到它的原位置后，我们继续外部循环，向后遍历链表中的每个节点，直到链表的最后一个元素。

5.最后，我们在main()函数中，为链表添加节点，并按顺序输出节点的值。然后，我们使用sortList()方法对链表进行排序，再次输出结果。可以看到，链表中的节点已按升序排列。

通过本文的示例代码，我们学到了如何使用C++双向链表对数据进行排序。尽管C++提供了许多排序算法，但在处理大数据集时，建议使用插入排序算法，因为它的均摊复杂度与数据已经缩小的有序集合的大小成正比例，这使得它在大多数情况下都能提供最佳性能。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++中输入不定长度的二维数组

评论区

相似文章