C++链表排序函数 |21xrx.com

C++链表排序函数

2023-06-23 15:22:40 深夜i 25 0

C++ 链表排序函数

C++是一种面向对象、高效、通用的编程语言，它在实际的软件开发中得到了广泛的应用。在C++中，链表是一种非常常见的数据结构，它被用来存储一系列的数据节点。

如果我们需要对链表中的数据进行排序，该怎么办呢？其实，C++已经提供了对链表进行排序的库函数std::sort()，我们只需调用这个函数即可。

std::sort()函数是C++ STL（Standard Template Library）提供的排序函数。它可以对任何支持比较操作的类型进行排序，包括数组、向量（vector）、链表等各种容器。

在使用std::sort()函数对链表排序时，我们需要注意以下几点：

1.需要包含头文件algorithm和头文件functional，因为std::sort()函数需要使用比较操作。比较操作函数是由std::less<>模板类定义的，默认情况下使用std::less<>。

2.需要自定义比较函数，用于比较链表节点。比较函数必须返回true或false，以表明两个节点的大小关系。

3.需要遍历链表，通过std::sort()函数对链表节点进行排序。由于链表不支持随机访问，因此我们需要定义一个函数用于获取链表中指定位置的节点指针。

下面是一个简单的C++链表排序程序代码：

#include <iostream>
#include <algorithm>
#include <functional>
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
  ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next)
      slow = slow->next;
      fast = fast->next->next;
    
    ListNode *mid = slow->next;
    slow->next = NULL;
    ListNode *left = sortList(head);
    ListNode *right = sortList(mid);
    return merge(left, right);
  }
  ListNode* merge(ListNode *l1, ListNode *l2) {
    ListNode *dummy = new ListNode(-1);
    ListNode *p = dummy;
    while (l1 && l2) {
      if (l1->val < l2->val)
        p->next = l1;
        l1 = l1->next;
       else
        p->next = l2;
        l2 = l2->next;
      
      p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return dummy->next;
  }
};
int main()
{
  ListNode* head = new ListNode(3);
  ListNode* node1 = new ListNode(7);
  ListNode* node2 = new ListNode(2);
  ListNode* node3 = new ListNode(5);
  ListNode* node4 = new ListNode(4);
  ListNode* node5 = new ListNode(6);
  head->next = node1;
  node1->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = node5;
  node5->next = NULL;
  Solution solution;
  ListNode* sorted_list = solution.sortList(head);
  while (sorted_list)
    std::cout << sorted_list->val << " ";
    sorted_list = sorted_list->next;
  
  return 0;
}

以上程序使用了归并排序算法来对链表进行排序。通过递归调用sortList()函数将链表分成两个部分，然后使用merge()函数对两个部分进行合并。这样，我们就可以对链表中的数据进行排序了。

总结起来，C++提供了丰富的库函数来支持链表排序操作。我们只需使用std::sort()函数，并自定义比较函数，就可以对链表中的数据进行排序。

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

下一篇: C++实现数组元素的升序排列输出

评论区

相似文章