C++链表的冒泡排序 |21xrx.com

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++语言的链表数据结构和库函数，让链表的冒泡排序变得非常容易和方便。

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

下一篇: 如何在Visual C++中新建C++文件？

评论区

()

相似文章