1074 Reversing Linked List (25 分) 反转列表 PAT甲级
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了1074 Reversing Linked List (25 分) 反转列表 PAT甲级，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2841字，纯文字阅读大概需要5分钟。
内容图文
原题:
给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10^5)以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 ?1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
题目小结：
本题考查静态链表的使用。解题过程参考《算法笔记——上机训练实战指南》
有以下几个注意事项：
1、题目给出的结点并不都在链表内，有些是游离的，对结点的order赋值100010，正常情况下不会出现如此大的序号，所以排序时会将无效结点排在数组后面。
2、address和data可以视为绑定的，输出结点时需要考虑的是next。
3、最后输出的时候需要分多种情况考虑，注意%05d会使-1的输出出现问题。
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;//定义数组的最大容量，同时也是order的默认无效值
struct Node {//结点的结构体定义
int address,data,next;
int order;//order存放结点在所给出链表里的顺序
Node() {
order = maxn;//这里是为了方便结点比较时，无效结点排在后面
}
}node[maxn];
bool cmp(Node a, Node b) {//比较函数，order小的放前面
return a.order < b.order;
}
int main(){
int begin,n,k,address,count=0;//输入起点地址,总的结点个数，每个翻转模块里数的个数
scanf("%d %d %d", &begin, &n,&k);
for (int i = 1; i <= n; i++) {
scanf("%d", &address);
scanf("%d %d", &node[address].data, &node[address].next);
node[address].address = address;
}//在数组address的位置存放地址为address的结点
for (int pos = begin; pos!=-1; pos=node[pos].next) {//为每个节点的order赋值
node[pos].order = count++;
}
sort(node, node + maxn, cmp);//按照order的大小排序
n = count;
for (int i = 0; i < n / k; i++){//共有(n\k)个完整的组进行倒转
for (int j = (i + 1) * k - 1; j > i * k; j--) {//输出某个完整块中的前k-1个结点
printf("%05d %d %05d\n", node[j].address, node[j].data, node[j - 1].address);
}
printf("%05d %d ", node[i * k].address, node[i * k].data);//输出某个块最后一个结点的前两个信息
if (i < n / k - 1) {//如果这个块不是最后一个块
printf("%05d\n", node[(i + 2) * k - 1].address);
}
else {//如果这是最后一个块
if (n % k == 0) {//是最后一个块且刚好整分，所以该结点的next肯定是-1
printf("-1\n");
}
else {//输出剩下的结点
printf("%05d\n", node[(i + 1) * k].address);
for (int i = n / k * k; i < n; i++) {
printf("%05d %d ", node[i].address, node[i].data);
if (i < n - 1) {
printf("%05d\n", node[i + 1].address);
}
else {
printf("-1\n");
}
}
}
}
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的1074 Reversing Linked List (25 分) 反转列表 PAT甲级全部内容，希望文章能够帮你解决1074 Reversing Linked List (25 分) 反转列表 PAT甲级所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。