PAT甲级1052LinkedListSorting(25分)（数组模拟链表，没注意到不一定所有节点都在链表里）

#include
#include
#include
#include
#include
#include
#include<string>
#include
using namespace std;
int n;
struct node{
    int k;
    int next;
}a[100005];
struct node2{
    int k;
    int add;
}b[100005];
int x;
bool cmp(node2 x,node2 y){
    return x.k<y.k;
}
int main(){
    int root;
    cin>>n>>root;
    a[root].next=-2;
    for(int i=1;i<=n;i++){
        cin>>x;
        cin>>a[x].k>>a[x].next;//这样存储
    }
    int num=0;
    if(a[root].next==-2){//没有一个在链表里
        printf("%d %d",0,-1);
        return 0;
    }
    while(a[root].next!=-1){//排序的节点必须都在链表里
        b[++num].k=a[root].k;//换一种存储节点的方式，按顺序存储
        b[num].add=root;
        root=a[root].next;
    }
    b[++num].k=a[root].k;
    b[num].add=root;
    sort(b+1,b+1+num,cmp);
    printf("%d %05d\n",num,b[1].add);
    for(int i=1;i<=num;i++){
        printf("%05d %d ",b[i].add,b[i].k);
        if(i!=num) printf("%05d\n",b[i+1].add);
        else cout<<"-1";
    }
    return 0;
}

#include 
using namespace std;
struct NODE {
    int address, key, next;
    bool flag;
}node[100000];
int cmp1(NODE a, NODE b) {
    return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key;
}
int main() {
    int n, cnt = 0, s, a, b, c;
    scanf("%d%d", &n, &s);
    for(int i = 0; i ) {
        scanf("%d%d%d", &a, &b, &c);
        node[a] = {a, b, c, false};
    }
    for(int i = s; i != -1; i = node[i].next) {
        node[i].flag = true;
        cnt++;
    }
    if(cnt == 0) {
        printf("0 -1");
    } else {
        sort(node, node + 100000, cmp1);
        printf("%d %05d\n", cnt, node[0].address);
        for(int i = 0; i ) {
            printf("%05d %d ", node[i].address, node[i].key);
            if(i != cnt - 1)
                printf("%05d\n", node[i + 1].address);
            else
                printf("-1\n");
        }
    }
    return 0;
}