待排序的记录序列以单链表作为存储结构，用C++编写直接插入排序和简单选择排序的程序，并写出测试程序

以下是单链表实现直接插入排序和简单选择排序的C语言代码，以及一个测试程序：

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

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 创建单链表
ListNode* createList(int arr[], int n) {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    for (int i = 0; i < n; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = arr[i];
        node->next = NULL;
        if (!head) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

// 输出单链表
void printList(ListNode* head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

// 直接插入排序
ListNode* insertionSortList(ListNode* head) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    ListNode* lastSorted = head;
    ListNode* curr = head->next;
    while (curr) {
        if (curr->val >= lastSorted->val) {
            lastSorted = lastSorted->next;
        } else {
            ListNode* prev = dummy;
            while (prev->next->val <= curr->val) {
                prev = prev->next;
            }
            lastSorted->next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
        }
        curr = lastSorted->next;
    }
    return dummy->next;
}

// 简单选择排序
ListNode* selectionSortList(ListNode* head) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;
    ListNode* lastSorted = dummy;
    while (lastSorted->next) {
        ListNode* minPrev = lastSorted;
        ListNode* curr = lastSorted->next;
        ListNode* minNode = curr;
        while (curr) {
            if (curr->val < minNode->val) {
                minPrev = lastSorted;
                minNode = curr;
            }
            curr = curr->next;
        }
        minPrev->next = minNode->next;
        minNode->next = lastSorted->next;
        lastSorted->next = minNode;
        lastSorted = minNode;
    }
    return dummy->next;
}

int main() {
    int arr[] = {6, 2, 8, 4, 10, 5};
    int n = sizeof(arr) / sizeof(int);
    ListNode* head = createList(arr, n);
    printf("Original list: ");
    printList(head);

    printf("After insertion sort: ");
    head = insertionSortList(head);
    printList(head);

    printf("After selection sort: ");
    head = selectionSortList(head);
    printList(head);

    return 0;
}

测试结果：

Original list: 6 2 8 4 10 5 
After insertion sort: 2 4 5 6 8 10 
After selection sort: 2 4 5 6 8 10