没想到学校的算法竞赛竟然用的也是PTA

于是，我又回来了

接着更题

好久没写了，这个题的思路也是看的网上用的比较多的方法

有几个注意的点：

• 输出的时候注意零的补齐
• 输出最后一个节点的下一个地址时不用补齐零（直接输出-1）
• 新生成的链表的下一个节点的地址注意更新

思路：构建结构体数组，结构体包含地址、数据、下一个节点的地址，数组大小为10000，输入的时候数组下标即为节点地址，由于输入个数未知，所以用vector来保存链表，遍历各个链表地址（数组下标）得到vector链表，之后对的得到的链表进行负数元素，小于K元素，大于K元素数据处理，最后输出

C++

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 //定义结构体数组，数组下标即为题中地址
 7 struct list {
 8     int address, data, next;
 9 }List[100000];
10 
11 int main() {
12     int K = 0, Address_first = 0, N = 0, i = 0;
13     bool Check[100000] = { false };                                     //用于检查节点是否被处理
14     vector<list> Arrange_list, Sort_list;
15 
16     cin >> Address_first >> N >> K;
17     for (i = 0; i < N; ++i) {
18         int tmp_address = 0;
19         cin >> tmp_address;
20         cin >> List[tmp_address].data >> List[tmp_address].next;
21         List[tmp_address].address = tmp_address;
22     }
23 
24     for (i = Address_first; List[i].next != -1; i = List[i].next) {     //利用容器将输入数据形成链表
25         Arrange_list.push_back(List[i]);
26     }
27     Arrange_list.push_back(List[i]);                                    //进行链表最后最后一位数据处理时已跳出循环，需补上
28 
29     for (i = 0; i < Arrange_list.size(); ++i) {
30         if (Arrange_list[i].data < 0) {                                 //处理链表中数据为负数的节点
31             Sort_list.push_back(Arrange_list[i]);
32             Check[Arrange_list[i].address] = true;                      //标记该节点已被处理
33         }
34     }
35 
36     for (i = 0; i < Arrange_list.size(); ++i) {                         //处理链表中数据小于K的节点
37         if (Arrange_list[i].data <= K && !Check[Arrange_list[i].address]) {
38             Sort_list.push_back(Arrange_list[i]);
39             Check[Arrange_list[i].address] = true;
40         }
41     }
42     for (i = 0; i < Arrange_list.size(); ++i) {                         //其余节点处理
43         if (!Check[Arrange_list[i].address]) {
44             Sort_list.push_back(Arrange_list[i]);
45         }
46     }
47     for (i = 0; i < Sort_list.size() - 1; i++)                          //重排节点地址
48         Sort_list[i].next = Sort_list[i+1].address;
49     Sort_list[i].next = -1;                                             //注意最后一个节点的下一个地址为-1
50     for (i = 0; i < Sort_list.size(); ++i) {
51         if (Sort_list[i].next == -1) printf("%05d %d %d\n", Sort_list[i].address, Sort_list[i].data, Sort_list[i].next);    //输出补零处理
52         else printf("%05d %d %05d\n", Sort_list[i].address, Sort_list[i].data, Sort_list[i].next);                          //最后一个节点的下一个地址特殊处理
53     }
54 
55     return 0;
56 }