[C/자료구조] 오름차순으로 정렬된 연결리스트 구현하기

C언어를 이용한 자료구조 실습입니다.

연결리스트를 항상 오름차순으로 정렬된 연결리스트를 생성합니다.

순차탐색을 이용해 위치를 찾고 이전 노드에 연결하여 반환하는 insert() 함수를 구현합니다. 

---

 

I. 문제

노드의 구조는 (data, link)로 구성된다. 여기서  data는 정수 타입이며, link는 노드에 대한 포인터이다. 이러한 노드들로 연결되는 리스트를 고려한다.

 

다음 함수들을 C 함수로 작성하라.

 

•  정수 배열 a를 선언하면서 다음 수들로 초기화하라 : (5, 1, 3, 7, 1, 4, 3, 5, 2, 1, 9, 6, 2, 8, 3)
•  리스트 list에 포함된 노드들이 data 필드 값 기준으로 오름차순으로 정렬되어 있다고 가정한다. list와  정수 val를 전달받아서, val을 포함한 노드를 동적 생성하고, 이 노드를 list에 삽입하되 list가 정렬이 유지되게 하라. 또한, 그 결과 리스트를 반환하는 insert(list, val)을 작성하라.
•  배열 a를 매개변수로 전달받아서 배열에 포함된 각 요소에 대해서 노드를 생성하고, 이들을 data 필드 값 기준으로 오름차순으로 정렬되게 연결하여 리스트를 구성하여 반환하는 gen_list(a, size)를 작성하라(size는 배열 크기임). 단, 위의 insert() 함수를 이용하라.
•  매개변수로 전달된 리스트 list에 포함된 모든 노드의  data 필드 값을 순서대로 출력하는 print_list(list)를 작성하라.

 

---

II. 구현

insert 함수 구현시 고려해야할 경우의 수는 다음과 같다고 설정한 뒤 작성하였습니다.

 

1. 첫 번째 요소를 넣을 때
2. 넣으려는 요소가 리스트의 첫 번째 요소보다 작을 때
3. 넣으려는 요소가 리스트의 중간에 들어갈 때
4. 넣으려는 요소가 리스트의 어떤 값보다 가장 클 때

#include<stdio.h>
#include<stdlib.h>

typedef int element; // 정수형 데이터

// 노드 구조체
typedef struct
{
	element data;
	struct ListNode* link;

}ListNode; 


ListNode* insert(ListNode* head, int val)
{

	ListNode* new; // 노드 생성
	new = (ListNode*)malloc(sizeof(ListNode)); // 동적할당
	new->link = NULL; //초기화
	new->data = val; 

	if (head == NULL){		// 첫번째 요소일 때
		new->link = head;	// head가 가리키는 곳을 new->link가 가리킴
		head = new;			// head는 new를 가리킴
	}
	else{
		int check = 0;
		ListNode* pre = NULL;
		ListNode* now = head;	// 헤드 부터
		while (now != NULL)		// 요소의 끝까지 비교
		{
			if (new->data < now->data){  // 새로 넣을 값이 현재 탐색중인 노드 데이터보다 작을 때

				if (pre == NULL){		// 첫 번째 요소보다 작다면
					new->link = head;
					head = new;			// 맨 앞에저장
					check = 1;
				}
				else{					// 첫번째 요소가 아니라면 전요소(pre) 앞에 연결
					pre->link = new;		
					new->link = now;		
					check = 1;
				}
				break;
			}
			pre = now;		  
			now = now->link;  // 다음 노드 탐색
		}

		if (check == 0)			// 여태 들어온 값들 중 가장 크다면
			pre->link = new;	// 마지막 노드에 연결
	}
	return head; //리스트 반환
}


ListNode* gen_list(int* a, int size)
{
	ListNode* head = NULL;
	for (int i = 0; i < size; i++)
		head = insert(head, a[i]); // 함수 호출
	return head; // 리스트 반환

}
void print_list(ListNode* head)
{
	ListNode* p;
	p = head;		// 포인터를 헤드에 연결
	while (p != NULL){
		printf("%d -> ", p->data); // 출력
		p = p->link; // 다음 노드로 넘어감
	}
	printf("NULL\n");  // 마지막은 NULL출력

}


int main()
{
	element a[] = { 5, 1, 3, 7, 1, 4, 3, 5, 2, 1, 9, 6, 2, 8, 3 }; // 배열 a
	ListNode* head = NULL; // 헤드 선언
	head = gen_list(a, sizeof(a) / sizeof(element)); // 요소들이 정렬된 리스트 생성

	print_list(head); // 값 출력

	return 0;

}

 

III. 분석 및 결과

 

ListNode* insert(ListNode* head, int val){
	ListNode* new; // 노드 생성
	new = (ListNode*)malloc(sizeof(ListNode)); // 동적할당
	new->link = NULL; //초기화
	new->data = val; 
    
	if (head == NULL){		// 첫번째 요소일 때
		new->link = head;	// head가 가리키는 곳을 new->link가 가리킴
		head = new;		// head는 new를 가리킴
	}
	else{
        .....
    }
	return head; //리스트 반환
}

insert 함수는 head와 val(이 문제에서는 a배열의 요소)을 매개변수로 받아온다. 그리고 새로운 노드(new)를 동적으로 생성 하여 초기화한다. 이때 head가 NULL을 가리키고 있다면 첫 번째 요소이기에 new를 바로 head 다음으로 연결해준다.

 

 

	...
	else{
		int check = 0;
		ListNode* pre = NULL;
		ListNode* now = head;	// 헤드 부터
		while (now != NULL)	// 요소의 끝까지 비교
		{
        
			....
            
            
			pre = now;		  
			now = now->link;  // 다음 노드 탐색
		}

		if (check == 0)			// 여태 들어온 값들 중 가장 크다면
			pre->link = new;	// 마지막 노드에 연결
	}
	return head; // 리스트 반환
}

 

NULL이 아니라면 new의 위치를 찾기 위해 pre과 now를 사용한다. 먼저 now는 현재 탐색중인 노드를 가리킨다. 첫 번째 요소에서 시작해, 비교하며 한 칸씩 앞으로 나아가는 역할이다. pre는 now의 전요소를 가리키는 역할로 new 노드의 자리를 찾았을 때 연결할 자리를 저장하는 역할이다. while문을 통해 now가 마지막 노드를 탐색할 때까지 탐색은 계속된다.

while문이 종료되었는데도 check가 0이라면 현재 노드들 보다 큰 값이 들어온 것이므로 마지막 노드에 연결한다.

 

 

 

			...

			if (new->data < now->data){  // 새로 넣을 값이 현재 탐색중인 노드 데이터보다 작을 때

				if (pre == NULL){		// 첫 번째 요소보다 작다면
					new->link = head;
					head = new;			// 맨 앞에저장
					check = 1;
				}
				else{					// 첫번째 요소가 아니라면 전요소(pre) 앞에 연결
					pre->link = new;		
					new->link = now;		
					check = 1;
				}
				break;
			}
			...

 

반복문 내에서는 다음 과정을 반복한다.

new의 값(data)이 첫 번째 요소보다 작으면 맨 앞에 노드를 추가한다. 아니라면 중간에 위치한 값으로 pre이 가지고 있던 위치에 new 노드를 추가한다. 노드가 자리를 잡으면 바로 break 하여 while 문을 탈출한다.

 

 

 

 

결과를 보면 잘 정렬된 것을 확인할 수 있다. 

 

 

감사합니다.

 

---

 

공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.