링크 의 역 치 (헤드 삽입, 현지 역 치, 재 귀)

12009 단어 데이터 구조
데이터 구조 실험의 링크 3: 링크 의 역 치
설명 은 여러 개의 정 수 를 입력 하고 - 1 을 끝 표지 로 하 며 순서대로 선두 결점 을 가 진 단일 체인 표를 만 든 다음 에 이 단일 체인 표 의 데 이 터 를 역 치 하고 역 치 된 단일 체인 표 데 이 터 를 출력 합 니 다.Input 은 여러 개의 정 수 를 입력 하여 - 1 을 끝 표지 로 합 니 다.출력 역 설 치 된 단일 링크 데이터.Sample Input 12 56 4 6 55 15 33 62 -1 Output 62 33 15 55 6 4 56 12
링크 의 역 치 는 보통 세 가지 흔히 볼 수 있 는 방법 이 있 습 니 다. 보통 순환 (헤드 삽입 법, 현지 역 치) 과 재 귀 입 니 다. 아래 의 이 코드 는 제 가 처음 썼 을 때 쓴 것 입 니 다. 바로 새로 만 든 선두 노드 의 링크 에 해당 합 니 다. 그리고 데 이 터 를 거꾸로 복사 한 것 입 니 다.
#include
using namespace std;
struct node
{
	int data;
	struct node *next;
};
int main()
{
	struct node *head,*tail,*p,*q,*k;
	head=new struct node();
	head->next=NULL;
	tail=head;
	while(1)
	{
		p=new struct node();
		p->next=NULL;
		cin>>p->data;
		if(p->data==-1)
			break;
		tail->next=p;
		tail=p;
	}
	//——————————    ——————————
	p=head->next;
	q=new struct node();		//       
	q->next=NULL;
	while(p)
	{
		k=new struct node();
		k->data=p->data;
		k->next=q->next;
		q->next=k;
		p=p->next;
	}
	//———————————————————————————
	for(p=q->next;p!=NULL;p=p->next)
		cout<<p->data<<" ";
	return 0;
}

다음은 머리 삽입 법의 코드 입 니 다. 헛 된 상상 이 어렵 습 니 다. 여러분 은 종 이 를 가지 고 순환 과정 을 보 여 드릴 수 있 습 니 다. 중점 은 순환 이 시작 되 기 전의 이 두 문장 입 니 다. 순서 가 바 뀌 면 안 됩 니 다. 순환 안 은 p 로 옮 겨 다 니 고 q 로 삽입 합 니 다.
	p=head->next;				//   p       
	head->next=NULL;			//         ，    
	while(p)
	{
		q=p;					//q p           
		p=p->next;
		
		q->next=head->next;	    //           ， q        
		head->next=q;
	}

이것 은 포인터 의 방향 이 바 뀌 었 기 때문에 그 자리 에서 역 설 치 된 코드 블록 입 니 다.이것 도 강 한 두 문장의 순 서 를 주의해 야 합 니 다. 일반적으로 헤드 포인터 가 없 는 링크 를 역 설정 해 야 합 니 다. 저 는 p 로 첫 번 째 요 소 를 가리 키 고 head 를 NULL 로 직접 할당 합 니 다.NULL 값 의 변 수 를 도입 할 수도 있 습 니 다.현지 역 치 의 정 수 는 헤드, q, p 이다. 이 세 가 지 는 순서 가 인접 한 세 개의 결점 을 가리 키 고 q 를 이용 하여 결점 의 지향 을 바꾼다.
	p=head->next;
	head=NULL;
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		
		q->next=head;		//         ，          
		head=q;
	}

다음은 재 귀 의 해법 이다. 재 귀 는 항상 이해 하기 어렵다. 먼저 뒤의 결점 을 찾 은 다음 에 다시 거 슬러 올라간다.
node* newList(node *head)
{
    if (head == NULL || head->next == NULL)
             return head;
     node *newhead = newList(head->next);
 
     head->next->next = head;
     head->next = NULL;
     return newhead;
 }

헤드 삽입 법 과 현지 역 치 코드 를 첫 번 째 완전한 프로그램의 대응 위치 에 놓 으 면 됩 니 다.
[Kotlin Docs] Package and Import
[c++] 백준 11286, 절댓값 힙

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage