已知长度为n的线性表A采用顺序存储结构,请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法可删除线性表中所有值为item的数据元素c语言
时间: 2024-10-15 10:09:20 浏览: 84
在C语言中,我们可以使用遍历的方式来删除顺序存储结构(数组)中所有值为`item`的数据元素。下面是一个简单的示例:
```c
#include <stdio.h>
void deleteItem(int A[], int n, int item) {
int i = 0; // 初始化索引i
// 遍历数组,如果找到item则跳过
while (i < n) {
if (A[i] != item) { // 如果当前元素不是item,则移动到下一个位置并继续检查
A[i] = A[i+1]; // 将非item元素复制到当前位置
} else { // 找到了item,跳过它
n--; // 减少数组长度,因为不需要后面的元素了
}
i++; // 移动到下一个位置
}
// 调整数组大小
A[n] = '\0'; // 添加终止符,因为数组现在可能会变短
}
int main() {
int A[5] = {1, 2, 3, 4, 5}; // 示例数组
int n = sizeof(A) / sizeof(A[0]);
int item = 3;
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", A[i]);
}
deleteItem(A, n, item);
printf("\nArray after deletion of all items %d: ", item);
for (int i = 0; i <= n; i++) { // 注意更新循环条件,因为可能删减了最后一个元素的位置
printf("%d ", A[i]);
}
return 0;
}
```
这个算法的时间复杂度是O(n),因为它需要遍历整个数组一次。空间复杂度是O(1),因为我们只使用了几个额外的变量,而没有分配新的内存。
阅读全文