做动图为所欲为的网站,建设网站的企业邮箱,wordpress禁止查看源代码,网站开发开票链表的基础操作III
时间限制#xff1a;1.000S 空间限制#xff1a;128MB
题目描述
请编写一个程序#xff0c;实现以下链表操作#xff1a;构建一个单向链表#xff0c;链表中包含一组整数数据。
1. 实现在链表的第 n 个位置插入一个元素#xff0c;输出整个链表的…链表的基础操作III
时间限制1.000S 空间限制128MB
题目描述
请编写一个程序实现以下链表操作构建一个单向链表链表中包含一组整数数据。
1. 实现在链表的第 n 个位置插入一个元素输出整个链表的所有元素。 2. 实现删除链表的第 m 个位置的元素输出整个链表的所有元素。
要求
1. 使用自定义的链表数据结构。 2. 提供一个 linkedList 类来管理链表包含构建链表、插入元素、删除元素和输出链表元素的方法。 3. 在 main 函数中创建一个包含一组整数数据的链表然后根据输入的 n 和 m调用链表的方法插入和删除元素并输出整个链表的所有元素。
输入描述
每次输出只有一组测试数据。
每组的第一行包含一个整数 k表示需要构建的链表的长度。
第二行包含 k 个整数表示链表中的元素。
第三行包含一个整数 S表示后续会有 S 行输入每行两个整数第一个整数为 n第二个整数为 x 代表在链表的第 n 个位置插入 x。
S 行输入...
在 S 行输入后后续会输入一个整数 L表示后续会有 L 行输入每行一个整数 m代表删除链表中的第 m 个元素。
L 行输入...
输出描述
包含多组输出。
每组第一行输出构建的链表链表元素中用空格隔开最后一个元素后没有空格。
然后是 S 行输出每次插入一个元素之后都将链表输出一次元素之间用空格隔开最后一个元素后没有空格
如果插入位置不合法则输出“Insertion position is invalid.”。
然后是 L 行输出每次删除一个元素之后都将链表输出一次元素之间用空格隔开最后一个元素后没有空格
如果删除位置不合法则输出“Deletion position is invalid.”。
输入示例
5
1 2 3 4 5
3
4 3
3 4
9 8
2
1
0
输出示例
1 2 3 3 4 5
1 2 4 3 3 4 5
Insertion position is invalid.
2 4 3 3 4 5
Deletion position is invalid. 之前我们也提到过往数组的中间插入一个元素后续所有元素都需要往后挪动一位而链表则不必这么麻烦那往链表的中间添加或者删除一个节点具体应该怎么做呢
插入链表的过程 我们可以假设这样一个场景在传递情报过程中A的下线是B, 也就是A - next B, 现在我们要引入一个C充当A和B之间的中间人A的下线是C, C的下线是B我们可以直接将A的next指向C即A - next C, 然后将C的next指向B, 但是B无法直接表示之前是用A - next来表示B的现在A - next已经指向C了所以在操作之前我们需要实现定义一个变量保存B假设为tmp, 然后将C的next指针指向B即可。
在链表中具体插入的过程如下
找到要插入的位置的前一个节点将之命名为cur, 要插入的位置的下一个节点将之命名为tmp, 它们之间的关系是cur - next tmp创建一个新的链表newNode, 将cur的next指针指向newNode 即cur - next nowNode将newNode的next指针指向tmp, 即newNode - next tmp
这样就完成了链表节点的插入过程。转换成代码如下
// 创建了一个新的 ListNode 结构的节点值为x, 并将其地址赋给指针 newNode
ListNode *newNode new ListNode(x);
// 创建了一个名为 tmp 的指针临时存储当前节点 cur 的下一个节点的地址。
ListNode *tmp cur -next;
// 将当前节点 cur 的 next 指针更新为指向新节点 newNode将新节点插入到当前节点后面。
cur-next newNode;
// 将新节点 newNode 的 next 指针设置为指向之前临时存储的节点 tmp
newNode-next tmp;删除链表的过程 删除链表的过程则比较简单只需要找到删除节点的前一个节点cur, 并将其next 指针设置为指向当前节点的下下个节点从而跳过了下一个节点实现了节点的删除操作。
// cur-next 表示当前节点 cur 的下一个节点
// cur-next-next 表示要删除的节点的下一个节点
// 当前节点 cur 的 next 指针不再指向要删除的节点而是指向了要删除节点的下一个节点
cur-next cur-next-next;打印链表
在函数内部定义了一个名为 cur 的指针它初始化为指向 head即链表的头节点。
什么时候链表迭代到最后一个节点呢检查当前节点 cur 的下一个节点是否存在不为 NULL, 当前节点的下一个节点为NULL时说明下一个节点为空节点即链表的末尾。
while(cur - next ! NULL) {}在循环体内打印当前节点 cur 的下一个节点cur-next的值val。接下来将 cur 更新为指向链表中的下一个节点以便在下一次循环中打印下一个节点的值。
while (cur-next ! NULL) {cout cur-next-val ;cur cur - next;
}循环体结束时表示已经遍历完了整个链表。最后打印一个换行符用于分隔不同的输出行。
// 打印链表
void printLinklist(ListNode* head) {ListNode* cur head;while (cur-next ! NULL) {cout cur-next-val ;cur cur - next;}cout endl;
}代码编写
我们照例先把代码的基础结构以及定义链表的结构体写出来。
#include iostream
using namespace std;
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};
int main() {}首先需要接收整数k, 表示需要构建链表的长度
int main() {int k, val; // k表示链表长度val表示构建链表时输入的值cin k;
}然后我们需要构建一个长度为k的链表在构建链表之前可以先创建一个虚拟头节点以及初始化一个指针cur指向虚拟头节点方便后续节点的接入。
ListNode* dummyHead new ListNode(0); // 创建了一个虚拟头结点
ListNode* cur dummyHead; // 定义一个指向当前节点的指针 cur初始指向虚拟头结点
for (int i 0; i k; i) { // 或者使用while(n--)cin val;ListNode *newNode new ListNode(val); // 构造一个新的节点cur - next newNode; // 将新节点接入链表cur cur - next; // cur 指向下一个节点
}之后需要接收一个整数s表示s行输入每行两个整数第一个整数为 n第二个整数为 x 代表在链表的第 n 个位置插入 x。
int s, n, x; // s表示s行输入n代表插入位置x代表插入元素的值
cin s; // 输入s
while (s--) {cin n x; // 输入n和x}题目中要求插入位置不合法时输出Insertion position is invalid.
什么时候才会插入位置不合法呢当插入的位置n是一个小于等于0的数或者n大于链表的长度时插入位置不合法。 ⚠️ 需要注意插入后链表的长度会变化所以我们可以提前定义一个变量listLen指代链表的长度 int listLen k; // 定义链表的长度if (n 0 || n listLen) { // 当要插入的位置非法时cout Insertion position is invalid. endl; // 输出错误提示continue;
}如果不满足上面的if语句说明插入的位置合法后续执行的操作是完成插入以及打印链表。
插入链表节点的过程在前面已经描述过只需找到需要插入位置的前一个节点即可, 也就是第n-1个节点从虚拟头节点开始遍历需要走n-1步
// 指针重新指向虚拟头结点准备用cur遍历链表
cur dummyHead;
// 寻找添加节点的位置i从1开始
for (int i 1; i n; i) {cur cur-next;
}插入节点的代码直接拿来使用即可不要忘记将链表长度加1
// 插入节点
ListNode *newNode new ListNode(x); // 构造一个新的节点
ListNode *tmp cur -next;
cur-next newNode;
newNode-next tmp;// 链表长度加1
listLen;接着完成打印链表即可
// 打印链表
printLinklist(dummyHead);链表节点删除的前置步骤类型需要接收一个整数 L表示后续会有 L 行输入每行一个整数 m代表删除链表中的第 m 个元素。
int l,m;
cin l;
while (l--) {cin m;
}判断是否是非法输入
if (m 0 || m listLen) {cout Deletion position is invalid. endl;continue;
}找到要删除节点的前一个节点
// 指针重新指向虚拟头结点准备用cur遍历链表
cur dummyHead;//开始寻找删除节点的位置i从1开始因为节点计数从1开始
for (int i 1; i m; i) cur cur-next;// 删除节点
cur-next cur-next-next;listLen--; // 链表长度减一// 如果删除节点后链表为空则不打印
if (listLen ! 0) printLinklist(dummyHead); c代码实现
#includeiostream
using namespace std;
typedef struct ListNode{int data;ListNode *next;ListNode(int x):data(x),next(nullptr){}
}*L;
void printLinkList(ListNode *dummyHead){ListNode *curdummyHead;while(cur-next!NULL){coutcur-next-data ;curcur-next;}coutendl;
}
int main(){int k;L dummyHeadnew ListNode(0);//创建一个虚拟头节点cink;int listlenk;//记录链表的长度L curdummyHead;//定义一个指向当前节点的指针cur初始指向虚拟头节点int val;for(int i0;ik;i){cinval;L newNodenew ListNode(val);cur-nextnewNode;curcur-next;}int s,n,x;cins;while(s--){cinnx;if(n0||nlistlen){cout Insertion position is invalid. endl;continue;}//指针重新指向虚拟头节点。准备用cur遍历链表curdummyHead;//for(int i1;in;i)curcur-next;L newNodenew ListNode(x);L tmpcur-next;cur-nextnewNode;newNode-nexttmp;listlen;printLinkList(dummyHead);}int l,m;cinl;while(l--){cinm;if(m0||mlistlen){cout Deletion position is invalid. endl;continue;}curdummyHead;for(int i1;im;i) curcur-next;cur-nextcur-next-next;listlen--;if(listlen!0){printLinkList(dummyHead);}}
}
