분할 알고리즘 (사상) 이 데이터 구조 에서 의 응용

분할 알고리즘: 간단 한 요약 은 잠시 해결 할 수 없 는 큰 문 제 를 많은 입문 자 문제 로 나 누 는 것 이다.
만약 하위 문제 가 여전히 해결 되 지 않 는 다 면, 하위 문제 가 작 을 때 까지 계속 하위 문제 로 나 누 어 라.
해결 할 수 있 는 규모, 원래 문 제 는 하위 문제 의 합병 이다.
PartOne:
분할 처리 법 으로 배열 a [L,..., R] 를 인쇄 합 니 다.   분석:   하나의 순환 이면 되 지만, 분할 알고리즘 으로 해결 하려 면 어떻게 해 야 합 니까? 인쇄 할 시퀀스 길이 가 1 이면 직접 인쇄 할 수 있 습 니 다. 인쇄 할 시퀀스 길이 가 N 이면 두 부분 으로 나 눌 수 있 습 니 다. 첫 번 째 부분 은 1, 후 N - 1 은 다른 구분 으로 배열 의 길이 가 1 일 때 까지 유추 된다.

 void print(int a[], int L, int R)
 {
	if(L > R)
		return;
	else if(L == R)
	{
		cout<<"a[L]"<<" ";
	}
	else
	{
		cout<<a[L]<<" ";
		print(a, L + 1, R);
	}
 
 }

PartTwo:  함수 divid () 가 존재 한다 고 가정 하면 하나의 배열 a [L,..., R] 를 두 부분 으로 나 눌 수 있 습 니 다.
요소 a [L] 는 분계선 이 고 a [L] 보다 작은 요 소 는 왼쪽 에 있 으 며 a [L] 보다 큰 요 소 는 오른쪽 에 있 습 니 다.   함수 설명 은 다음 과 같 습 니 다. 

int divid(int a[], int L, int R);

 분 치 법 을 사용 하여 배열 a [L,... R] 의 요 소 를 빠르게 정렬 합 니 다.
 
 분석:
 
 길이 가 1 보다 작 으 면 기본적으로 질서 가 있 고, 서열 길이 가 1 보다 크 면 divid () 함수 로
이 를 3 부분 으로 나 누고 왼쪽 은 a [L] 보다 작은 부분 이 며 중간 은 a [L] 이 고 오른쪽 은 크다.
a [L] 의 부분.a [L] 질서 가 있 으 면 좌우 두 부분 만 분기 처리 해 야 합 니 다.

 void Qsort()
 {
	int mid;
	if(L >= R)
		return;
	else
	{
		mid = divid(a, L, R);
		Qsort(a, L, mid);
		Qsort(a, mid + 1, R);
	}
 }

PartThree;
 이 진 트 리 하나 가 이 진 트 리 에 저장 되 어 있 으 며, 분 치 법 으로 모든 노드 값 을 인쇄 합 니 다.
근결 점 은 p 가 가리킨다.   분석: 나무 가 비어 있 을 때 는 아무것도 하지 않 고 문 제 를 직접 해결한다. 나무 에 점 이 하나 이상 있 을 때 나무 전 체 를 뿌리, 왼쪽 나무 로 나 누 어
오른쪽 나무 세 부분.루트 노드 를 직접 인쇄 하여 왼쪽 트 리 를 계속 분할 처리 합 니 다.
오른쪽 트 리 를 계속 나 누 어 처리 하고 마지막 으로 이 진 트 리 전 체 를 인쇄 합 니 다.

 void printTree(BTNode *p)
 {
	if(p == NULL)
		return;
	else
	{
			cout<<p->data<<" ";
			printTree(p->lchild);
			printTree(p->rchild);
	}
 }
 

PartFour：
 하나의 연결 그림 G 는 인접 표 로 저장 되 고 분 치 법 으로 그림 의 모든 정점 값 을 인쇄 합 니 다. 정점 v 부터 인쇄 한다 고 가정 합 니 다.
 전체 그림 을 n 부분 으로 나 눌 수 있 습 니 다. 그 다음 에 앞의 예 와 같이 그림 을 나 눌 수 있 습 니 다. 첫 번 째 변 에 이 르 는 하위 그림 과 같 습 니 다.
 두 번 째 변 에 도달 한 서브 맵.V 는 직접 인쇄 한 후에 각 하위 그림 을 각각 나 누 어 처리 할 수 있다.
 회로 현상 을 방지 하기 위해 서 는 이미 지나 간 길 을 표시 하 는 배열 visited [] 를 설정 할 수 있 습 니 다.
(깊이 우선 검색 의 분할 해석)

void printGraph(AGraph *G, int v)
{
	ArcNode *p;
	visited[v] = 1;
	cout<<v<<" ";
	p = G->adjlist[v].firstarc;
	while(p != NULL)
	{
		if(visited[p->adjvex] == 0)
		{
			printGraph(G, p->adjvex);
		}
		p = p->nextarc;
	}
} 
 

PartFive:
 이 진 트 리 의 우선 순 서 는 시퀀스 와 중간 순 서 를 옮 겨 다 니 며 각각 a [L1,..., R1] 에 저 장 됩 니 다.
b[L2,...R2];두 배열 에서 분리 알고리즘 으로 이 두 배열 에서 이 진 트 리 를 만 듭 니 다.
이 진 링크 에 저 장 된 구조 에 저 장 됩 니 다.   분석: 빈 서열 이 라면 아무것도 할 필요 가 없다.길이 가 1 보다 크 면 a [L1] 비트 이 진 트 리
의 뿌리 결산 점 은 b [] 에서 a [L] 를 찾 고 아래 에 k 라 고 표시 하면 b [L2,................................................................
의 모든 결점, b [k + 1,.........................................................................
a [L1 + 1,... L1 + k - L2] 와 b [L2,..., k - 1] 는 계속 분할 처 리 를 한다.최종 적 으로 나 무 를 만 들 수 있 습 니 다.

BTNode* Create(int a[], int b[], int L1, int R1, int L2, int R2)
 {
	int k;
	if(L1 > R1)
		return NULL;
	else
	{
		s = (BTNode*)malloc(sizeof(BTNode));
		s->data = a[L1];
		for(k = L2; k < R2; ++k)
		{
			if(a[L1] == b[K])
			{
				break;
			}
		}
		s->lchild = Create(a, b, L1 + 1, L1 + k - L2, L2, k - 1);
		s->lchild = Create(a, b, L1 + k - L2 + 1, R1, k + 1, R2);
	}
 }