对链表使用插入排序的C语言实现示例

简介: 对链表使用插入排序的C语言实现示例
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};
// 插入排序函数
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode dummy;
    dummy.next = NULL;
    struct ListNode* current = head;
    while (current != NULL) {
        struct ListNode* prev = &dummy;
        struct ListNode* nextNode = current->next;
        // 在已排序的链表中找到插入位置
        while (prev->next != NULL && prev->next->val < current->val) {
            prev = prev->next;
        }
        // 插入当前节点
        current->next = prev->next;
        prev->next = current;
        // 继续处理下一个节点
        current = nextNode;
    }
    return dummy.next;
}
// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}
// 打印链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}
// 释放链表节点的内存
void freeList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        struct ListNode* temp = current;
        current = current->next;
        free(temp);
    }
}
int main() {
    // 创建示例链表: 4 -> 2 -> 1 -> 3
    struct ListNode* head = createNode(4);
    head->next = createNode(2);
    head->next->next = createNode(1);
    head->next->next->next = createNode(3);
    printf("Original list: ");
    printList(head);
    // 对链表进行插入排序
    head = insertionSortList(head);
    printf("Sorted list: ");
    printList(head);
    // 释放链表节点的内存
    freeList(head);
    return 0;
}

在这个示例中,我们定义了 insertionSortList 函数用于对链表进行插入排序。然后,在 main 函数中创建了示例链表,调用 insertionSortList 函数进行排序,并打印结果。最后,释放了链表节点的内存。

插入排序的时间复杂度为O(n^2),在某些情况下比归并排序的O(nlogn)更有效。

  1. 特殊情况处理: 首先,我们检查链表是否为空或者只有一个节点。如果是这样,那么链表已经是有序的,不需要进行排序,直接返回原链表。
  2. 创建一个哑节点: 我们创建一个名为 dummy 的哑节点,它的作用是作为新链表的头部。这样做的好处是,哑节点可以简化插入操作的边界情况处理,同时也可以减少对头节点是否变化的判断。
  3. 遍历链表: 我们使用一个指针 current 来遍历原始链表。在每次迭代中,我们将 current 指向的节点从原始链表中取下,准备将其插入到新链表中。
  4. 在新链表中找到插入位置: 我们需要在新链表中找到正确的插入位置,使得新节点能够保持有序。为了做到这一点,我们从哑节点开始,沿着新链表向后遍历,直到找到插入位置或者到达链表末尾。
  5. 插入节点: 一旦找到了正确的插入位置,我们就将当前节点插入到新链表中。具体操作是,将当前节点的 next 指针指向插入位置节点的下一个节点,然后将插入位置节点的 next 指针指向当前节点。这样就成功地将当前节点插入到了新链表中。
  6. 继续遍历: 接着,我们继续遍历原始链表,重复上述步骤,直到所有节点都被插入到了新链表中。
  7. 返回结果: 最后,我们返回新链表的头部,即哑节点的下一个节点,作为排序后的链表。

在代码中,我们用 struct ListNode* prev 来记录当前节点在新链表中的插入位置的前一个节点,这样可以更方便地进行插入操作。另外,我们使用了一个 nextNode 指针来保存当前节点的下一个节点,以便在插入操作后继续遍历原始链表。

 

相关文章
|
4月前
|
存储 C语言
【C语言】基础刷题训练4(含全面分析和代码改进示例)
【C语言】基础刷题训练4(含全面分析和代码改进示例)
|
20天前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
160 6
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
86 4
|
2月前
|
存储 缓存 C语言
C语言:链表和数组有什么区别
C语言中,链表和数组是两种常用的数据结构。数组是一种线性结构,元素在内存中连续存储,通过下标访问,适合随机访问且大小固定的情况。链表由一系列不连续的节点组成,每个节点存储数据和指向下一个节点的指针,适用于频繁插入和删除操作的场景,链表的大小可以动态变化。
|
2月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装,包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
29 0
|
2月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装,包括节点的创建、链表的初始化、数据的插入和删除,以及链表的打印等功能。
21 1
|
2月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码,包括创建链表、插入、删除和打印等基本操作。
35 1
|
2月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法,包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除,以及链表的打印等功能。文章通过具体的代码示例,展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除,以及如何清空和销毁链表。
47 0
单链表之无头链表(C语言版)
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
60 0