题目
请你实现一个链表。
操作：
insert x y：将y加入链表，插入在第一个值为x的结点之前。若链表中不存在值为x的结点，则插入在链表末尾。保证x,y为int型整数。
delete x：删除链表中第一个值为x的结点。若不存在值为x的结点，则不删除。
输入描述：
第一行输入一个整数n (1≤n≤1041≤n≤104)，表示操作次数。
接下来的n行，每行一个字符串，表示一个操作。保证操作是题目描述中的一种。
输出描述：
输出一行，将链表中所有结点的值按顺序输出。若链表为空，输出"NULL"(不含引号)。
示例1
输入：
5
insert 0 1
insert 0 3
insert 1 2
insert 3 4
delete 4
输出：
2 1 3
实现思路
这道题考察的是链表的增查删改操作，我们要实现以下四个接口：
ListNode*BuySLTNode(int x); void STLPrint(ListNode*ps); void STLinsert(ListNode**ps,int x,int y); void STLdelet(ListNode**ps,int x);
结构体定义：
1. typedef struct n{ 2. int data; 3. struct n *next; 4. }ListNode;
核心逻辑：
- BuySLTNode 函数：该函数用于生成一个新的 ListNode 节点，并返回该节点的指针。其实现逻辑如下：
- 首先调用 malloc 函数申请一块内存，大小为 ListNode 结构体大小。
- 判断是否申请成功，如果失败则输出错误信息并退出程序。
- 将参数 x 放入新节点的 data 成员中，将指针成员 next 初始化为 NULL。
- 最后返回新节点的指针。
- STLPrint 函数：该函数用于遍历链表并输出每个节点的 data 值。其实现逻辑如下：
- 定义一个指向当前节点的指针 cur，初始值为 head。
- 循环遍历链表，直到找到尾节点。每次循环中执行以下操作：
- 输出当前节点的 data 值。
- 将 cur 指针指向下一个节点。
- SLTXinsert 函数：该函数用于在链表中插入一个新节点。其实现逻辑如下：
- 首先使用 BuySLTNode 函数生成一个新节点。
- 如果链表为空，则将新节点设为头结点，即将头指针 head 指向新节点，然后直接返回。
- 否则，定义两个指针 prev 和 cur，分别指向头结点和下一个节点。
- 循环遍历链表，直到找到第一个值为参数 x 的节点或者到达链表尾部。每次循环中执行以下操作：
- 将 prev 指针指向当前节点 cur。
- 将 cur 指针移动到下一个节点。
- 如果 cur 为空，则说明没有找到值为 x 的节点，此时将新节点添加到链表末尾即可。首先将新节点的 next 指针设为 NULL，然后将 prev 节点的 next 指针指向新节点。
- 否则，将新节点添加到链表中间。首先将新节点的 next 指针指向 cur 节点，然后判断 prev 是否为 NULL。如果是，则说明头结点就是要插入的位置，需要修改头指针 head；否则，将 prev 节点的 next 指针指向新节点。
- SLTdelet 函数：该函数用于删除链表中的一个节点。其实现逻辑如下：
- 定义两个指针 prev 和 cur，分别指向头结点和下一个节点。
- 如果头结点的 data 值等于参数 x，则说明需要删除头结点。此时将头指针 head 指向下一个节点，释放当前节点的内存，并直接返回。
- 循环遍历链表，直到找到第一个值为参数 x 的节点或者到达链表尾部。每次循环中执行以下操作：
- 将 prev 指针指向当前节点 cur。
- 将 cur 指针移动到下一个节点。
- 如果 cur 不为空，则说明找到了值为 x 的节点，此时将 prev 节点的 next 指针指向 cur 节点的下一个节点，释放 cur 节点的内存即可。
- 否则，说明没有找到要删除的节点，函数直接返回。
代码
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> typedef struct n{ int data; struct n *next; }ListNode; ListNode*BuySLTNode(int x); void STLPrint(ListNode*ps); void STLinsert(ListNode**ps,int x,int y); void STLdelet(ListNode**ps,int x); ListNode*BuySLTNode(int x) { ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode)); if(NewNode==NULL) { perror("malloc"); exit(-1); } NewNode->data = x; NewNode->next = NULL; return NewNode; } void STLPrint(ListNode*ps) { ListNode*cur = ps; if(ps==NULL) { printf("NULL"); } while(cur) { printf("%d ",ps->data); cur = cur->next; } printf("\n"); } void STLinsert(ListNode**ps,int x,int y) { ListNode*newNode = BuySLTNode(y); if(*ps==NULL) { newNode->next = NULL; *ps = newNode; } ListNode*cur = *ps; ListNode*prev = NULL; while(cur&&cur->data!=x) { prev = cur; cur = cur->next; } if(cur==NULL) { newNode->next = NULL; *ps = newNode; } else{ newNode->next = cur; if(prev==NULL) { prev->next = newNode; } } } void STLdelet(ListNode**ps,int x) { ListNode*cur = *ps; ListNode*prev = NULL; while(cur&&cur->data==x) { *ps = cur->next; free(cur); return; } while(cur&&cur->data!=x) { prev = cur; cur = cur->next; } if(cur==NULL) { prev->next = cur->next; free(cur); } } int main() { int input = 0; int s1,s2,s3; char array[20]; ListNode*css = NULL; scanf("%d",&input); while(input--) { scanf("%s",array); if(strcmp(array,"insert")==0) { scanf("%d%d",&s1,&s2); STLinsert(&css,s1,s2); } else if(strcmp(array,"delete")==0) { scanf("%d",&s3); STLdelet(&css,s3); } } STLPrint(css); }
