当前位置:网站首页>PAT_ Grade A_ 1052 Linked List Sorting

PAT_ Grade A_ 1052 Linked List Sorting

2020-11-10 12:44:27 Qiao Zixin

The main idea of the topic :

Given N The starting address of nodes is $begin$_$address$ The single chain table of , Requirements according to data Sort , Then output the linked list

Algorithm ideas :

We use $node$ Array stores all the input nodes , Use when typing $dataToAddress$ Record data to address mapping ( Data and address are bound , No matter what, it won't change ), For input, there may be nodes that are not on the linked list , So use $isExist$ Record all input nodes , In this way, we can judge whether the starting node exists in the input node , The purpose is to solve the problem that the linked list is empty . In the case of only partially valid nodes , We need to traverse $node$ Array , And use $data$ The array holds the data of all nodes in the linked list ,$count$ Record the number of valid nodes , Here the sort is the skill of index sort , Direct pair $data$ Array sorting , So reuse $dataToAddress$ You can easily know the address of the corresponding node , also $next$ It's the next node $address$, But be careful , Of the last node $next$ by -1, Manual assignment is required , At the same time, you need to record the new starting address as $data$ The address of the first node in the array . Finally, output according to the requirements

Be careful :

1、 The input node will be invalid , So we have to traverse the input nodes , Save the information of valid nodes , Test point 1 and 4 Investigate .
2、 Test point 4 Consider the case where all nodes are invalid , It's time to output "0 -1"
3、 Address reservation 5 Significant digits ,-1 Special judgment .

Submit results :

image.png

AC Code :

#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];//  Save all the data 
    int count = 0;// The number of nodes in the linked list 
    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){
            //  Record the new starting address 
            begin_address = address;
        }
    }
    //  The address of the next node of the last node is -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;
}

版权声明
本文为[Qiao Zixin]所创,转载请带上原文链接,感谢