【1074】Reversing Linked List (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
const int maxn=100010;
//算法de思路：结点结构体的order初始化为maxn(无效结点)，再按照静态链表结点排序(order依次赋值)
五个步骤，key：第五个中对每一块最后一个结点的next地址的处理
//定义静态链表(步骤1)
struct Node{  
  int address,data,next;
  int order;  //结点在链表中的序号，无效结点记为maxn
}node[maxn];
bool cmp(Node a,Node b){
  return a.order<b.order; //按order从小到大排序
}
int main(){   
  //初始化(步骤2)
  for(int i=0;i<maxn;i++){  
    node[i].order=maxn;  //初始化全部为无效结点
  }
  int begin,n,K,address;
  scanf("%d%d%d",&begin,&n,&K);  //起始地址，结点个数，步长
  //初始化静态链表
  for(int i=0;i<n;i++){
    scanf("%d",&address);
    scanf("%d%d",&node[address].data,&node[address].next);
    node[address].address=address;  //别漏了这步，“两个”address不同
  }
  int p=begin,count=0; //count计数有效结点的数目
  //遍历链表找出单链表的所有有效结点(步骤3)
  while(p!=-1){  
    node[p].order=count++; //结点在单链表中的序号
    p=node[p].next;  //下一个结点
  }
  //按单链表从头到尾顺序排列(步骤4)
  sort(node ,node+maxn,cmp);  
  //有效结点为前count个结点，为了书写方便就把count赋值给n
  n=count;
  //单链表已经形成,按照题目要求输出(步骤5)
  for(int i=0;i<n/K;i++){  //枚举完整的n/K块
    for(int j=(i+1)*K-1 ; j>i*K;  j-- ){  //第i块倒着输出
      printf("%05d %d %05d\n",node[j].address, node[j].data,  node[j-1].address);
    }
    //下面是每一块的最后一个结点的next地址的处理
    printf("%05d %d ",node[i*K].address,node[i*K].data);
    if(i<n/K-1){ //如果不是最后一块,就指向下一块的最后一个结点
      printf("%05d\n",node[ (i+2)*K-1 ].address );
    }else{  //如果是最后一块时
      if(n%K==0) { //恰好是最后一个结点时，输出-1
        printf("-1\n");
    }else{  //剩下不完整的块按照原先的顺序输出
      printf("%05d\n",node[ (i+1)*K ].address);//注意换行符
      for(int i=n/K*K ;  i<n ;i++){
        printf("%05d %d ",node[i].address,node[i].data);
        if(i<n-1){
          printf("%05d\n",node[i+1].address);
        }else{
          printf("-1\n");
        }
      }
      }
    }
  } 
  system("pause");
  return 0;   
}