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?(≤10?5??) 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);
}
