PAT甲级A1052---链表处理

1052 Linked List Sorting (25分)

分析：

注意有效结点等于0的时候特判。

C++：

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 100010;
const int INF = 1 << 30;
struct Node {
    int add, next, data;
    bool flag;
} nodes[maxn];

bool cmp(Node a, Node b) {
    if (a.flag == false || b.flag == false) {
        return a.flag > b.flag;
    } else {
        return a.data < b.data;
    }
}

int main() {
    int n, begin;
    scanf("%d%d", &n, &begin);
    int data, add, next;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &add, &data, &next);
        nodes[add].add = add;
        nodes[add].data = data;
        nodes[add].next = next;
    }
    int count = 0;//有效结点
    while (begin != -1) {
        nodes[begin].flag = true;
        count++;
        begin = nodes[begin].next;
    }
    if (count == 0) {
        printf("0 -1\n");
        return 0;
    }
    sort(nodes, nodes + maxn, cmp);
    printf("%d %05d\n", count, nodes[0].add);
    for (int i = 0; i < count - 1; i++) {
        printf("%05d %d %05d\n", nodes[i].add, nodes[i].data, nodes[i + 1].add);
    }
    printf("%05d %d -1\n", nodes[count - 1].add, nodes[count - 1].data);
    return 0;
}