21xrx.com
2024-11-08 22:29:19 Friday
登录
文章检索 我的文章 写文章
C++双向链表排序
2023-06-22 13:39:41 深夜i     --     --
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++提供了许多排序算法，但在处理大数据集时，建议使用插入排序算法，因为它的均摊复杂度与数据已经缩小的有序集合的大小成正比例，这使得它在大多数情况下都能提供最佳性能。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复