6 - 1 싱글 체인 시트 역전 (절 빅 데이터 구조 PTA)

이 문 제 는 하나의 함 수 를 실현 하고 주어진 단일 체인 표를 역전 시 켜 야 한다.
함수 인터페이스 정의: List Reverse (List L);
그 중에서 List 구 조 는 다음 과 같다.
typedef struct Node PtrToNode; struct Node {Element Type 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
이 문 제 는 싱글 체인 시 계 를 직접 역 설정 하면 됩 니 다. 체인 시 계 를 새로 만 들 지 않 아 도 됩 니 다. 그러나 이 PTA 문 제 는 머리 노드 가 없 는 싱글 체인 시 계 를 사용 하기 때문에 여러 번 틀 리 고 답답 합 니 다.이 문제 에 대응 하 는 역 치 코드:

PtrToNode Reverse(PtrToNode L)
{
  PtrToNode p1=NULL,p2=NULL;
  while(L!=NULL)
  {
    p2=L->Next;
    L->Next=p1;
    p1=L;
    L=p2;
  }
  return p1;
}

실제 적 으로 사용 하 는 방법 은 지침 의 방향 을 바 꾸 는 것 이다.
두 결점 이 있 는 전체 코드 를 보 여 줍 니 다. (본 문제 에 적용 되 지 않 음) (원래 의 단일 체인 표를 바 꾸 었 습 니 다)

#include
#include
typedef struct Node *PtrToNode;
struct Node
{
	int data;
	PtrToNode Next;
};
PtrToNode read()
{
    int n;
    scanf("%d",&n);
	PtrToNode L,head;
	L=(PtrToNode)malloc(sizeof(struct Node));
	L->Next=NULL;
	head=L;
	int i;
	for(i=1;i<=n;i++)
	{
		PtrToNode e=(PtrToNode)malloc(sizeof(struct Node));
		scanf("%d",&e->data);
		e->Next=NULL;
		L->Next=e;
		L=L->Next;
	}
	return head;
}
void Print(PtrToNode L)
{
	PtrToNode p;
	p=L->Next;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->Next;
	}
}
void Printt(PtrToNode L)
{
	PtrToNode p=L;
	while(p!=NULL)
	{
		printf("%d",p->data);
		p=p->Next;
	}
	return ;
}
PtrToNode Reverse(PtrToNode L)
{
  PtrToNode p,q;
  p=L->Next;
  L->Next=NULL;
  while(p!=NULL)
  {
    q=p->Next;//  q      
    p->Next=L->Next;//             
    L->Next=p;//  ，   p     (      ) 
    p=q;
  }
  return L;
}
int main()
{
	PtrToNode L1,L2;
	L1=read();
	L2=Reverse(L1);
	Print(L2);
	return 0;
}

포인터 p 가 어느 위치 로 이동 할 때 p - > L 이 가리 키 는 다음 (사실 L 의 Next 가 가리 키 는 것 은 p 앞 에 있 는 것) 을 가리 키 면 방향 이 바 뀝 니 다.