关于算法-数据结构: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;
}