数组模拟单链表(y总基础班讲的数组模拟)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
const int maxn=1e6+10;

vector<P> v;
int e[maxn],ne[maxn];

int main(){
    int n,head,a,b,c;
    bool flag=false;
    scanf("%d%d",&n,&head);
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        e[a]=b,ne[a]=c;
        if(a==head) flag=true;
    }
    if(!flag){
        puts("0 -1");
        return 0;
    }
    for(int i=head;i!=-1;i=ne[i])
        v.push_back({e[i],i});
    sort(v.begin(),v.end());
    printf("%d %05d\n",(int)v.size(),v[0].second);
    n=(int)v.size();
    for(int i=0;i<n;i++){
        if(i==n-1) printf("%05d %d -1\n",v[i].second,v[i].first);
        else printf("%05d %d %05d\n",v[i].second,v[i].first,v[i+1].second);
    }
    return 0;
}

结构体+哈希表(y总PAT课上讲的)

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

struct node{
    string ad;
    int val;
    string next;
    bool operator < (const node& a) const{
        return val<a.val;
    }
};
vector<node> v;
unordered_map<string,node> mp;


int main(){
    int n,val;
    char h[10],nex[10];
    scanf("%d%s",&n,h);
    string head(h);
    for(int i=0;i<n;i++){
        scanf("%s%d%s",h,&val,nex);
        string ad(h),next(nex);
        mp[ad]={ad,val,next};
    }
    for(string i=head;i!="-1";i=mp[i].next) v.push_back(mp[i]);
    printf("%d ",v.size());
    if(v.empty()) puts("-1");
    else{
        sort(v.begin(),v.end());
        printf("%s\n",v[0].ad.c_str());
        for(int i=0;i<v.size();i++){
            if(i==v.size()-1)
                printf("%s %d -1\n",v[i].ad.c_str(),v[i].val);
            else printf("%s %d %s\n",v[i].ad.c_str(),v[i].val,v[i+1].ad.c_str());
        }
    }
    return 0;
}