设待排序的记录序列用单链表作存储结构，编写直接插入排序的程序

直接插入排序的基本思路是：将待排序的元素一个一个插入到已经排序好的元素中，直到所有元素都被插入完毕。对于单链表来说，我们可以使用指针来实现元素的插入和移动。

以下是单链表直接插入排序的代码实现：

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

// 定义单链表结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 插入节点
void insert(ListNode *head, ListNode *node) {
    node->next = head->next;
    head->next = node;
}

// 遍历链表
void traverse(ListNode *head) {
    ListNode *p = head->next;
    while (p) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

// 直接插入排序
void insertionSort(ListNode *head) {
    ListNode *p = head->next;
    head->next = NULL;
    while (p) {
        ListNode *q = p->next;
        insert(head, p);
        p = q;
    }
}

int main() {
    // 创建链表
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *tail = head;
    int n;
    printf("请输入待排序的元素个数：");
    scanf("%d", &n);
    printf("请输入 %d 个整数：", n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        ListNode *node = (ListNode *)malloc(sizeof(ListNode));
        node->val = x;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }

    // 输出排序前的链表
    printf("排序前的链表：");
    traverse(head);

    // 进行直接插入排序
    insertionSort(head);

    // 输出排序后的链表
    printf("排序后的链表：");
    traverse(head);

    // 释放内存
    ListNode *p = head;
    while (p) {
        ListNode *q = p->next;
        free(p);
        p = q;
    }

    return 0;
}

该程序先创建一个单链表，然后输入待排序的元素，使用 `insertionSort` 函数进行排序，最后输出排序后的结果。在 `insertionSort` 函数中，我们先将链表的头节点的 `next` 指针设为 `NULL`，然后遍历链表，将每个节点插入到已经排序好的节点中。在插入节点时，我们需要使用 `insert` 函数将节点插入到链表中。最后，释放内存并退出程序。