C++单链表插入排序：实现降序和升序排列

C++单链表插入排序：实现降序和升序排列

本文介绍如何使用 C++ 实现从键盘输入 5 个无序整数，并将它们分别插入到两个单链表 a 和 b 中，其中单链表 a 的数据按降序排列，单链表 b 的数据按升序排列。

代码实现

以下是完整的 C++ 代码：cpp#include using namespace std;

// 定义单链表节点struct ListNode { int val; ListNode* next;

ListNode(int value) : val(value), next(nullptr) {}};

// 插入节点到单链表 a，并保持从大到小排序ListNode* insertNodeA(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (head == nullptr || value >= head->val) { newNode->next = head; return newNode; }

ListNode* cur = head;    while (cur->next != nullptr && cur->next->val > value) {        cur = cur->next;    }

newNode->next = cur->next;    cur->next = newNode;    return head;}

// 插入节点到单链表 b，并保持从小到大排序ListNode* insertNodeB(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (head == nullptr || value < head->val) { newNode->next = head; return newNode; }

ListNode* cur = head;    while (cur->next != nullptr && cur->next->val < value) {        cur = cur->next;    }

newNode->next = cur->next;    cur->next = newNode;    return head;}

// 打印单链表void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << endl;}

int main() { ListNode* a = nullptr; ListNode* b = nullptr;

cout << '请输入 5 个无序整数，用空格分隔：' << endl;    for (int i = 0; i < 5; i++) {        int num;        cin >> num;        a = insertNodeA(a, num);        b = insertNodeB(b, num);    }

cout << '排序后的单链表 a 为：';    printList(a);

cout << '排序后的单链表 b 为：';    printList(b);

// 释放单链表内存    ListNode* curA = a;    while (curA != nullptr) {        ListNode* temp = curA;        curA = curA->next;        delete temp;    }

ListNode* curB = b;    while (curB != nullptr) {        ListNode* temp = curB;        curB = curB->next;        delete temp;    }

return 0;}

代码解析

1. 定义单链表节点: 代码首先定义了一个名为 ListNode 的结构体，表示单链表中的节点。每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。

2. 插入节点并排序: 代码中定义了 insertNodeA 和 insertNodeB 两个函数，分别用于将节点插入到单链表 a 和 b 中，并保证插入后链表的有序性。 - insertNodeA 函数将节点按降序插入到单链表 a 中。 - insertNodeB 函数将节点按升序插入到单链表 b 中。

3. 打印单链表: printList 函数用于遍历并打印单链表中的所有节点值。

4. 主函数: main 函数是程序的入口点，它首先创建两个空的单链表 a 和 b。然后，程序提示用户输入 5 个无序整数，并将它们分别插入到单链表 a 和 b 中。最后，程序调用 printList 函数打印排序后的两个单链表，并释放内存。

总结

本文介绍了如何使用 C++ 实现单链表的插入排序，并分别实现了降序和升序两种排序方式。代码中包含了详细的注释，希望能够帮助你理解单链表的插入排序算法。