02 - 선형 구조 2 리 버스 링 링크 목록

02 - 선형 구조 2
 
Reversing Linked List  (25 분)
Given a constant KK and a singly linked list LL, you are supposed to reverse the links of every KK elements on LL. For example, given LL being 1→2→3→4→5→6, if K = 3K=3, then you must output 3→2→1→6→5→4; if K = 4K=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 NN (\le 10^5≤10​5​​) which is the total number of nodes, and a positive KK (\le N≤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 NN 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
    :         ,          ,            ,     
#include
#include

#define MAXSIZE 100001 //100001=100000+1


typedef struct LNode *Ptr; 
struct LNode{
	int address;
	int data; 
	int next;
	Ptr link; //     
}list;

Ptr Reverse(Ptr head, int K,int L);
Ptr MakeList(int f_add, int next_add[],int data[],int L); 
void Attach(int a,int n_a,int data,Ptr *pRear);
void PrintList(Ptr P);


int main()
{
	int K = 0, L = 0; //K         ,L      
	int link_num = 0;//      
	int i;//     
	
	int address_tmp;//    
	int first_add;//    
	
	Ptr p,p_tmp,r_p;

	int Next[MAXSIZE] ;// address    
	int Data[MAXSIZE] ;// address    
	
	//     ,    ,     
	scanf("%d %d %d",&first_add,&L,&K);
	//            
	for(i = 0 ; i < L ; i++){ 
		scanf("%d",&address_tmp);//     
		scanf("%d %d",&Data[address_tmp],&Next[address_tmp]); 			
	}
 
 	//       
	p = MakeList(first_add,Next,Data,L);
	
	//     ******************    *****************************
	if(K<=L){//K<=L      
		for(i = 0; i < (L/K); i++){
			r_p = Reverse(p,K,L);	
			p_tmp ->link = r_p;//        
			p_tmp ->next =  r_p->address;
			for(int j = 0; j < 	K; j++ ){
	// p                 (           )  
				p_tmp = p_tmp->link;
			}
		} 
	}
	//************************************************************
	
	//    
	PrintList(p_tmp); 
	 
	return 0;
} 
 
 
Ptr MakeList(int f_add, int next_add[],int data[],int L)
{
	Ptr P , Rear, t; 
	int t_L = L;
	int a,n_a,d,tmp_n_a;
	int i;
	
	P = (Ptr)malloc(sizeof(struct LNode));//      
	P->link = NULL; 
	Rear = P;
	
	//      
	a = f_add;
	d = data[a];
	n_a = next_add[a]; 
	Attach(a,n_a,d,&Rear); 
	t_L--; 
			
	while(t_L--){//       
		a = n_a;
		d = data[a];
		n_a = next_add[a];
		Attach(a,n_a,d,&Rear); 
	}
	//t = P;P=P->link;free(t);//         
	return P; 
}

void Attach(int a,int n_a,int data,Ptr *pRear)
{
	Ptr P;
	P = (Ptr)malloc(sizeof(struct LNode));
	
	P->address = a;
	P->data = data;
	P->next = n_a;
	P->link = NULL;
	
	(*pRear)->link = P;
	*pRear = P;	
}
 
Ptr Reverse(Ptr head, int K,int L)
{
	int cnt = 1;
	Ptr new_, old,tmp;
	//       new_,        ,new_ = head->link; 
	new_ = head->link;
	//            old, old = new_->link; 
	old = new_->link;
	while(cnt < K){
		//      tmp,   old     ,tmp = old->link;
		tmp = old->link;
		// old     new_, old->link = new_;  
		old->link =new_;
		//old       new_     
		old->next = new_->address;
		//  ,old         new_        new_,
		//      old           new_,new_ = old;  		
		new_ = old;
		//    old    tmp,old = tmp; 
		old = tmp;
		cnt ++; 
	} 
	///                           
	head->link->link = old;
	
	if(old != NULL){//       
		head->link->next = old -> address;	
	}
	else{
		head->link->next = -1;//          
	}
	return new_; 
}

void PrintList(Ptr P)
{
	while(P){
		if(P->next == -1) {//             
			printf("%.5d %d %d
",P->address,P->data,P->next); } else{ printf("%.5d %d %.5d
",P->address,P->data,P->next); // ,%.5 5 , 0 :22, :00022 } P = P->link; } }

좋은 웹페이지 즐겨찾기