21xrx.com
2024-12-23 02:03:12 Monday
登录
文章检索 我的文章 写文章
C++链表排序函数
2023-06-23 15:22:40 深夜i     --     --
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()函数，并自定义比较函数，就可以对链表中的数据进行排序。

  
  

评论区

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