C语言单链表实现简单选择排序算法

简介

本文将介绍如何使用C语言实现一个单链表，并使用简单选择排序算法对其进行排序。

代码实现

以下是使用单链表实现简单选择排序算法的C代码示例：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 向链表末尾插入节点
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* curr = *head;
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

// 交换两个节点的值
void swap(Node* a, Node* b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

// 遍历链表
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf('%d ', curr->data);
        curr = curr->next;
    }
    printf('
');
}

// 使用简单选择排序算法对链表进行排序
void selectionSort(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        Node* minNode = curr;
        Node* temp = curr->next;
        while (temp != NULL) {
            if (temp->data < minNode->data) {
                minNode = temp;
            }
            temp = temp->next;
        }
        swap(curr, minNode);
        curr = curr->next;
    }
}

int main() {
    Node* head = NULL;
    insertNode(&head, 5);
    insertNode(&head, 2);
    insertNode(&head, 8);
    insertNode(&head, 1);
    insertNode(&head, 6);

    printf('原始链表: ');
    printList(head);

    selectionSort(head);

    printf('排序后链表: ');
    printList(head);

    return 0;
}

运行结果

运行以上代码，输出结果为：

原始链表: 5 2 8 1 6 
排序后链表: 1 2 5 6 8

代码解释

以上代码使用单链表实现了简单选择排序算法。

首先定义了链表节点结构体Node，包含一个整数数据data和一个指向下一个节点的指针next。
然后定义了创建节点createNode、插入节点insertNode、交换节点值swap、遍历链表printList等辅助函数。
selectionSort函数实现了简单选择排序算法，它遍历链表，找到未排序部分的最小节点，并将其与未排序部分的第一个节点交换位置。
在主函数中，首先创建了一个链表，并插入了一些节点。然后打印原始链表，调用selectionSort函数对链表进行排序，最后再次打印排序后的链表。