乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1075 链表元素分类

问题分析

• 题设给定链表头节点地址, 总节点个数, 元素分类阈值, 要求按照指定的方式对链表元素进行分类排序。
• 指定方式为:
  • 将元素的值按照"大于0", “大于等于0且小于等于给定阈值”, "大于给定阈值"分为三组;
  • 分组中的元素保持在原始链表中的相对顺序;
  • 最后按照指定格式输出分类排序后的各个节点信息。
• 由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
• 比如: 将各个链表元素按照连接顺序放入连续的数组中, 然后给定规则对数组元素进行排序, 最后直接按照要求输出。
• 给定规则描述为: 两个元素处于同一取值区间时相对位置不变, 如果处于不同区间, 则按照数值大小递增排序。

完整描述步骤

1. 获取输入: 链表头节点, 节点个数, 区间阈值
2. 按照链表连接顺序, 将各个节点放入连续数组中, 并计算链表长度
3. 自定义排序规则:
   • 如果两个元素都小于0, 则两个元素顺序不变;
   • 如果两个元素都大于等于0且小于等于给定阈值, 则两个元素顺序不变;
   • 如果两个元素都大于给定阈值, 则两个元素顺序不变;
   • 否则, 按照元素值递增顺序排列两个元素;
4. 按照自定义规则对连续数组进行排序
5. 按照排序后的数组顺序输出各个节点的地址, 数据以及节点所在位置的下一个位置的元素的地址:
   • 如果是最后一个元素, 则输出"{该元素的地址} {数据} -1"

伪代码描述

1. get input: head, node_amount, threshold
2. put linked list into array, and calcualte length of array
3. define rule of array sorting:
   • if A < 0 and B < 0: not change order bewteen A and B;
   • if 0 <= A <= threshold and 0 <= B <= threshold: not change order bewteen A and B;
   • if A > threshold and B > threshold: not change order bewteen A and B;
   • else: sort A and B as value ascending
4. sorted array by defined sorting rule
5. for index in range(0, length(array)):
   • if index != length(array) - 1:
     • print(“{array[i].address} {array[i].data} {array[i+1].address}”);
   • else:
     • print(“{array[i].address} {array[i].data} -1”);

完整提交代码

/*
# 问题分析
题设给定链表头节点地址, 总节点个数, 元素分类阈值, 要求按照指定的方式对链表元素进行分类排序。
指定方式为: 将元素的值按照"大于0", "大于等于0且小于等于给定阈值", "大于给定阈值"分为三组, 分组中的元素保持在原始链表中的相对顺序, 最后按照指定格式输出分类排序后的各个节点信息。
由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
比如: 将各个链表元素按照连接顺序放入连续的数组中, 然后给定规则对数组元素进行排序, 最后直接按照要求输出。
给定规则描述为: 两个元素处于同一取值区间时相对位置不变, 如果处于不同区间, 则按照数值大小递增排序。# 完整描述步骤
1. 获取输入: 链表头节点, 节点个数, 区间阈值
2. 按照链表连接顺序, 将各个节点放入连续数组中, 并计算链表长度
3. 自定义排序规则:- 如果两个元素都小于0, 则两个元素顺序不变;- 如果两个元素都大于等于0且小于等于给定阈值, 则两个元素顺序不变;- 如果两个元素都大于给定阈值, 则两个元素顺序不变;- 否则, 按照元素值递增顺序排列两个元素;
4. 按照自定义规则对连续数组进行排序
5. 按照排序后的数组顺序输出各个节点的地址, 数据以及节点所在位置的下一个位置的元素的地址:- 如果是最后一个元素, 则输出"{该元素的地址} {数据} -1"# 伪代码描述
1. get input: head, node_amount, threshold
2. put linked list into array, and calcualte length of array
3. define rule of array sorting:- if A < 0 and B < 0: not change order bewteen A and B;- if 0 <= A <= threshold and 0 <= B <= threshold: not change order bewteen A and B;- if A > threshold and B > threshold: not change order bewteen A and B;- else: sort A and B as value ascending
4. sorted array by defined sorting rule
5. for index in range(0, length(array)):- if index != length(array) - 1:- print("{array[i].address} {array[i].data} {array[i+1].address}");- else:- print("{array[i].address} {array[i].data} -1");
*/# includetypedef struct node{int address;int data;int next;
} node;node nodes[100001];
int threshold;int cmp(const void* a, const void* b){node node_a = *(node*)a;node node_b = *(node*)b;int A = node_a.data;int B = node_b.data;if (A < 0 && B < 0){return 0;}if (A > threshold && B > threshold){return 0;}if (0 <= A && A <= threshold && 0 <= B && B <= threshold){return 0;}return A > B;
}int main(){int head, node_amount;scanf("%d %d %d", &head, &node_amount, &threshold);int address, data, next;for (int i = 0; i < node_amount; i++){scanf("%d %d %d", &address, &data, &next);nodes[address].address = address;nodes[address].data = data;nodes[address].next = next;}int valid_node_amount = 0;node valid_nodes[node_amount];int current_address = head;while (current_address != -1){valid_nodes[valid_node_amount] = nodes[current_address];valid_node_amount++;current_address = nodes[current_address].next;}qsort(valid_nodes, valid_node_amount, sizeof(node), cmp);for(int i = 0; i < valid_node_amount; i++){if (i == valid_node_amount-1){printf("%05d %d -1\n", valid_nodes[i].address, valid_nodes[i].data);} else {printf("%05d %d %05d\n", valid_nodes[i].address, valid_nodes[i].data, valid_nodes[i+1].address);}}return 0;
}