假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x的元素，要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。用三种c语言算法

假设我们要在一个一维数组（顺序表）中删除所有值等于 `x` 的元素，可以设计三种C语言算法来满足时间复杂度为O(n)和空间复杂度为O(1)的要求：

1. **双指针法**（两重循环）

void deleteElements(int arr[], int n, int x) {
    int i = 0, j = 0;
    while (i < n) {
        if (arr[i] != x) {
            arr[j++] = arr[i];
        }
        i++;
    }
    arr[j] = 0; // 如果数组未到达结尾，需要填充最后一个位置防止越界
}

这个方法通过一个索引 `i` 遍历整个数组，当遇到不等于 `x` 的元素就移到新的位置 `j`。

2. **单链表法**（链表节点操作）

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void deleteElements(Node* head, int x) {
    Node* prev = NULL;
    Node* curr = head;
    while (curr != NULL) {
        if (curr->data != x) {
            if (prev == NULL) {
                head = curr;
            } else {
                prev->next = curr;
            }
            prev = curr;
        }
        curr = curr->next;
    }
    if (prev != NULL) {
        prev->next = NULL; // 结束处可能还有 x 元素，连接上最后一个非 x 节点
    }
}

这里适用于已将输入数据组织成单向链表的情况。

3. **迭代器法**（仅适用于支持随机访问的数据结构，如动态数组）

#include <stdio.h>

// 假设 arr 是动态数组（例如数组），size 是长度
void deleteElements(int arr[], size_t* size, int x) {
    for (size_t i = 0; i < *size; ++i) {
        if (arr[i] != x) {
            memmove(arr + i, arr + i + 1, (*size - i - 1) * sizeof(arr[0]));
        } else {
            --(*size); // 直接减少大小，不需要移动元素
        }
    }
}

注意此方法在原地修改数组，并不创建新数组，所以空间复杂度为O(1)，但需更新`size`指针。