[C语言/PTA] 单链表结点删除

2023-06-18 13:15| 来源: 网络整理| 查看: 265

[C语言/PTA] 单链表结点删除题目要求解题思路代码总结

题目要求

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下：

struct ListNode { int data; ListNode *next; }; 函数接口定义： struct ListNode *readlist(); struct ListNode *deletem( struct ListNode *L, int m ); 函数readlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数deletem将单链表L中所有存储了m的结点删除。返回指向结果链表头结点的指针。

裁判测试程序样例：

#include #include struct ListNode { int data; struct ListNode *next; }; struct ListNode *readlist(); struct ListNode *deletem( struct ListNode *L, int m ); void printlist( struct ListNode *L ) { struct ListNode *p = L; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { int m; struct ListNode *L = readlist(); scanf("%d", &m); L = deletem(L, m); printlist(L); return 0; } /* 你的代码将被嵌在这里 */

输入样例： 10 11 10 12 10 -1 10

输出样例： 11 12

解题思路

结合所给代码，可分析代码实现过程如下：

通过 readlist() 函数将输入的数据存储到链表中，再调用 deletem() 函数来删除链表中指定的元素，最后通过 printlist() 函数输出最终的链表结果。

其中，struct ListNode 为链表节点结构体，包含两个成员变量：int data 表示当前节点存储的数据，struct ListNode *next 表示指向下一个节点的指针。

函数 void printlist(struct ListNode *L) 用于遍历整个链表并打印出每个节点的值；

函数 struct ListNode *readlist() 用于读取输入的数据并生成链表；

函数 struct ListNode *deletem(struct ListNode *L, int m) 用于删除链表中所有值为 m 的节点，并返回处理后的链表。

代码 struct ListNode *readlist() // 读取链表 { struct ListNode *head,*p1,*p2; // 定义头结点和两个临时指针变量 int n=0; // 定义节点数量 head = NULL; // 初始化头结点为空指针 p1 = p2 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 开辟新空间 scanf("%d",&p1->data); // 从键盘上读入第一个节点的数据 while(p1->data!=-1) // 如果当前节点不是最后一个节点 { n++; // 记录节点个数 if(n==1) // 如果是头节点 head = p1; // 将当前节点作为头结点 else p2->next = p1; // 将前一个节点指针指向当前节点 p2 = p1; // 将 p1 赋值给 p2，以便在下一次循环中使用 p1 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 为下一节点开辟新空间 scanf("%d",&p1->data); // 读入下一个节点的数据 } p2->next = NULL; // 最后一个节点指向 NULL return head; // 返回头结点指针 } struct ListNode *deletem( struct ListNode *L, int m ) // 删除指定元素 { struct ListNode *p1,*p2; // 定义两个指针变量 p1 = L; // 将 L（链表的头结点）赋值给 p1 while(p1!=NULL) // 循环遍历链表 { if(p1->data==m) // 如果当前节点存储的数据等于待删除的数 m { if(p1==L) // 如果当前节点是头节点 L = p1->next; // 将头指针指向当前节点的下一个节点，即删除头节点 else p2->next = p1->next; // 将前一个节点的指针指向当前节点的下一个节点，即删除中间节点或尾节点 } else { p2 = p1; // 将 p1 赋值给 p2，以便在下一次循环中使用 } p1 = p1->next; // 将 p1 指向下一个节点 } return L; // 返回操作后的链表 }

完整代码如下：

#include #include struct ListNode { int data; // 当前节点存储的数据 struct ListNode *next; // 指向下一个节点的指针 }; struct ListNode *readlist(); // 读取链表 struct ListNode *deletem( struct ListNode *L, int m ); // 删除指定元素 void printlist( struct ListNode *L ) // 输出链表 { struct ListNode *p = L; while (p) { // 循环遍历链表 printf("%d ", p->data); // 输出当前节点的数据 p = p->next; // 寻找下一个节点 } printf("\n"); } int main() { int m; // 定义待删除的数 struct ListNode *L = readlist(); // 读取链表 scanf("%d", &m); // 从键盘上输入待删除的数 L = deletem(L, m); // 删除待删除的数并返回操作后的链表 printlist(L); // 输出最终的链表 return 0; } struct ListNode *readlist() // 读取链表 { struct ListNode *head,*p1,*p2; // 定义头结点和两个临时指针变量 int n=0; // 定义节点数量 head = NULL; // 初始化头结点为空指针 p1 = p2 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 开辟新空间 scanf("%d",&p1->data); // 从键盘上读入第一个节点的数据 while(p1->data!=-1) // 如果当前节点不是最后一个节点 { n++; // 记录节点个数 if(n==1) // 如果是头节点 head = p1; // 将当前节点作为头结点 else p2->next = p1; // 将前一个节点指针指向当前节点 p2 = p1; // 将 p1 赋值给 p2，以便在下一次循环中使用 p1 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 为下一节点开辟新空间 scanf("%d",&p1->data); // 读入下一个节点的数据 } p2->next = NULL; // 最后一个节点指向 NULL return head; // 返回头结点指针 } struct ListNode *deletem( struct ListNode *L, int m ) // 删除指定元素 { struct ListNode *p1,*p2; // 定义两个指针变量 p1 = L; // 将 L（链表的头结点）赋值给 p1 while(p1!=NULL) // 循环遍历链表 { if(p1->data==m) // 如果当前节点存储的数据等于待删除的数 m { if(p1==L) // 如果当前节点是头节点 L = p1->next; // 将头指针指向当前节点的下一个节点，即删除头节点 else p2->next = p1->next; // 将前一个节点的指针指向当前节点的下一个节点，即删除中间节点或尾节点 } else { p2 = p1; // 将 p1 赋值给 p2，以便在下一次循环中使用 } p1 = p1->next; // 将 p1 指向下一个节点 } return L; // 返回操作后的链表 } 总结

该题考察了链表的基本操作，包括链表的创建、遍历、删除指定元素等。此外，还涉及到如何使用动态内存分配函数 malloc 和函数指针等知识点。

我是秋说，我们下次见。

【本文地址】

公司简介

联系我们