PTA 02 - 선형 구조 3 리 버스 링 링크 목록 문제 분석

PTA - mooc 전체 문제 분석 및 AC 코드 라 이브 러 리: PTA (맞 춤 형 A) - 절강대학 교 중국 대학 mooc 데이터 구조 전 AC 코드 와 문제 분석 (C 언어)
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) 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

제목 해석:
단일 체인 테이블 을 뒤 집 고 체인 테이블 의 길이 N 과 상수 K 를 지정 합 니 다. 체인 테이블 에 있 는 K 개의 요소 마다 체인 테이블 을 뒤 집 습 니 다. 마지막 으로 K 개의 순 서 를 유지 하기 에는 부족 합 니 다.
입력 설명:
첫 번 째 줄 의 세 개 수 는 체인 헤더 의 주소, 링크 길이 N 과 몇 개의 요소 가 뒤 집 히 는 K 값 을 나타 낸다.
그 다음 에 N 줄 에 이 어 모든 줄 은 하나의 링크 노드 정 보 를 표시 합 니 다. 여기 서 제 시 된 링크 노드 순 서 는 무질서 합 니 다.각 줄 의 노드 정 보 는 세 개의 숫자 가 있 는데 그 다음은 이 노드 주소, 노드 값 과 연 결 된 다음 요소 주소 (마지막 요소 라면 - 1) 이다.
출력 설명:
링크 를 뒤 집 은 순서대로 출력 합 니 다. 각 노드 는 한 줄 을 차지 하고 출력 형식 은 입력 한 노드 형식 과 같 습 니 다.
제목 분석:
이 문 제 는 다음 과 같은 몇 단계 로 나 눌 수 있다.

모든 노드 를 배열 에 읽 기

모든 노드 를 연결 합 니 다

K 개 원소 마다 뒤 집기

출력 결과 링크

이 문 제 는 몇 가지 함정 이 있 으 니 주의해 야 한다.

입력 한 링크 노드 정 보 는 특정한 노드 의 다음 연결 위 치 를 모든 주어진 입력 에서 찾 을 수 없 을 수 있 습 니 다. 이때 실제 링크 수 는 주어진 링크 길이

보다 작 습 니 다.

두 번 째 단계 에서 특정한 결점 을 찾 을 때마다 다음 결점 은 모든 것 을 탐색 할 때 시간 을 초과 합 니 다. 즉, 시간 복잡 도 는 O (n ^ 2) 가 될 수 없습니다.모든 노드 의 주 소 는 성형 수로 표시 되 기 때문에 하나의 큰 배열 을 미리 설명 하고 모든 노드 를 해당 하 는 색인 위치 에 저장 할 수 있다. 그러면 특정한 노드 의 다음 노드 를 찾 는 시간 복잡 도 는 O (1) 이 고 두 번 째 단계 의 시간 복잡 도 는 O (n)

로 변 한다.

링크 노드 를 뒤 집 을 때 각 노드 가 가리 키 는 다음 노드 주소 도 바 꿔 야 한다

Code: (C 구현)

#include 
#include 

typedef int Position;
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    Position Address;
    ElementType Data;
    Position Next;
    PtrToNode   Nextptr;
};
typedef PtrToNode List;

#define MaxSize 100000
struct Node arr[MaxSize];

List ReadList(Position firstAddr, int *length)
{
    int i, list_size;
    Position addr, pos;
    List L, p, temp;
    L = (List)malloc(sizeof(struct Node)); L->Nextptr = NULL;
    p = L;
    memset(&arr, -1, sizeof(struct Node));

    for ( i = 0; i < (*length); ++i ) {
        scanf("%d", &addr);
        arr[addr].Address = addr;
        scanf("%d %d", &arr[addr].Data, &arr[addr].Next);
    }

    list_size = 0;
    pos = firstAddr;
    while (arr[pos].Address != -1) {
        p->Nextptr = &arr[pos];
        p = p->Nextptr;
        ++list_size;
        if (arr[pos].Next == -1)
            break;

        pos = p->Next;
    }

    *length = list_size;
    temp = L; L = L->Nextptr; free(temp);
    return L;
}

List Reverse(List L, int reverse_length)
{
    List p1, p2, p3, rear;
    p1 = L; p2 = L->Nextptr; p3 = p2->Nextptr;

    while (reverse_length--) {
        p2->Nextptr = p1;
        p1 = p2;
        p2 = p3;
        if(p3) p3 = p3->Nextptr;
    }
    rear = L->Nextptr;
    rear->Nextptr = p2;
    L->Nextptr = p1;
    return rear;
}

List ReverseList(List L, int length, int reverse_length)
{
    if (reverse_length == 1)
        return L;

    int t;
    List head, p, temp;
    head = (List)malloc(sizeof(struct Node)); head->Nextptr = L;
    p = head;
    t = length / reverse_length;
    while (t--) {
        p = Reverse(p, reverse_length);
    }
    if (length % reverse_length == 0)
        p->Nextptr = NULL;
    temp = head;
    head = head->Nextptr;
    free(temp);
    return head;
}

void PrintList( List L )
{
    List p;
    p = L;
    while (p) {
        if (!p->Nextptr)
            printf("%.5d %d %d
", p->Address, p->Data, -1);
        else
            printf("%.5d %d %.5d
", p->Address, p->Data, p->Nextptr->Address);
        p = p->Nextptr;
    }
}

int main()
{
    Position firstAddr;
    int N, K;
    List L;
    scanf("%d %d %d", &firstAddr, &N, &K);

    L = ReadList(firstAddr, &N);
    L = ReverseList(L, N, K);
    PrintList(L);

    return 0;
}