제목 1673: 알고리즘 2 - 1: 집합 union [데이터 구조]

내 가 터 뜨 렸 어, 이 죽은 문제 가 도대체 무슨 뜻 이 야?
제목 설명
만약 에 두 개의 선형 표 LA 와 LB 를 이용 하여 각각 두 개의 집합 A 와 B (즉, 선형 표 의 데이터 요 소 는 집합 중의 구성원) 를 나타 낸다 고 가정 하면 현 재 는 새로운 집합 A = A * 8746 ° B 를 요구한다.이 는 선형 표 에 대해 다음 과 같은 조작 을 해 야 한다. 선형 표 LA 를 확대 하고 선형 표 LA 에 존재 하지 않 는 데이터 요 소 를 선형 표 LA 에 삽입 해 야 한다.선형 표 LB 에서 각 요 소 를 순서대로 얻 고 값 에 따라 선형 표 LA 에서 조사 하면 존재 하지 않 으 면 삽입 합 니 다.상술 한 조작 과정 은 아래 의 알고리즘 으로 설명 할 수 있다.

void Union(List &La, List &Lb)
{
     
	//       Lb    La       La 
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for(i = 0; i <= Lb_len; i++){
     
		GetElem(Lb, i, e);// Lb  i     e
		if(!LocateElem(La, e, equal))	//La     e     
			ListInsert(La, ++La_len, e);
	}
}

그림: 두 목록 을 합 친 알고리즘 (C / C + 설명) 위의 그림 알고리즘 에서 8 번 째 줄 에서 집합 B 의 요 소 를 얻 은 다음 10 번 째 줄 에 집합 A 에 삽입 합 니 다.당신 의 임 무 는 집합 A 와 집합 B 의 요 소 를 먼저 출력 하고 한 줄 에 집합 하여 출력 하 는 것 입 니 다.그리고 집합 B 에 있 는 요 소 를 꺼 내 집합 A 끝 에 삽입 한 후에 집합 A 에 있 는 요 소 를 출력 합 니 다.물론 당신 의 코드 는 위의 코드 와 다 를 수 있 습 니 다. 같은 출력 만 있 으 면 됩 니 다.
입력
여러 조 의 테스트 데이터 가 있 는데, 각 조 의 테스트 데 이 터 는 두 줄 을 차지한다.첫 줄 은 집합 A, 첫 번 째 정수 m (0) 이다.
출력
각 그룹의 테스트 데이터 출력 n + 2 줄: 앞의 두 줄 은 각각 집합 A, 집합 B 의 데 이 터 를 출력 합 니 다. 뒤의 n 줄 은 B 에서 요 소 를 꺼 내 A 꼬리 에 삽입 한 후의 집합 A 입 니 다. 각 줄 의 정수 사 이 는 하나의 빈 칸 으로 분리 되 고 각 그룹의 테스트 데이터 사 이 는 한 줄 의 빈 줄 로 격 리 됩 니 다.
샘플 입력
5 1 5 2 6 3 3 1 7 9 1 3 2 2 7 4 2 5 1 4 4 1 2 4 5
샘플 출력
1 5 2 6 3 1 7 9 1 5 2 6 3 1 5 2 6 3 7 1 5 2 6 3 7 9
3 2 7 3 2 3 2 7
2 5 1 4 1 2 4 5 2 5 1 4 2 5 1 4 2 5 1 4 2 5 1 4
Code AND Analysis
가장 큰 문 제 는 순서 표 의 크기 입 니 다!! 두 개의 순서 표 가 합 쳐 져 있 기 때문에 두 개의 요소 가 모두 100 개의 요 소 를 포함 하고 두 표 에 중복 되 는 요소 가 나타 나 지 않 는 다 면 100 의 공간 크기 만 신청 하 는 것 은 부족 합 니 다. 그리고 신기 한 출력 각 요소 뒤 에는 빈 칸 이 있 고 마지막 요 소 는 차 로 돌아 가 는 방법 입 니 다.

#include
#define MAXN 200
typedef struct {
     
	int base[MAXN + 1];
	int length;
}SqList;

int LocateElem(SqList L, int e)
{
     
	int i;
	for (i = 0; i < L.length && e != L.base[i]; i++);
	if (i == L.length)	return 0;
	else	return 1;
}
void InsertElem(SqList* L, int e)
{
     
	L->base[L->length] = e;
	(L->length)++;
	return;
}
void PrintList(SqList L)
{
     
	//     
	if (L.length == 0)	return;
	int i;
	//               ，         
	for (i = 0; i < L.length - 1; i++)
		printf("%d ", L.base[i]);
	printf("%d
", L.base[i]);
	return;
}
void Union(SqList *La, SqList *Lb)
{
     
	int i;
	for (i = 0; i < Lb->length; i++) {
     
		if (!LocateElem(*La, Lb->base[i])) {
     
			InsertElem(La, Lb->base[i]);
		}
		PrintList(*La);
	}
	return;
}


int main()
{
     
	int n, i;
	SqList La, Lb;
	while (scanf("%d", &n) != EOF) {
     
		for (i = 0, La.length = n; i < n; i++)
			scanf("%d", &La.base[i]);
		scanf("%d", &n);
		for (i = 0, Lb.length = n; i < n; i++)
			scanf("%d", &Lb.base[i]);
		PrintList(La);
		PrintList(Lb);
		if(La.length != 0 || Lb.length != 0)
			Union(&La, &Lb);
		printf("
");
	}
}