데이터 구조와 알고리즘 문제집(중국어) 6-1 단일 체인 테이블 역전(20점)
1382 단어 기본 알고리즘과 데이터 구조
함수 인터페이스 정의:
List Reverse( List L );
여기서
List
구조 정의는 다음과 같습니다.typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* */
PtrToNode Next; /* */
};
typedef PtrToNode List; /* */
L
는 단일 체인 테이블을 정하고 함수Reverse
는 역전된 체인 테이블로 되돌아간다.심판 테스트 프로그램의 예:
#include
#include
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* */
void Print( List L ); /* */
List Reverse( List L );
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
/* */
샘플 입력:
5
1 3 4 5 2
출력 예제:
1
2 5 4 3 1
이 문제는 나를 오랫동안 괴롭혔는데, 맞는 코드를 제출한 것 같지만 틀렸다...남의 문제풀이를 보고 내가 뭘 잘못했는지 알았어...
두 포인터 정의 p1, p2.처음에는 두 포인터의 값이 NULL입니다.그리고 다음 포인터 값을 기록한 다음에 다음 포인터의 값이 앞 노드를 가리키도록 합니다...
그리고 각자 한 명씩 뒤로 옮겨서...
이렇게 순환하다.
코드는 다음과 같습니다.
List Reverse( List L )
{
List p1=NULL,p2=NULL;
while (L)
{
p2=L->Next;
L->Next=p1;
p1=L;
L=p2;
}
return p1;
}