#include<stdio.h>
#include<algorithm>
using namespace std;
struct Node{
int now;
int data;
int next;
int order;
}node[100010];
bool cmp(Node a,Node b){
return a.order<b.order;
}
int main(){
int first,n,m;
scanf("%d%d%d",&first,&n,&m);
for(int i=0;i<=100010;i++){
node[i].order=100010;
}
for(int i=1;i<=n;i++){
int now;
scanf("%d",&now);
scanf("%d%d",&node[now].data,&node[now].next);
node[now].now=now;
}
int p=first,count=0;
while(p!=-1){
node[p].order=count++;
p=node[p].next;
}
sort(node,node+100010,cmp);
n=count;//有效节点数;
int k;
for(int i=0;i<n/m;i++){
for(int j=(i+1)*m-1;j>i*m;j--){
printf("%05d %d %05d\n",node[j].now,node[j].data,node[j-1].now);
}
if(i<n/m-1){
printf("%05d %d %05d\n",node[i*m].now,node[i*m].data,node[(i+2)*m-1].now);
}else{
if(n%m==0)
printf("%05d %d -1\n",node[i*m].now,node[i*m].data);
else{
printf("%05d %d %05d\n",node[i*m].now,node[i*m].data,node[(i+1)*m].now);
for(k=0;k<n%m-1;k++){
printf("%05d %d %05d\n",node[(i+1)*m+k].now,node[(i+1)*m+k].data,node[(i+1)*m+k+1].now);
}
printf("%05d %d -1\n",node[(i+1)*m+k].now,node[(i+1)*m+k].data);
}
}
}
return 0;
}
第一次,参考算法笔记;
难点在于利用order把链表结点排序;
利用now存数组现有地址