算法1:数组模拟单链表存储-遍历单链表需要操作的数据放到数组中操作() $O(nlogn)$
//排序 排的是值,同时要输出地址 pair存储
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1E5+10;
PII a[N]; //值 和 该节点的地址
int n, h, e[N], ne[N], cnt;
int main() {
scanf("%d%d", &n, &h);
for (int i = 0; i < n; ++ i) {
int addr, data, nex;
scanf("%d%d%d", &addr, &data, &nex);
e[addr] = data;
ne[addr] = nex;
}
for (int i = h; i != -1; i = ne[i])
a[cnt++] = {e[i], i};
sort(a, a+cnt);
printf("%d ", cnt);
if (cnt == 0) {
printf("-1");
return 0;
}
printf("%05d\n", a[0].second);
for (int i = 0; i < cnt; ++ i) {
printf("%05d %d ", a[i].second, a[i].first);
if (i == cnt-1) printf("-1");
else printf("%05d\n", a[i+1].second);
}
return 0;
}
算法2:结构体存储() $O(nlogn)$
//结构体存储单链表
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1E5+10;
struct node{
int addr, data, next;
bool operator< (const node& t) const{
return data < t.data;
}
}a[N];//存储地址和节点的映射
vector<node> res;
int h, n;
int main() {
scanf("%d%d", &n, &h);
for (int i = 0; i < n; ++ i) {
int addr, data, next;
scanf("%d%d%d", &addr, &data, &next);
a[addr] = {addr, data, next}; //
}
//存储出现在单链表中的节点,a中存下的是所有节点,有些节点并不在单链表上
for (int i = h; ~i; i = a[i].next)
res.push_back(a[i]);
if (res.empty()) {
printf("0 -1");
return 0;
}
sort(res.begin(), res.end());
printf("%d %05d\n", res.size(), res[0].addr);
for (int i = 0; i < res.size(); ++ i) {
printf("%05d %d ", res[i].addr, res[i].data);
if (i == res.size() - 1) printf("-1\n");
else printf("%05d\n", res[i+1].addr); //后面那个节点的地址
}
return 0;
}