用C语言试写一程序，生成一有序线性表，并将X插入到当中的适当位置上，以保持该表的有序性， 测试数据:生成List(0,1,...,499,501,...999,1000)插入500,顺序表、链表都实现，计算其时间

在C语言中，我们通常可以使用数组（顺序表）或链表（动态存储）来实现这个功能。这里分别给出两个示例：

**顺序表（数组实现）：**

#include <stdio.h>

#define MAX_SIZE 1000

void insertIntoSorted(int arr[], int n, int x) {
    if (n >= MAX_SIZE)
        return; // 如果超过最大容量，无法插入

    int i;
    for (i = 0; i < n && x > arr[i]; i++) { // 找到合适的位置
        arr[i] = x; // 插入元素并后移其他元素
    }
    arr[i] = x; // 最后一个位置直接插入
}

int main() {
    int list[MAX_SIZE];
    int n = sizeof(list) / sizeof(list[0]);
    int x = 500;

    // 初始化列表
    for (int i = 0; i <= n / 2; i++)
        list[i] = i * 2;
    for (int i = n / 2 + 1; i < n; i++)
        list[i] = (i - n / 2) * 2 + 1;

    insertIntoSorted(list, n, x);

    printf("Sorted array after inserting %d:\n", x);
    for (int i = 0; i < n; i++)
        printf("%d ", list[i]);

    return 0;
}

**链表（链接节点实现）：**

#include <stdio.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;

void insertAtSortedPosition(Node** head, int x) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;

    if (*head == NULL || x <= (*head)->data) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL && current->next->data < x) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

int main() {
    Node* sortedList = NULL;
    // ... (类似上面的初始化链表过程)

    insertAtSortedPosition(&sortedList, 500);

    // ... (打印链表内容)

    return 0;
}

对于这两个例子，时间复杂度分析：
- 对于顺序表，如果x正好位于数组中间，插入操作需要移动一半元素，因此时间复杂度为O(n)，其中n是数组长度。
- 对于链表，最好的情况是找到正确的位置立即插入，最坏的情况是x位于链表末尾，此时需要遍历整个链表，所以时间复杂度为O(n)。

实际运行的时间取决于具体的硬件环境和优化程度。为了计算插入操作的确切时间，你需要运行上述代码并在实际环境中测量，这通常涉及到操作系统层面的细节和CPU定时等功能。