日常，21分共25分
1. 有多余结点不在链表上.............................................段错误
2.最大N,最后剩K-1不反转 ......................................... 运行超时
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.
Then N lines follow, each describes a node in the format:
Address Data Nextwhere
Addressis the position of the node,Datais an integer, andNextis 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 33218Sample Output:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
我的AC：
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct LNode *List;
struct LNode{
int fadr; //first adress
int data;
int nadr;
List Next;
};
List read_link();
void attach(int f, int d, int n, List* PtrL);
List reverse_link(List PtrL);
void Reverse(List *PtrL, List *rear, int *a);
List search_adress(int adress, List PtrL);
void Print_link(List PtrL);
void Free_link(List PtrL);
int main()
{
List P1, P;
P1 = read_link();
P = reverse_link(P1);
Print_link(P);
Free_link(P1);
Free_link(P);
return 0;
}
List read_link()
{
int first, length, key;
int fadr, data, nadr;
List P, rear;
scanf("%d%d%d", &first, &length, &key);
P = (List)malloc(sizeof(struct LNode));
P ->Next = NULL;
P ->fadr = first;
P ->data = length;
P ->nadr = key;
rear = P;
while(length--){
scanf("%d%d%d", &fadr, &data, &nadr);
attach(fadr, data, nadr, &rear);
}
return P;
}
void attach(int f, int d, int n, List* PtrL)
{
List A1;
A1 = (List)malloc(sizeof(struct LNode));
A1 ->fadr = f;
A1 ->data = d;
A1 ->nadr = n;
A1 ->Next = NULL;
(*PtrL) ->Next = A1;
*PtrL = A1;
}
List reverse_link(List PtrL)
{
List Link, P;
List new_link, rear, T;
int adress = PtrL ->fadr;
int a[PtrL ->data];
new_link = (List)malloc(sizeof(struct LNode));
new_link ->Next = NULL;
rear = new_link;
Link = PtrL ->Next;
for(int i = 0; i < PtrL ->data; i++)
{
P = search_adress(adress, Link);
a[i] = P ->fadr;
adress = P ->nadr;
}
Reverse(&PtrL, &rear, a);
T = new_link;
new_link = new_link ->Next;
free(T);
return new_link;
}
void Reverse(List *PtrL, List *rear, int *a)
{
List P;
int flag = 0, Temp;
int j = (*PtrL)->nadr -1;
bool sign = false;
while(flag != (*PtrL)->data - 1){
if((*PtrL)->nadr != 1 && j % (*PtrL)->nadr == 0){
P = search_adress(a[j], (*PtrL)->Next);
Temp = j;
if((*PtrL) ->data - (flag + 1) >= (*PtrL)->nadr){
j = flag + ((*PtrL)->nadr);
}else{
j = flag + 1;
sign = true;
}
attach(a[Temp], P->data, a[j], rear);
flag++;
}
P = search_adress(a[j], (*PtrL)->Next);
if(sign || (*PtrL)->nadr == 1){
attach(a[j], P->data, a[j + 1], rear);
j ++;
}else{
attach(a[j], P->data, a[j-1], rear);
j --;
}
flag++;
}
P = search_adress(a[j], (*PtrL)->Next);
attach(a[j], P->data, -1, rear);
}
List search_adress(int adress, List PtrL)
{
if(!PtrL){
return NULL;
}
while(PtrL)
{
if(PtrL ->fadr == adress)
return PtrL;
PtrL = PtrL ->Next;
}
return NULL;
}
void Print_link(List PtrL)
{
if(!PtrL){
return ;
}
while(PtrL->Next){
printf("%05d %d %05d\n", PtrL->fadr, PtrL ->data, PtrL ->nadr);
PtrL = PtrL ->Next;
}
printf("%05d %d %d\n", PtrL->fadr, PtrL ->data, PtrL ->nadr);
return ;
}
void Free_link(List PtrL)
{
List T;
if(!PtrL){
return ;
}
while(PtrL){
T = PtrL;
PtrL = PtrL ->Next;
free(T);
}
}