试写一c语言算法，实现正位序输入 n 个数据元素的值，建立带头结点的单链表，要求时间复杂度是线性阶的

在 C 语言中，我们可以使用一个线性结构（如单链表）来存储正序输入的 n 个数据元素。这里有一个简单的算法步骤：

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next; // 指向下一个节点的指针
} Node;

// 创建新节点并插入到链表末尾
Node* insert(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
    if (newNode != NULL) {
        newNode->data = value;
        newNode->next = NULL;
        return newNode;
    } else {
        printf("Memory allocation failed.\n");
        return NULL;
    }
}

// 正序读取并插入链表
void insertInOrder(int n) {
    Node* head = NULL; // 初始化链表头指针为NULL

    for (int i = 0; i < n; i++) {
        int input;
        scanf("%d", &input); // 输入一个数字
        if (i == 0 || input > head->data) { // 如果是第一个元素或输入值大于当前节点
            head = insert(input); // 插入新节点作为头节点
        } else {
            Node* current = head;
            while (current->next != NULL && current->next->data < input) {
                current = current->next;
            }
            current->next = insert(input); // 将输入值插入适当位置
        }
    }
}

// 打印链表
void printList(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    int n;
    printf("Enter the number of elements to be inserted in sorted order: ");
    scanf("%d", &n);

    insertInOrder(n);

    printf("Sorted linked list:\n");
    printList(head); // 打印链表

    return 0;
}

这个算法的时间复杂度是 O(n)，因为我们只遍历了一次输入的数据，并且在链表中插入元素也最多需要遍历一次。当输入数据已经正序排列时，该算法更有效率。