PAT B1075 链表元素分类(C++)

PAT甲级目录 | PAT乙级目录

题目描述

B1075 链表元素分类

解题思路

将链表存放到数组中,遍历链表,将对应范围的值加入不同的可变数组中,最后合并数组,顺序输出。

易错点

  • 最后一个结点的 next 地址应当输出 -1
  • 地址的格式为五位数

也许陌生的知识点

  • vector<int> ans;
    • 实现变长数组,元素类型可任意指定
      • ans.push_back(num[i])往变长数组末尾中添加一个元素
      • ans.pop_back()删除变长数组中最后一个元素
    • 需要的头文件:vector

代码示例:

  • 方法一:利用数组存放链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <vector>
using namespace std;
int main() {
int A[100010], D[100010], n, k, pos, now, next, temp;
vector<int> first, second, last;
scanf("%d %d %d", &pos, &n, &k);
for(int i = 0; i < n; i++){
scanf("%d %d %d",&now, &temp, &next);
A[now] = next;
D[now] = temp;
}
while(pos != -1){ // 遍历链表
if(D[pos] < 0) first.push_back(pos);
else if(D[pos] > k) last.push_back(pos);
else second.push_back(pos);
pos = A[pos];
}
for(int i = 0; i < second.size(); i++) first.push_back(second[i]);
for(int i = 0; i < last.size(); i++) first.push_back(last[i]);
for(int i = 0; i < first.size(); i++){
if(i == first.size() - 1) printf("%05d %d -1", first[i], D[first[i]]);
else printf("%05d %d %05d\n", first[i], D[first[i]], first[i + 1]);
}
return 0;
}
  • 方法二:利用结构体数组存储链表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <vector>
    #include <cstdio>
    using namespace std;
    struct Node{
    int address, data, next;
    }LNode[100010];
    int main(){
    vector<int> first, second, last;
    int now, n, k, t;
    scanf("%d %d %d", &now, &n, &k);
    for(int i = 0; i < n; i++){
    scanf("%d", &t);
    LNode[t].address = t;
    scanf("%d %d", &LNode[t].data, &LNode[t].next);
    }
    while(now != -1){
    if(LNode[now].data < 0)first.push_back(now);
    else if(LNode[now].data > k) last.push_back(now);
    else second.push_back(now);
    now = LNode[now].next;
    }
    for(int i = 0; i < second.size(); i++) first.push_back(second[i]);
    for(int i = 0; i < last.size(); i++) first.push_back(last[i]);
    for(int i = 0; i < first.size(); i++){
    if(i == first.size() - 1) printf("%05d %d -1", first[i], LNode[first[i]].address);
    else printf("%05d %d %05d\n", first[i], LNode[first[i]].address, first[i + 1]);
    }
    return 0;
    }