C语言实现单链表排序算法：冒泡排序

C语言实现单链表排序：冒泡排序算法

本文提供了一个使用 C 语言实现的单链表排序算法示例。该算法采用冒泡排序法对带头节点的单链表进行排序，并提供详细的代码解释。

代码实现c#include <stdio.h>#include <stdlib.h>

typedef struct __Node { int value; struct __Node* next;} Node;

Node* sort_list(Node* head) { // 如果链表为空或只有一个节点，则不需要排序，直接返回 if (head == NULL || head->next == NULL) { return head; }

// 使用冒泡排序对链表进行排序    int swapped;    Node* ptr1;    Node* lptr = NULL;

do {        swapped = 0;        ptr1 = head;

    while (ptr1->next != lptr) {            if (ptr1->value > ptr1->next->value) {                // 交换节点的值                int temp = ptr1->value;                ptr1->value = ptr1->next->value;                ptr1->next->value = temp;

            swapped = 1;            }            ptr1 = ptr1->next;        }        lptr = ptr1;    } while (swapped);

return head;}

void destroy_list(Node* head) { Node* current = head; Node* temp;

while (current != NULL) {        temp = current;        current = current->next;        free(temp);    }}

int main() { // 创建一个示例链表 Node* head = (Node*)malloc(sizeof(Node)); head->next = NULL;

Node* node1 = (Node*)malloc(sizeof(Node));    node1->value = 3;    node1->next = NULL;    head->next = node1;

Node* node2 = (Node*)malloc(sizeof(Node));    node2->value = 1;    node2->next = NULL;    node1->next = node2;

Node* node3 = (Node*)malloc(sizeof(Node));    node3->value = 2;    node3->next = NULL;    node2->next = node3;

// 打印排序前的链表数据    Node* current = head->next;    printf('排序前的链表：');    while (current != NULL) {        printf('%d ', current->value);        current = current->next;    }    printf('

');

// 对链表进行排序    head->next = sort_list(head->next);

// 打印排序后的链表数据    current = head->next;    printf('排序后的链表：');    while (current != NULL) {        printf('%d ', current->value);        current = current->next;    }    printf('

');

// 销毁链表    destroy_list(head);

return 0;}

代码解释

节点结构体定义: - typedef struct __Node { ... } Node; 定义了链表节点的数据结构，包含一个整型变量 value 和一个指向下一个节点的指针 next。
排序函数 sort_list: - 接收链表头节点指针 head 作为参数。 - 如果链表为空或只有一个节点，直接返回 head。 - 使用冒泡排序算法对链表进行排序： - 使用 swapped 变量标记是否发生交换，初始值为 0。 - 使用 ptr1 指针遍历链表，lptr 指针标记已排序的最后一个节点。 - 在每一次循环中，比较相邻节点的值，如果前一个节点的值大于后一个节点的值，则交换它们的值，并将 swapped 变量设置为 1。 - 循环结束后，如果 swapped 变量的值为 1，则说明发生了交换，需要继续循环；否则说明链表已经有序，结束循环。
销毁链表函数 destroy_list: - 接收链表头节点指针 head 作为参数。 - 遍历链表，逐个释放节点占用的内存空间。
主函数 main: - 创建一个示例链表，并初始化节点的值。 - 打印排序前的链表数据。 - 调用 sort_list 函数对链表进行排序。 - 打印排序后的链表数据。 - 调用 destroy_list 函数销毁链表，释放内存空间。

总结

本文提供了一个使用 C 语言实现单链表排序的示例代码，并对代码进行了详细的解释。该代码采用了冒泡排序算法，并包含了创建链表、排序链表和销毁链表的完整过程，可以作为学习和理解单链表排序算法的参考。