PAT 1075 链表元素分类

本文主要是介绍PAT 1075 链表元素分类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：请点击
思路：定义结构体，其中一个结构体node，用下标表示该结点的地址，可直接访问地址得到结点相关信息，且保证每一类元素内部的顺序不变；另一个结构体是排好序待输出的。3次循环，每次按题要求找到一类元素，最后输出
注1 要注意结点有可能是孤立节点，即该结点与其他结点不是一个链表内的。测点4可能与此有关。
AC代码

#include<iostream>
using namespace std;
struct Node{int add;//结点地址 int data;//结点保存的数据 int next;//下一结点的地址 
};
Node node[500000]; //用下标表示该结点的地址 
int main(){int iniAdd,N,K;cin>>iniAdd>>N>>K;Node sort[N];//排序后待输出的结点 for(int i=0;i<N;i++){int add;cin>>add;node[add].add=add;cin>>node[add].data>>node[add].next;}int pos=iniAdd,l=0,cnt=0;while(pos!=-1){//先找到负值元素if(node[pos].data<0){if(cnt) sort[l-1].next=node[pos].add;sort[l].add=node[pos].add;sort[l].data=node[pos].data;cnt=1;l++;}pos=node[pos].next;}pos=iniAdd;while(pos!=-1){//找到在[0,K]区间内的元素if(node[pos].data>=0&&node[pos].data<=K){sort[l-1].next=node[pos].add;sort[l].add=node[pos].add;sort[l].data=node[pos].data;l++;}pos=node[pos].next;}pos=iniAdd;while(pos!=-1){//找到大于K的if(node[pos].data>K){sort[l-1].next=node[pos].add;sort[l].add=node[pos].add;sort[l].data=node[pos].data;l++;}pos=node[pos].next;}sort[l-1].next=-1;for(int i=0;i<l;i++){if(sort[i].next!=-1)printf("%05d %d %05d\n",sort[i].add,sort[i].data,sort[i].next);else printf("%05d %d %d\n",sort[i].add,sort[i].data,sort[i].next);}return 0;
}