天梯——链表去重
思路
数组模拟链表
- 用结构体存储一个节点的键值和下一个节点地址，然后开一个结构体数组，用当前节点地址作为下标，这样可以直接访问
- 再开一个标记数组flag，下标是每个节点键值的绝对值，初始化为0，用来标记该键值是否出现
- 从题目给出的链表第一个节点开始遍历链表，注意如何遍历：
for(int i=st;i!=-1;i=nodep[i].next) - 输出两个数组，注意最后一个节点的下一个节点地址要输出-1，还有每个地址占5位，不足在前面补0
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{ //结构体，表示链表中的一个成员int data,next; //键值，下一个节点地址
}nodep[N]; //结构体数组
int flag[N]={0}; //标记键值是否出现
int main(){int st,n;cin>>st>>n;for(int i=0;i<n;i++){int t; //存储当前节点地址cin>>t; //用当前节点地址作为nodep数组的下标cin>>nodep[t].data>>nodep[t].next;}memset(flag,0,sizeof(flag)); //flag数组初始化为0vector<int>v1,v2; //v1存储去重后的链表节点地址，v2存储被删除的链表节点地址for(int i=st;i!=-1;i=nodep[i].next){ //从链表的第一个节点st开始遍历链表if(flag[abs(nodep[i].data)]==0){flag[abs(nodep[i].data)]=1;v1.push_back(i);}else{v2.push_back(i);}} //输出for(int i=0;i<v1.size();i++){if(i+1<v1.size()) printf("%05d %d %05d\n",v1[i],nodep[v1[i]].data,v1[i+1]);else printf("%05d %d %d\n",v1[i],nodep[v1[i]].data,-1);}if(v2.size()){for(int i=0;i<v2.size();i++){if(i+1<v2.size()) printf("%05d %d %05d\n",v2[i],nodep[v2[i]].data,v2[i+1]);else printf("%05d %d %d\n",v2[i],nodep[v2[i]].data,-1);}}return 0;
}延申
通过本题，我认为创建一个链表并实现它的删除，插入操作也可以用数组模拟
- 创建一个结构体数组nodep，数组下标为当前节点地址，结构体包含两个数据，节点的键值和下一个节点地址
- 按照题目所给节点数量，循环建立链表
- 再开一个vector数组v，从第一个节点遍历整个链表，直至-1，将所有节点地址存储到vector数组中
- 此时，如果要删除第i个节点，直接让第i-1的next指向i+1，如果是在第i和i+1之间插入一个数a，那便让i的next指向a,a的next指向i+1,如果要访问第i个节点，直接用v[i]得到该节点地址，再用nodep[v[i]].data和nodep[v[i]].next访问相关信息即可
可行性
利用结构体数组 nodep 来模拟链表节点，数组下标当作节点地址，结构体里存有节点的键值和下一个节点的地址，这种做法可行。同时，借助 vector 数组 v 存储链表节点的地址，能更方便地进行遍历、插入、删除等操作。
链表构建
根据题目给定的节点数量，通过循环把节点信息存入 nodep 数组，从而构建链表，这是可行的。示例代码如下：
#include <iostream>
#include <vector>
using namespace std;const int N = 100005;
struct node {int data, next;
} nodep[N];int main() {int st, n;cin >> st >> n;for (int i = 0; i < n; i++) {int t;cin >> t;cin >> nodep[t].data >> nodep[t].next;}return 0;
}节点地址存储
从第一个节点开始遍历整个链表，直至遍历到 -1，把所有节点的地址存到 vector 数组 v 中，这样后续操作会更便捷。示例代码如下：
vector<int> v;
for (int i = st; i != -1; i = nodep[i].next) {v.push_back(i);
}删除操作
要删除第 i 个节点，让第 i - 1 个节点的 next 指向第 i + 1 个节点，这样就把第 i 个节点从链表中移除了。不过要注意边界情况，例如删除第一个节点或者最后一个节点。示例代码如下：
// 假设要删除第 i 个节点
if (i > 0 && i < v.size()) {int prev = v[i - 1];int next = v[i + 1];nodep[prev].next = next;
}插入操作
若要在第 i 和第 i + 1 个节点之间插入一个新节点 a，让第 i 个节点的 next 指向 a，a 的 next 指向第 i + 1 个节点。同样要注意边界情况。示例代码如下：
// 假设要在第 i 和第 i + 1 个节点之间插入新节点 a
if (i >= 0 && i < v.size() - 1) {int cur = v[i];int next = v[i + 1];nodep[a].next = next;nodep[cur].next = a;// 更新 v 数组v.insert(v.begin() + i + 1, a);
}访问操作
要访问第 i 个节点，直接使用 v[i] 得到该节点的地址，再通过 nodep[v[i]].data 和 nodep[v[i]].next 访问相关信息。示例代码如下：
// 访问第 i 个节点
if (i >= 0 && i < v.size()) {int addr = v[i];int data = nodep[addr].data;int next = nodep[addr].next;cout << "Data: " << data << ", Next: " << next << endl;
}如果有错误可以评论区告诉我，我会认真修改的