关于算法-数据结构:PAT甲级1052-Linked-List-Sorting

题目粗心:

给定 N 个结点起始地址为 $begin$_$address$ 的单链表, 要求依据 data 进行排序, 而后输入链表

算法思路：

咱们首先用 $node$ 数组存储所有输出的结点, 在输出的时候应用 $dataToAddress$ 记录数据到地址的映射 (数据和地址是绑定的，无论怎么样都不会变动), 因为对于输出可能会有不在链表上的结点, 所以应用 $isExist$ 记录所有输出的节点, 这样就能够判断起始节点是否存在输出节点中，目标是为了解决链表为空的状况。对于只有局部无效节点的状况，咱们须要遍历 $node$ 数组，并应用 $data$ 数组保留所有在链表中的节点的数据，$count$ 记录无效节点的个数，这里排序采纳的是索引排序的技巧，间接对 $data$ 数组排序，那么再利用 $dataToAddress$ 就能够不便的晓得对应节点的地址，并且 $next$ 就是下一个节点的 $address$, 不过得留神，最初一个节点的 $next$ 为 -1，须要手动赋值，同时须要记录新的起始地址为 $data$ 数组中第一个节点的地址。最初依照要求进行输入即可

留神点：

1、输出节点会呈现有效的状况，所以得遍历输出节点，保留无效节点的信息，测试点 1 和 4 考查。
2、测试点 4 考查所有节点都是有效的状况，这个时候得输入 ”0 -1″
3、地址保留 5 位有效数字，- 1 得特判。

提交后果：

AC 代码：

#include <cstdio>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Node{
    int address;
    int data;
    int next;
}node[100005];

unordered_map<int,int> dataToAddress;
unordered_map<int,bool > isExist;

int main(){
    int N,begin_address;
    scanf("%d %d",&N,&begin_address);
    Node p{};
    for (int i = 0; i < N; ++i) {scanf("%d %d %d",&p.address,&p.data,&p.next);
        node[p.address] = p;
        dataToAddress[p.data] = p.address;
        isExist[p.address] = true;
    }
    if(!isExist[begin_address]){printf("0 -1\n");
        return 0;
    }
    int data[N];// 保留所有的数据
    int count = 0;// 链表上的节点个数
    for (int address = begin_address; address !=-1 ; address=node[address].next) {data[count++] = node[address].data;
    }
    sort(data,data+count);
    for (int i = 0; i < count-1; ++i) {int address = dataToAddress[data[i]];
        int nextAddress = dataToAddress[data[i+1]];
        node[address].next = nextAddress;
        if(i==0){
            // 记录新的起始地址
            begin_address = address;
        }
    }
    // 最初一个节点的下一个节点地址为 -1
    node[dataToAddress[data[count-1]]].next = -1;
    printf("%d %05d\n",count,begin_address);
    while (begin_address!=-1){if(node[begin_address].next!=-1){printf("%05d %d %05d\n",node[begin_address].address,node[begin_address].data,node[begin_address].next);
        } else {printf("%05d %d -1\n",node[begin_address].address,node[begin_address].data);
        }
        begin_address = node[begin_address].next;
    }
    return 0;
}