使用C语言编写一个程序,在这个程序中完成如下功能: (1)建立顺序表。 (2)在顺序表上实现插入、删除和查找操作。 (3)实现遍历输出顺序表中所有元素。 (3)实现在有序顺序表中删除其中重复的元素,要求删除有序顺序表中重复元素的操作算法时间复杂度为O (n).
时间: 2024-09-25 14:08:50 浏览: 49
在C语言中,我们可以使用结构体和指针来创建顺序表并实现所需的功能。这里是一个简单的示例,我们将定义一个`Node`结构体表示列表节点,并提供相应的插入、删除、查找和去重函数:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义顺序表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指向下一个节点的指针
} Node;
// 初始化顺序表
Node* createList() {
Node* head = NULL;
return head;
}
// 插入元素
void insert(Node** head, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return;
}
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
// 查找元素
int search(Node* head, int value) {
Node* current = head;
while (current != NULL) {
if (current->data == value)
return 1; // 找到元素,返回1
current = current->next;
}
return 0; // 没找到元素,返回0
}
// 删除元素
void deleteElement(Node** head, int value) {
Node* temp = *head, *prev = NULL;
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return; // 没有找到值
prev->next = temp->next;
free(temp);
}
// 遍历顺序表
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 去除重复元素(保持有序)
void removeDuplicates(Node** head) {
if (*head == NULL || (*head)->next == NULL)
return;
Node* current = *head, *temp = NULL;
while (current != NULL) {
temp = current->next;
while (temp != NULL && temp->data <= current->data) { // 避免提前结束循环
if (temp->data == current->data) {
Node* toFree = temp;
temp = temp->next;
free(toFree);
} else {
temp = temp->next;
}
}
current->next = temp;
current = current->next;
}
}
int main() {
Node* list = createList();
// 插入元素
insert(&list, 5);
insert(&list, 7);
insert(&list, 10);
insert(&list, 5); // 重复元素
insert(&list, 8);
// 输出原序列
printf("Original List:\n");
printList(list);
// 删除重复元素
removeDuplicates(&list);
// 输出去重后的序列
printf("\nList with duplicates removed:\n");
printList(list);
// 查找元素
int found = search(list, 10);
if (found)
printf("Found 10 in the list.\n");
else
printf("Did not find 10 in the list.\n");
return 0;
}
```
请注意,这个示例只是一个基础的演示,实际应用中需要考虑更多的边界条件和错误处理。
阅读全文