c언어로 두 개의 연결리스트를 하나의 정렬된 연결리스트로 합병하는 프로그램

「 두 연결리스트를 하나의 정렬된 연결리스트로 합병하는 프로그램 」

두 개의 정렬된 연결리스트를 합병하여 한 개의 정렬된 연결리스트를 구성하는 프로그램을 작성 해 봅시다.

 

아래는 이 문제에 대한 조건입니다.

 

「 문제 및 조건 」

1. 20개의 공간을 가지는 배열을 선언하고, 1~1000 사이의 정수를 랜덤으로 20개를 할당.

 

2. 이 배열을 선택 정렬을 통해 오름차순으로 정렬.

 

3. 정렬된 배열의 내용을 정렬된 연결리스트로 구성하고(연결리스트 변수는 a), 리스트의 각 노드를 순서대로 출력.

 

4. 연결리스트 b를 구성하고, 리스트의 각 노드를 순서대로 출력.(1,2,3 단계 반복)

 

5. a와 b의 연결 리스트를 합병하여 하나로 정렬된 40개의 연결리스트 d를 구성하고, d리스트의 각 노드를 순서대로 출력.

 

「 프로그램 소스코드 」

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))  //x와 y의 값을 바꾸는 swap 함수

struct node { //자기 참조를 할 수 있는 구조체 node를 선언
	int data;
	struct node * next;
};

void makeArr(int arr[]) // int형 변수 20개를 저장 할 수 있는 배열을 생성하는 함수
{	
	for (int i = 0; i < 20; i++)
		arr[i] = rand()%999 + 1;
}

void printList(struct node * a) // 연결리스트를 받아 출력 하는 함수
{
	for ( ; a != NULL; a = a->next)
		printf("%d ", a->data);
	printf("\n");
}

void sort(int arr[]) // 배열을 오름차순으로 정렬 하는 함수
{
	int i, j, min, temp;
	for (i = 0; i<19; i++) {  
		min = i;	  
		for (j = i + 1; j<20; j++)
			if (arr[j]<arr[min])
				min = j; 
		SWAP(arr[i], arr[min], temp); 
	}
}

struct node * linkList(int arr[]) // 링크드리스트를 만드는 함수
{
	struct node * A = NULL;
	struct node * B = NULL;
	struct node * last = NULL;
	int i = 0;

	A = (struct node*)malloc(sizeof(struct node));
	A->data = arr[0];
	A->next = NULL;
	last = A;

	for (i = 1; i < 20; i++)
	{
		B = (struct node*)malloc(sizeof(struct node));
		B->data = arr[i];
		B->next = NULL;

		last->next = B;
		last = B;
	}

	return A;
}

struct node * connectionList(struct node * a, struct node * b) // 두 개의 링크드리스트를 인자로 받아 오름차순으로 연결 하는 함수
{
	struct node * start;
	struct node * last;

	if (a->data < b->data)
	{
		start = a;
		last = start;
		a = a->next;
		
	}

	else
	{
		start = b;
		last = start;
		b = b->next;
	}

	while (a != NULL && b != NULL)
	{
		if (a->data <= b->data)
		{
			last->next = a;
			last = a;
			a = a->next;
		}

		else
		{
			last->next = b;
			last = b;
			b = b->next;
		}
	}

	if (a == NULL)
		last->next = b;
	else
		last->next = a;

	return start;
}

void main() //메인함수
{
	srand(time(NULL));

	int arr1[20];
	int arr2[20];
	struct node * a;
	struct node * b;
	struct node * d;

	makeArr(arr1);
	sort(arr1);
	a = linkList(arr1);
	printf("a 리스트: ");
	printList(a);
	
	makeArr(arr2);
	sort(arr2);
	b = linkList(arr2);
	printf("b 리스트: ");
	printList(b);

	d = connectionList(a, b);
	printf("d 리스트: ");
	printList(d);

}

 

「 출력화면 」

LinkedList 출력화면