02-线性结构3 Reversing Linked List （25 分）
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 Lbeing 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 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
Code:
#include <stdio.h>
#define MAX 100000
typedef struct{
int data;
int next;
}Node;
//计算在数组中的元素个数
int CountNum(Node *list,int plist);
//反转元素
int Reverse(Node *list,int num,int plist,int k);
//打印元素
void Print(Node *list,int plist);
int main(){
Node list[MAX];
int plist,n,k;
scanf("%d%d%d",&plist,&n,&k);
int addr,data,next;
while(n>0){
scanf("%d%d%d",&addr,&data,&next);
list[addr].data=data;
list[addr].next=next;
n--;
}
int num=CountNum(list,plist);
int newplist=Reverse(list,num,plist,k);
Print(list,newplist);
return 0;
}
int Reverse(Node *list,int num,int plist,int k){
int preNode,curNode,nextNode;
preNode=-1;
curNode=plist;
nextNode=list[curNode].next;
int head=-1,lasthead;
for (int i=0;i<num/k;i++){
lasthead=head;
head=curNode;
for(int j=0;j<k;j++){
list[curNode].next=preNode;
preNode=curNode;
curNode=nextNode;
nextNode=list[curNode].next;
}
if (i==0) plist=preNode;
else list[lasthead].next=preNode;
}
list[head].next = curNode; //不用逆转的剩余部分加上
return plist;
}
int CountNum(Node *list,int plist){
int c=1;
while((plist=list[plist].next)!=-1) c++;
return c;
}
void Print(Node *list,int plist){
while((list[plist].next)!=-1){
printf("%05d %d %d\n",plist,list[plist].data,list[plist].next);
plist = list[plist].next;
}
printf("%05d %d %d\n",plist,list[plist].data,list[plist].next);
}
