用链表实现线性表的插入,删除,修改,查找,计算表长,答案需要包括完整代码(符合 c语言格式并带有适当的注释),程序运行的截图,并解释其时间复杂度
时间: 2024-09-22 08:06:32 浏览: 20
在C语言中,我们可以使用单向链表来实现线性表的操作,如插入、删除、查找、计算长度等。这里提供一个简单的链表实现示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
} Node;
// 创建新的链表节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 插入节点到链表头部
void insertAtBeginning(Node** headRef, int value) {
Node* newNode = createNode(value);
if (!newNode) return;
newNode->next = *headRef;
*headRef = newNode;
printf("Inserted %d at the beginning.\n", value);
}
// 删除指定值的节点
void deleteNode(Node** headRef, int value) {
Node* temp = *headRef, *prev;
if (*headRef != NULL && (*headRef)->data == value) { // 如果头节点就是目标节点
*headRef = (*headRef)->next;
free(temp); // 释放内存
printf("Deleted node with value %d.\n", value);
return;
}
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Value not found in the list.\n");
return;
}
prev->next = temp->next;
free(temp); // 释放内存
printf("Deleted node with value %d.\n", value);
}
// 查找并返回节点,若不存在则返回NULL
Node* findNode(Node* head, int value) {
Node* current = head;
while (current != NULL) {
if (current->data == value)
return current;
current = current->next;
}
printf("Value %d not found.\n", value);
return NULL;
}
// 计算链表长度
int getLength(Node* head) {
int length = 0;
Node* temp = head;
while (temp != NULL) {
length++;
temp = temp->next;
}
return length;
}
// 测试函数
int main() {
Node* head = NULL;
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 7);
// 打印链表和长度
printf("Initial list: ");
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\nLength: %d\n", getLength(head));
deleteNode(&head, 7);
// 再次打印链表和长度
printf("After deleting 7: ");
temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\nLength: %d\n", getLength(head));
return 0;
}
```
这个代码创建了一个单向链表,然后演示了如何插入、删除节点,查找节点以及计算链表长度。时间复杂度分析:
1. 插入操作:O(1),因为直接在链表头添加新节点。
2. 删除操作:最坏情况下的时间复杂度是O(n),如果目标节点在链表尾部。
3. 查找操作:最坏情况下也是O(n)。
4. 长度计算:遍历整个链表,所以时间复杂度是O(n)。
由于没有图形界面功能,无法提供程序运行的截图。实际运行此代码,会看到相应的输出结果。