静态链表

PAT的套路题，多刷几道知道了。
注意：是以地址作为数组的下标，所以读入的时候要细心，我开始就想当然的挨个存了，最后调了很久才发现。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
	int add,key,next;
	int no,tag;
}Node[100005];
int hash[100005];
bool cmp(node a, node b){
	if(a.tag!=b.tag) return a.tag > b.tag;
	else return a.no < b.no;
}
int main(){
	int start,n,x;
	scanf("%d %d",&start,&n);
	memset(hash,0,sizeof(hash));
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		Node[x].add=x;
		scanf("%d %d",&Node[x].key,&Node[x].next);
	}
	int p = start;
	int cnt=0;
	int num1=0,num2=0;
	while(p != -1){
		if(hash[abs(Node[p].key)]==0){
			hash[abs(Node[p].key)]=1;
			Node[p].tag=2;
			num1++;
		}else{
			Node[p].tag=1;
			num2++;
		}
		Node[p].no=cnt;
		cnt++;
		p = Node[p].next;
	}
	
	sort(Node,Node+100000,cmp);
	for(int i=0;i<num1;i++){
		if(i!=num1-1){
			printf("%05d %d %05d\n",Node[i].add,Node[i].key,Node[i+1].add);
		}else{
			printf("%05d %d -1\n",Node[i].add,Node[i].key);
		}
	}	
	for(int i=num1;i<cnt;i++){
		if(i!=cnt-1){
			printf("%05d %d %05d\n",Node[i].add,Node[i].key,Node[i+1].add);
		}else{
			printf("%05d %d -1\n",Node[i].add,Node[i].key);
		}
	}
	return 0;
}

版本2

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
	int add,value,index,next,tag;
}E[maxn];
bool cmp(node a, node b){
	if(a.tag!=b.tag) return a.tag > b.tag;
	else{
		return a.index < b.index;
	}
}
int Hash[10005]={0};
int main(){
	int p,n,add,value,next;
	cin>>p>>n;
	for(int i=0;i<maxn;i++){
		E[i].tag = 0;
		E[i].index = maxn;
	}
	for(int i=0;i<n;i++){
		cin>>add>>value>>next;
		E[add].add = add;
		E[add].value = value;
		E[add].next = next;
		
	}
	int m=0,k=0;
	while(p!=-1){
		if(Hash[abs(E[p].value)]==0){
			E[p].tag = 1;
			Hash[abs(E[p].value)]=1;
			m++;
		}
		E[p].index = k;
		p = E[p].next;
		k++; //单链表中总的节点 
	}
	sort(E,E+maxn,cmp);
	for(int i=0;i<m;i++){
		printf("%05d %d",E[i].add,E[i].value);
		if(i!=m-1) printf(" %05d\n",E[i+1].add);
		else printf(" -1\n");
	}
	for(int i=m;i<k;i++){
		printf("%05d %d",E[i].add,E[i].value);
		if(i!=k-1) printf(" %05d\n",E[i+1].add);
		else printf(" -1\n");
	}
	return 0;
}