线性结构3 Reversing Linked List"/>
算法 线性结构3 Reversing Linked List
全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案汇总
题目:Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
给定一个常数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。
输入规格:
每个输入文件包含一个测试用例。对于每种情况,第一行包含第一个节点的地址、节点总数的正N(<105)和要反转的子列表的长度的正K(<N)。节点的地址是一个5位非负整数,空值用-1表示。
Then N lines follow, each describes a node in the format:
Address Data Next
where Address
is the position of the node, Data
is an integer, and Next
is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
解答:
解法1:
这里还是先说一下用链表怎么实现的:首先得通过遍历,把数据按照地址连起来。同时保存每个数据点所在的位置。
然后反转。反转完以后,注意把链表上每个结构体的指向进行修改(注意每个数据的地址是肯定不会变的,但是它指向的下一个数据的地址是会变的)
上面也说了,这种做法得不偿失,主要得不偿失之处在于通过遍历把数据按照地址连起来,超级浪费时间,暂时没找到什么好办法。
解法2:
这是现在我要介绍的第2种解法:
已知结点是五位的非负数,因为一个节点包含三个信息:当前位置,数值,下一个位置。所以我们直接建立两个大数组,用索引代表当前位置,并使用这两个数组来存,一个存它的数据大小,另一个存它的下一个地址:
#include<iostream>
#define MaxSize 100001
using namespace std;
int main() {int data[MaxSize];int link[MaxSize];int head, N, K;cin >> head >> N >> K;for (int i = 0;i<N;i++) {int address, dataPoint, linkPoint;cin >> address >> dataPoint >> linkPoint;data[address] = dataPoint;link[address] = linkPoint;}system("pause");return 0;
}
然后考虑一下反转以后的效果:
为了方便反转,我们直接用另一个数组给它排序:
注意这里的思路是把地址记录下来(因为如果地址是连续的,反转地址以后也可以直接把表当成数组使用)
int count = 0; //计数int sortList[MaxSize]; //最大情况while (head != -1) {sortList[count++] = head;head = link[head];}//注意这个时候的链表count 是 等于N的。
然后排序:
//注意这里,如果加到大于count了,说明超过了。剩下的几个数据不再反转for (int i = 0; i<count-count%K ;i += K) { //反转链表for (int j = 0;j<K / 2;j++) { int t = sortList[i + j];// 当K = 4, 0要和3交换,1要和2交换,算一下可知相当于 i+j索引元素与i+K -j-1 进行交换sortList[i + j] = sortList[i + K - j - 1];sortList[i + K - j - 1] = t;}}
最后输出就行了:注意输出格式有坑。
//输出格式这里是个大坑!for (int i = 0;i<count - 1;i++)//cout << sortList[i] <<" "<< data[sortList[i]] <<" "<< sortList[i + 1]<<endl;printf("%05d %d %05d\n", sortList[i], data[sortList[i]], sortList[i + 1]);//cout << sortList[count - 1] <<" "<< data[sortList[count - 1]]<<" " << -1<<endl;/**/printf("%05d %d -1\n", sortList[count - 1], data[sortList[count - 1]]);
完整代码:
#include<iostream>
using namespace std;
#define MaxSize 100001
#include<stdio.h>int main() {int data[MaxSize];int link[MaxSize];int head, N, K;cin >> head >> N >> K;for (int i = 0;i<N;i++) {int address, dataPoint, linkPoint;cin >> address >> dataPoint >> linkPoint;data[address] = dataPoint;link[address] = linkPoint;}int count = 0; //计数int sortList[MaxSize]; //最大情况while (head != -1) {sortList[count] = head;head = link[head];count++;}//注意这个时候的链表count 是 等于N的。//注意这里,如果加到大于count了,说明超过了。剩下的几个数据不再反转//比如count=14 ,K=4,则反转组为 0-3 4-7 8-11 不反转组为12-13//所以i必须要加到8以后,再加4则for判断失败退出循环。即小于14 - 2判断正确。for (int i = 0; i<count-count%K ;i += K) { //反转链表for (int j = 0;j<K / 2;j++) { int t = sortList[i + j];// 当K = 4, 0要和3交换,1要和2交换,算一下可知相当于 i+j索引元素与i+K -j-1 进行交换sortList[i + j] = sortList[i + K - j - 1];sortList[i + K - j - 1] = t;}}//输出格式这里是个大坑!for (int i = 0;i<count - 1;i++)//cout << sortList[i] <<" "<< data[sortList[i]] <<" "<< sortList[i + 1]<<endl;printf("%05d %d %05d\n", sortList[i], data[sortList[i]], sortList[i + 1]);//cout << sortList[count - 1] <<" "<< data[sortList[count - 1]]<<" " << -1<<endl;/**/printf("%05d %d -1\n", sortList[count - 1], data[sortList[count - 1]]);system("pause");return 0;
}
编译完全通过。
解法3:我还是尝试用链表做了一下,但是最终也只能归结到类似方法二按照数组的方法,建立了100000个结构体的数组。然后进行反转操作,这样的方法不但没有节约内存反而增加了程序复杂度。
总之,我一直没有想到什么很好的纯链表反转的解决思路。看了一些别人写的方法也都是建立大数组。此题待定,希望以后能有更好的方法。(不过既然用五位数来存地址了,可能冥冥之中告诉了题目就是要用五位数的数组吧)
更多推荐
算法 线性结构3 Reversing Linked List
发布评论