PAT-乙-1075 1075 链表元素分类 (25 分)
代码
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000;
struct node {
int id;
int data;
int next;
};
int main() {
int start, n, k;
scanf("%d %d %d", &start, &n, &k);
node nodeArray[MAX];
for(int i=0; i<n; i++) {
int id, data, next;
scanf("%d %d %d", &id, &data, &next);
nodeArray[id].id = id;
nodeArray[id].data = data;
nodeArray[id].next = next;
}
//original order
vector<node> v;
int now = start;
for(int i=0; i<n; i++) {
if(now!=-1) { //这个if判断条件很关键!
v.push_back(nodeArray[now]);
now = nodeArray[now].next;
}
}
//classify order
vector<node> v2;
for(int i=0; i<v.size(); i++){
node tmp = v.at(i);
if(tmp.data<0){
v2.push_back(tmp);
}
}
for(int i=0; i<v.size(); i++){
node tmp = v.at(i);
if(tmp.data>=0 && tmp.data<=k){
v2.push_back(tmp);
}
}
for(int i=0; i<v.size(); i++){
node tmp = v.at(i);
if(tmp.data>k){
v2.push_back(tmp);
}
}
for(int i=0; i<v2.size()-1; i++) {
node t = v2.at(i);
node tNext = v2.at(i+1);
printf("%05d %d %05d\n", t.id, t.data, tNext.id); //直接输出的下一个节点的id,偷懒了。
}
printf("%05d %d -1\n", v2.at(v2.size()-1).id, v2.at(v2.size()-1).data);
return 0;
}
注解
1、此题的数据结构与乙级1025相同。
2、按链表的原始顺序push到v中。
3、按题目给定的顺序将v中的元素push到v2中。
4、按v2的顺序输出元素。主要是注意next.id如何输出?这里直接输出的下一个节点的id,而不是真正改变了node.next值,偷懒了。后续看看如何优化?