ZBLOG

链表头插实现排序

在链表中使用头插法进行排序的基本思路是逐个将元素插入到已排序的部分,始终保持链表的有序状态。以下是一个简单的示例,展示了如何实现这一过程。

我们以单链表为例,并使用 C++ 语言进行实现。下面是具体步骤和代码:

  1. 定义节点结构:定义一个链表节点的结构体。
  2. 创建插入函数:实现头插法插入节点。
  3. 排序函数:逐步将未排序的节点插入到已排序链表中的适当位置。

以下是代码示例:

  1. #include <iostream>
  2. struct Node {
  3. int data;
  4. Node* next;
  5. Node(int val) : data(val), next(nullptr) {}
  6. };
  7. class LinkedList {
  8. public:
  9. Node* head;
  10. LinkedList() : head(nullptr) {}
  11. // 头插法
  12. void insertAtHead(int val) {
  13. Node* newNode = new Node(val);
  14. newNode->next = head;
  15. head = newNode;
  16. }
  17. // 排序函数(使用插入排序)
  18. void sortedInsert(Node* newNode) {
  19. if (head == nullptr || head->data >= newNode->data) {
  20. newNode->next = head;
  21. head = newNode;
  22. } else {
  23. Node* current = head;
  24. while (current->next != nullptr && current->next->data < newNode->data) {
  25. current = current->next;
  26. }
  27. newNode->next = current->next;
  28. current->next = newNode;
  29. }
  30. }
  31. // 排序整个链表
  32. void sort() {
  33. Node* sorted = nullptr; // 新的已排序链表
  34. Node* current = head;
  35. while (current != nullptr) {
  36. Node* nextNode = current->next; // 保存下一个要处理的节点
  37. sortedInsert(current); // 插入到新的已排序链表中
  38. current = nextNode; // 移动到下一个节点
  39. }
  40. head = sorted; // 更新原始头指针为新排好序的列表头
  41. }
  42. // 打印链表
  43. void printList() const {
  44. Node* temp = head;
  45. while (temp != nullptr) {
  46. std::cout << temp->data << " -> ";
  47. temp = temp->next;
  48. }
  49. std::cout << "nullptr" << std::endl;
  50. }
  51. };
  52. int main() {
  53. LinkedList list;
  54. list.insertAtHead(5);
  55. list.insertAtHead(3);
  56. list.insertAtHead(8);
  57. list.insertAtHead(1);
  58. std::cout << "Original List: ";
  59. list.printList();
  60. list.sort();
  61. std::cout << "Sorted List: ";
  62. list.printList();
  63. return 0;
  64. }

说明:

  1. insertAtHead 函数用于在链表头部插入新节点。
  2. sortedInsert 函数将当前节点按照大小顺序插入到已排序部分。
  3. sort 函数迭代处理原始链表,将每个节点通过 sortedInsert 插入到新的已排好序的链接中。

使用方法:

你可以在 main 函数中测试上述代码,通过调用不同的数据进行测试。在这个示例中,我们先创建一些无序数据,然后对其进行头插法排序,并打印结果。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=18879

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?