21xrx.com
2024-12-31 19:32:05 Tuesday
登录
文章检索 我的文章 写文章
C++链表的冒泡排序
2023-07-02 03:23:50 深夜i     --     --
C++ 链表 冒泡排序

链表是一种常见的数据结构，它可以用来表示线性序列或者其他数据结构。在实际应用中，我们常常需要对链表进行排序，最常见的排序算法是冒泡排序。C++语言中提供了方便的链表数据结构和库函数，使得链表的冒泡排序变得简单而直观。

链表的冒泡排序算法基本思路是：对于链表中的每一对相邻结点，比较它们的值，如果前一个结点的值大于后一个结点的值，则交换它们。重复这个过程，直到遍历整个链表，再重复进行若干次操作，直到链表有序。

下面给出C++代码实现：



#include <iostream>


using namespace std;


struct Node { // 定义链表结点类型


  int val;


  Node* next;


};


Node* bubbleSort(Node* head, int len) { // 链表冒泡排序


  if (len <= 1) return head; // 单结点或空链表不需排序


  for (int i = 0; i < len - 1; i++) { // 外循环控制迭代次数


    bool swapped = false; // 用于优化：如果这次迭代没有发生交换，则说明链表已经有序


    Node* prev = nullptr; // 记录前一个结点，用于交换


    for (Node* cur = head; cur->next != nullptr; ) { // 内循环遍历链表结点


      Node* nxt = cur->next; // 记录下一个结点


      if (cur->val > nxt->val) { // 如果需要交换


        swapped = true;


        if (prev != nullptr) prev->next = nxt; // 如果不是头结点，则需要修改前一个结点的指针


        else head = nxt; // 如果是头结点，则修改头指针


        cur->next = nxt->next; // 修改当前结点的指针


        nxt->next = cur;


        prev = nxt; // 修改前一个结点


      }


      else 则继续向下遍历


        prev = cur;


        cur = cur->next;


      


    }


    if (!swapped) break; // 如果本次迭代没有交换，则说明链表已经有序，可以结束了


  }


  return head;


}


int main() {


  Node nodes[] = {3,nullptr,nullptr,2,5}; // 测试链表数据


  int len = sizeof(nodes)/sizeof(Node);


  for (int i = 0; i < len-1; i++) { // 建立链表


    nodes[i].next = &nodes[i+1];


  }


  nodes[len-1].next = nullptr;


  Node* head = bubbleSort(&nodes[0], len); // 调用排序函数


  for (Node* cur = head; cur != nullptr; cur = cur->next) // 输出排序结果


    cout << cur->val << " ";


  


  cout << endl;


  return 0;


}

上述程序中，我们先定义了链表结点类型Node，包含一个整型val和一个指向下一个结点的指针next。然后我们定义了一个用于排序的bubbleSort函数，该函数接受链表头结点指针head和链表长度len作为参数，返回排序后的链表头结点指针。

在bubbleSort函数中，我们使用双重循环实现冒泡排序，外循环控制迭代次数，内循环遍历链表结点。在内循环中，我们使用指针变量cur和nxt记录当前结点和下一个结点，判断它们的值大小，如果需要交换则修改链表指针。外循环结束后，直接返回链表头结点指针head即可。

在主函数中，我们首先定义了一个链表数据nodes[]，然后依次将每个结点的next指针指向下一个结点或者nullptr，建立了一个长度为5的链表。接着调用bubbleSort函数，对链表进行排序。最后输出排序后的链表。

总之，链表的冒泡排序算法虽然简单，但是应用广泛。C++语言的链表数据结构和库函数，让链表的冒泡排序变得非常容易和方便。

  
  

评论区

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