已知长度为n的线性表A采用顺序存储结构,请写出一个时间复杂度为0(n) 的算法,该算法可删除线性表中所有值为item 的数据元素。C语言表示
时间: 2024-10-09 13:04:22 浏览: 38
数据结构课后习题2.doc
5星 · 资源好评率100%
为了删除线性表中所有值为 `item` 的数据元素,我们可以遍历整个数组并进行操作。以下是使用 C 语言的一个简单示例:
```c
#include <stdio.h>
void deleteAll(int arr[], int n, int item) {
int i = 0;
// 遍历数组
for (i = 0; i < n - 1; i++) { // 注意不要遍历到数组末尾,因为我们还在处理当前元素
if (arr[i] != item) {
arr[i + 1] = arr[i]; // 如果不是目标值,将当前元素移到下一个位置
} else {
// 如果找到目标值,跳过它,直接处理下一个元素
while (arr[i] == item && i < n) {
i++; // 跳过连续的目标值
}
}
}
// 最后一个元素可能也是我们要删除的,如果它是目标值
if (arr[n - 1] == item) {
n--; // 减少数组长度,因为最后一个元素已被删除
}
arr[n] = '\0'; // 添加空字符结束字符串,假设数组表示的是一个字符数组
printf("修改后的数组长度为 %d:\n", n);
for (int j = 0; j < n; j++) {
printf("%d ", arr[j]);
}
}
// 测试函数
int main() {
int A[] = {1, 2, 3, 4, 5, 2, 6, 7, 2, 8};
int n = sizeof(A) / sizeof(A[0]);
int item = 2;
deleteAll(A, n, item);
return 0;
}
```
这个算法的时间复杂度是 O(n),因为它需要遍历整个线性表一次。
阅读全文