pat甲级 1052 Linked List Sorting

时间:2022-12-19 07:21:48

题意:给出N个结点的地址address,数据域data以及指针域next,然后给出链表的首地址,要求把在这个链表上的结点按data值从大到小输出。

思路:用map来保存输入的数据,用vector迭代器来保存有效数据;

          看给出的首地址元素是否存在,存在则遍历链表,将元素保存在vector中,直到地址为-1;

          将vector中的元素按data的大小由小到大排序;

          循环输出;

注意点:直接使用%05d的输出格式进行补0,-1除外;

             题目可能出现无效结点,即结点不在链表上,所以要进行过滤;

            可能所有结点都为无效结点,所以需要保存下有效结点的个数k,当k为0时输出“0  -1”;

AC代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

struct node{
    int s;
    int number;
    int next;
};

bool cmp(node a,node b){
    return a.number<b.number;
}
int main(){
    vector<node>vec;
    map<int,node>mapp;
    int n,start;
    cin>>n>>start ;
    node x;
    for(int i=0;i<n;i++){
        cin>>x.s>>x.number>>x.next;
         mapp[x.s]=x;
    }
    int k=0;
    if(mapp[start].s==start)
    for(int i=start;i!=-1;i=mapp[i].next){
        vec.push_back(mapp[i]);
        k++;
    }
    if(k){
    sort(vec.begin(),vec.end(),cmp);
    printf("%d %05d\n",k,vec[0].s);
    for(int i=0;i<vec.size()-1;i++){
        printf("%05d %d %05d\n",vec[i].s,vec[i].number,vec[i+1].s);
    }
    printf("%05d %d -1",vec[k-1].s,vec[k-1].number);
}
else printf("0 -1");
}