C 언어 데이터 구조 링크 와 병합 정렬 인 스 턴 스 상세 설명

C 언어 데이터 구조 링크 와 병합 정렬 인 스 턴 스 상세 설명
병합 정렬 은 링크 의 원래 주소 정렬 에 적합 합 니 다.즉,포인터 의 연결 방식 만 바 꾸 고 링크 의 결산 점 내용 을 교환 하지 않 습 니 다.
병합 정렬 의 기본 사상 은 분 치 법 이다.먼저 하나의 링크 를 하나의 노드 만 있 는 링크 로 나 눈 다음 에 일정한 순서,아래 에서 위로 인접 한 두 개의 링크 를 합병 하 는 것 이다.
각종 크기 의 서브 링크 가 질서 가 있다 는 것 을 보증 하기 만 한다 면 마지막 으로 돌아 오 는 링크 는 반드시 질서 가 있 을 것 이다.
병합 순 서 는 분할 과 합병 두 개의 키 과정 으로 나 뉜 다.분할 은 재 귀 하 는 방법 으로 링크 를 반 으로 나 누 어 두 개의 링크 로 나 누 는 것 이다.합병 은 재 귀(회 삭)할 때 두 개의 질서 있 는 링크 를 질서 있 는 링크 로 합 친 것 이다.

(주의:한 노드 만 있 는 링크 는 질서 가 있 을 것 입 니 다)
여기 sort 과정 은 분할 과정 입 니 다.merge 프로 세 스 는 통합 및 정렬 과정 입 니 다.
분할 링크 에 대해 말하자면 문제 가 생 겼 다.링크 는 무 작위 로 방문 한 것 이 아니 라 분할 점 이 어디 에 있 는 지 어떻게 알 겠 는가?하나의 귀중 한 경험 은 두 개의 지침 을 지 키 는 것 이다.하 나 는 빠 르 고 하 나 는 느리다.빠 른 지침 은 매번 두 단 위 를 뒤로 옮 기 고 느 린 지침 은 매번 한 단위 만 이동한다.빠 른 바늘 이 tail 이나 마지막 유효 노드 로 이동 할 때 느 린 바늘 은 중간 노드 를 가리킨다.
sort 과정:

Node* sort (Node* beg)
{
  if(beg==tail || beg->next==tail) return beg;
  Node* a = beg; Node* b = beg->next;
  while(b!=tail && b->next != tail)
  {
    a = a->next; b = b->next->next;
  }
  b = a->next;  //the beginning of right part
  a->next = tail; //the end of left part
  return merge(sort(beg), sort(b));
}

체인 시 계 를 분할 한 후에 합병 해 야 한다.merge 작업 이 들 어 오 는 매개 변 수 는 두 개의 질서 있 는 링크 이 고 합병 후의 질서 있 는 링크 를 되 돌려 줍 니 다.두 개의 질서 있 는 링크 를 간단하게 연결 한 후에 반드시 질서 가 있 는 것 이 아니 라 모든 요 소 를 다시 배열 해 야 한다.이 재 배열 과정 은 두 개의 링크 가 각각 가장 작은(최대)요소 부터 작 으 면 누 구 를 새로운 링크 에 넣 는 것 이다.

Node* LinkedList<T>::merge(Node* a, Node* b)
{
	Node dummy = Node();
	Node* head = &dummy;
	// temp          
	Node* temp = head;
	while(a!=tail && b!=tail) //      a   b     
	{
		if(a->data <= b->data)
		{
			//   a b ,            a
			temp->next = a;
			//          
			temp = a;
			// a  
			a = a->next;
		}
		else 
		{
			temp->next = b;
			temp = b; 
			b = b->next;
		}
		//     a    ,        b     
		//      a    b    
		temp->next = (a==tail) ? b : a;
	}
	return head->next;
}

읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!