开学第二次作业(5.14)
题目
给定一个常数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(<= 105)、以及正整数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
这题大家每个人都做过了,不过是换成了新的方法--链表而已,也没啥好说的了,不过需要注意的是,本题一开始依然是不能创建链表的,应该要先把每个节点先存储起来(用原来的老方法),之后再创建链表、反转链表,仅此而已。
以下给出代码(这次作业代码后面有彩(吐)蛋(槽))
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct Link
{
int Data;
int Adress;
Link *nx;
};
int N,K;
int f[1000050] = {0};
int Now[100050] = {0};
int Back[100050] = {0};
int Data[100050] = {0};
void CreatLink(Link *head)//创建链表
{
Link *p,*q = head;
int coun = 0;
int t = 0;
while (Back[t] != -1)
{
t = f[Back[t]];
p = new Link;
p->Data = Data[t];
p->Adress = Now[t];
q->nx = p;
q = p;
coun++;
}
N = coun; //可能有链表外的点
p->nx = NULL;
return;
}
Link* Rotation(Link *p,Link *q)//p为需要反转的前一个节点, q为需要反转最后一个结点的后一个
{
Link *r1 = p->nx; //当前反转的结点
Link *r2; //记录当前反转结点的下一个节点
Link *r3 = p->nx; //记录反转的第一个结点,用于最后要连到全部反转后的下一个结点
while (r1 != q)
{
r2 = r1->nx;
r1->nx = p->nx;
p->nx = r1;
r1 = r2;
}
r3->nx = q;
return r3;//返回反转段的最后一个结点
}
int main()
{
// freopen("xx.txt","r",stdin);
/*保存各个点*/
scanf("%d %d %d",&Back[0],&N,&K);
int i;
for (i = 1; i < N + 1; i++)
{
scanf("%d %d %d",&Now[i],&Data[i],&Back[i]);
f[Now[i]] = i;
}
/*创建链表*/
Link *head = new Link;
head->nx = NULL;
CreatLink(head);
/*反转链表*/
int T = N/K;
Link *p,*q = head;
for (i = 0; i < T; i++)
{
p = q;
int coun = 0;
while(coun < K)
{
coun++;
q = q->nx;
}
q = Rotation(p,q->nx);
}
/*输出链表 */
p = head->nx;
delete head;
while (p->nx)
{
printf("%05d %d %05d\n",p->Adress ,p->Data, p->nx->Adress);
q = p;
p = p->nx;
delete q;//C程序设计平台上面这句话留着会给你2个RE,我不知道为啥
}
printf("%05d %d -1\n",p->Adress ,p->Data);
delete p;
return 0;
}
一点比较
本题其实最好的方法并不是链表(最好啥方法我也不知道）,相比链表,用数组方式模拟链表效果更好
以下给出对比:
用链表方式:
用数组模拟:
比较点:
1.运行速度
无论是PAT上还是程序设计的编译器上,用数组模拟都更快一筹
2.使用内存
其实我没想到使用内存会差这么多...可能我自己的原因？
3.代码实现复杂程度
这个不用说了把,链表易错啊易错,而数组操作起来相对简单,只要熟练运用数组模拟的方法,肯定比链表省事啊
其实说道实现复杂程度,还有一个比较重要的原因:
我!不!会!用!链!表!debug!(这个就比较尴尬了....)
讲道理,我想过怎么弄
1.设置酱油变量专门用来给调试看当前链表指针的值
2.很low的写一个循环输出值
然后,我选择了第二种....(第二种方便不费脑丫)
所以这次作业就是用来熟悉链表而已啦,一般人也不会在oj上面随便打链表的把....
就是这样子,没神马大问题,就是对我来说,链表调试是一个痛点。