데이터 구조 02 - 선형 구조 3 리 버스 링 링크 목록
10952 단어 데이터 구조데이터 구조 (저장 성)
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 (≤10 5 ^5 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
분석 하 다.
제목 은 한 조 의 형식 에
Address data next
의 결점 을 주 는 것 이다. 요구 에 따라 역순 출력 을 먼저 관찰 하고 역순 후에 변 하지 않 는 곳 은 앞의 두 조 의 데이터 이다. 즉, 모든 결점 의 Address 와 data 는 변 하지 않 고 계속 관찰 하 는 것 이다. 사실은 현재 결점 의 next 는 다음 결점 의 address 이다. 우 리 는 address 와 data 를 저장 하고 그들의 관 계 를 나타 내 는 것 을 고려 해 야 한다.배열 Data [address] = data 를 사용 할 수 있 습 니 다. 마찬가지 로 next 와 Address 도 이런 형식 으로 저장 할 수 있 습 니 다. 즉, next [address] = next 는 address 를 통 해 우 리 는 data [] 배열 을 통 해 대응 하 는 data 를 찾 을 수 있 고 next [] 배열 을 통 해 대응 하 는 next 를 찾 아 저장 한 후에 우 리 는 전체 링크 를 '정리' 할 수 있 습 니 다.제 시 된 first node 는 첫 번 째 address 입 니 다. next [first node] 는 다음 노드 의 address 입 니 다. 한 배열 list [] 로 매번 만 나 는 address 를 기록 합 니 다. 여기까지 우 리 는 address 에 따라 다른 데 이 터 를 찾 을 수 있 는 관계 배열 도 있 고 address 를 순서대로 기록 할 수 있 는 배열 도 있 습 니 다. 문 제 는 '반전 링크' 에서 '반전 Address' 로 간략화 합 니 다.K 개의 노드 를 구간 으로 하여 list [] 배열 에 저 장 된 Address 를 반전 시 키 고 address 와 다른 데이터 의 관계 에 따라 링크 를 완전 하 게 출력 할 수 있 습 니 다!#include
#include
#define MaxSize 100005
using namespace std;
int main(){
int Data[MaxSize];
int Next[MaxSize];
int list[MaxSize];
int FirstAdd,N,K;
scanf("%d %d %d",&FirstAdd,&N,&K);
for(int i=0;i<N;i++){
int tmpAdd,tmpData,tmpNext;
scanf("%d %d %d",&tmpAdd,&tmpData,&tmpNext);
Data[tmpAdd] = tmpData;
Next[tmpAdd] = tmpNext;
}
int sum=0; //
while(FirstAdd!=-1){ // -1
list[sum++] = FirstAdd; // Address
FirstAdd = Next[FirstAdd]; //
}
for(int i=0;i<sum-sum%K;i+=K){ // K
for(int j=0;j<K/2;j++){ //
int t = list[i+j];
list[i+j] = list[i+K-j-1];
list[i+K-j-1] = t;
}
}
for(int i=0;i<sum-1;i++)
printf("%05d %d %05d
",list[i],Data[list[i]],list[i+1]);
printf("%05d %d -1
",list[sum-1],Data[list[sum-1]]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.