1025 反转链表 (25 分) c语言实现+测试点

1025 反转链表 (25 分) c语言实现+测试点,第1张

1025 反转链表 (25 分) c语言实现+测试

题目

1025 反转链表 (25 分)

给定一个常数 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
typedef struct shuju
    {int address;     
     int data;        
     int next;        
     int before;      
    }stu;
int main(){
    stu a[100001];      
    stu *b[100001];    
    int add,ad,n,k,i,data,next,l;
    scanf("%d %d %d",&add,&n,&k);    
    for(i=0;il)       
                    {if(i!=l)    
                        printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i]->next);
                     else
                         printf("%05d %d %dn",b[i-x]->address,b[i-x]->data,b[i]->next);
                    }
                 else
                    {printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i-1+k]->next);
                    }
                }
             else
                printf("%05d %d %05dn",b[i-x]->address,b[i-x]->data,b[i-x]->before);
            }
        }
        i=i-k+1;
    for(;i<=l;i++)     
        if(b[i]->next==-1)
            printf("%05d %d %dn",b[i]->address,b[i]->data,b[i]->next);
        else
            printf("%05d %d %05dn",b[i]->address,b[i]->data,b[i]->next);
    return 0;
}

 测试点分析

    测试点0是总长度不到2*K的常规项,此项错误说明程序反转存在问题。

    测试点1 2 3 4要注意最后输出的-1,且不要重复输出,似乎使长度为K的整数倍的测试例。

    测试点5是一个比较大的测试例(可以看下面图片的测试结果,运行内存和时间相对都比较大),这个如果超时说明代码不够简洁,过于复杂。

    测试点6的关键在于不要把节点总个数当作从起始节点开始的长度,即起始节点不一定是表头。

注意点 

1.题目要求每K个反转,并不是前四个反转。

2.最后若不足K个,不反转。

3.注意最后一项的输出,-1不要输出成-10001

4.不要把节点总个数当作从起始节点开始的长度,起始节点不一定是表头。

 改了几次勉强过了,测试点6审题问题着实费了不少时间。

 但这个时候有小伙伴就要说了,你这也没真的反转啊,只是这么输出了而已。但其实只要在每一个printf的地方用另一个结构体组储存就可以,然后最后一起输出也是一样的,因为是做pat,只要求最后的输出,所以干脆偷懒啦。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5711668.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存