链表支持两种操作指令。 插入n:向链表中添加一个整数n。如果链表中已经存在n,则它什么也不做。指令 格式是一个i后跟一个空格和一个整数n。 删除n:从链表中删除一个整数n。如果链表中不存在n,它什么也不做。指令格式 是d后跟一个空格和一个整数n。 在每个命令之后,程序将输出链表的长度,然后是链表的内容,按照从第一个(最 小)到最后一个(最大)的顺序。 输入格式:输入的每一行都包含一条指令。每行都以一个字母(或者是“i”或者是 “d”)开头,后跟一个空格,然后是一个整数。以“i”开头的一行表示该整数应该插 入链表中。以“d”开头的一行表示应从链表中删除该整数。输入i和d以外的字符程序 结束运行。 输出格式:执行每个指令后,程序将输出一行文本,其中包含链表的长度、一个冒 号以及按顺序排列的链表元素,所有内容都用空格分隔。
时间: 2024-03-27 10:40:10 浏览: 45
链表的基本操作,包括插入数据和删除数据
以下是一个简单的C语言程序,可以根据从标准输入接收的指令来维护和操作排序的链表:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 在链表中插入新节点
void insert(struct Node** head_ref, int new_data) {
// 如果链表已经存在新数据,直接返回
struct Node* current = *head_ref;
while (current != NULL) {
if (current->data == new_data) {
return;
}
current = current->next;
}
// 创建新节点并插入到链表中
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
// 如果链表为空,直接将新节点作为头节点
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
// 如果新节点的值小于头节点的值,将新节点作为头节点
if (new_data < (*head_ref)->data) {
new_node->next = *head_ref;
*head_ref = new_node;
return;
}
// 在链表中遍历,找到新节点插入的位置
current = *head_ref;
while (current->next != NULL && current->next->data < new_data) {
current = current->next;
}
// 将新节点插入到链表中
new_node->next = current->next;
current->next = new_node;
}
// 在链表中删除节点
void delete(struct Node** head_ref, int key) {
// 如果链表为空,直接返回
if (*head_ref == NULL) {
return;
}
// 如果要删除的节点是头节点,将头节点指向下一个节点
if ((*head_ref)->data == key) {
struct Node* temp = *head_ref;
*head_ref = (*head_ref)->next;
free(temp);
return;
}
// 在链表中遍历,找到要删除的节点
struct Node* current = *head_ref;
while (current->next != NULL && current->next->data != key) {
current = current->next;
}
// 如果找到了要删除的节点,将该节点从链表中删除
if (current->next != NULL) {
struct Node* temp = current->next;
current->next = current->next->next;
free(temp);
}
}
// 打印链表中的节点
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
char command;
int value;
while (scanf("%c %d", &command, &value) == 2) {
if (command == 'i') {
insert(&head, value);
} else if (command == 'd') {
delete(&head, value);
} else {
break;
}
printf("%d: ", count(head));
printList(head);
// 清空输入缓冲区
while (getchar() != '\n');
}
// 释放链表中的所有节点
struct Node* current = head;
while (current != NULL) {
struct Node* temp = current;
current = current->next;
free(temp);
}
return 0;
}
// 计算链表的长度
int count(struct Node* node) {
int count = 0;
while (node != NULL) {
count++;
node = node->next;
}
return count;
}
```
程序中定义了一个链表节点结构体,包含一个整数值和一个指向下一个节点的指针。程序中实现了三个函数:insert用于在链表中插入新节点,delete用于在链表中删除节点,printList用于打印链表中的所有节点。
在main函数中,程序从标准输入中读取指令和值,根据指令调用相应的函数来维护链表,并调用printList函数打印链表中的所有节点。程序在处理完所有指令后,释放链表中的所有节点。
注意,在使用scanf从标准输入中读取指令和值时,需要在格式字符串中指定要读取的变量的类型,并使用空格或换行符将两个变量分隔开。程序在处理完每个指令后,需要清空输入缓冲区。这是因为在读取指令和值时,scanf通常只读取指定的字符,而将换行符留在输入缓冲区中,下一次读取时可能会被误读为值。程序中使用了count函数来计算链表的长度。
阅读全文