用c语言写出一段程序使得已知长度为m的线性表A采用顺序存储结构,请设计一个时间复杂度为O(n)空间复杂度为O(1)的算法,该算法可删除线性表中所有值为item的数据元素。
时间: 2024-10-07 10:07:55 浏览: 50
在C语言中,我们可以设计一个简单的遍历线性表并删除所有等于给定元素的算法。以下是一个示例:
```c
#include <stdio.h>
// 定义线性表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
} Node;
// 删除所有值为item的元素
void deleteItem(Node** head, int item) {
Node *current = *head;
Node *previous = NULL;
// 遍历整个链表
while (current != NULL) {
if (current->data == item) { // 如果当前节点值等于item
if (previous == NULL) { // 如果是第一个节点
*head = current->next; // 更新头指针,跳过第一个节点
} else {
previous->next = current->next; // 其他节点将当前节点指向下一个节点
}
free(current); // 释放当前节点内存
current = previous->next; // 移动到下一个节点继续检查
} else {
previous = current; // 未找到item,则更新前一个节点指针
current = current->next;
}
}
}
// 主函数示例,假设我们有一个链表已经初始化
int main() {
Node* head = ...; // 初始化你的线性表在这里
// 要删除的元素
int item = 5;
deleteItem(&head, item);
return 0;
}
```
这段代码首先定义了一个链表节点结构,然后提供了一个名为`deleteItem`的函数,它接受一个指向头节点的指针和一个整数作为输入。函数通过遍历链表,遇到值为`item`的节点就将其从链表中移除。由于是在原地操作,所以空间复杂度为O(1),时间复杂度为O(n)。
阅读全文