[자료구조] 단순 연결 리스트 Singly Linked List 실습 문제 - 동적 메모리 할당, 노드 생성(create), 삽입(insert), 역순 연산(reverse), 버블 정렬(bubble sort), 출력, 메모리 해제

 

 

scores.txt

정우람 100.0 45.9 78.5
양현종 64.8 78.9 100
박해진 82.4 93.5 88.4
추신수 99.5 43.9 88.3
박찬호 100.0 99.9 78.5
이대호 88.9 99.9 78.9
강백호 85.4 78.6 31.5
이재학 82.4 93.5 78.4

 

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

typedef struct element {
	char name[20];
	double kor, math, com, total;
}element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

ListNode* create_node(element data, ListNode* link);
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node);
ListNode* reverse(ListNode* head);
void display(ListNode* list);
void bubble(ListNode* head);
void free(ListNode* head);

int main() {
	FILE* fp = NULL;
	ListNode * list1 = NULL;
	element tmp;

	// 파일 열기
	fp = fopen("scores.txt", "rt");
	if (fp == NULL) {
		printf("File nout found\n");
		return 0;
	}

	while (!feof(fp)) {
		// char배열, 3개 double
		fscanf(fp, "%s %lf %lf %lf ", tmp.name, &tmp.kor, &tmp.math, &tmp.com);
		tmp.total = tmp.kor + tmp.math + tmp.com;

		// 새로운 다음 노드 생서 - create node(element, link)
		insert_node(&list1, NULL, create_node(tmp, NULL)); // list1= 연결리스트의 헤드 노드, 포인터 가리키는 앞에 추가, 추가하고자 하는 노드
	}

	list1=reverse(list1); // 리스트 노드 뒤집는다.
	
	// after reverse
	display(list1); // 출력

	free(list1); // 메모리 반환
	
	fclose(fp); // 파일 닫기
	return 0;
}

ListNode* create_node(element data, ListNode* link) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));

	// 새로운 동적 할당에 실패하면 프로그램 실행 종료
	if (new_node == NULL) {
		printf("memory allocation failure\n");
		exit(1); 
	}

	new_node->data = data; // 입력 받은 data구조체를 저장
	new_node->link = link; // 다음 링크 필드 저장(NULL값)

	return new_node;
}

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	// empty linked list인 경우 (empty list = > first insertion case)
	if (*phead == NULL) {
		new_node-> link = NULL; // 빈 리스트의 첫 노드가 되어 다음 링크의 값은 null
		*phead = new_node; // 리스트의 헤드에 저장하게 됨
	}
	else if (p == NULL) { // list의 가장 앞에 추가
		new_node->link = *phead; // previous first node와 phead 사이에 new_node를 끼워넣음
		*phead = new_node;
	}
	else { // p가 NULL이 아니고, new_node를 p 뒤에 추가
		new_node->link = p->link;
		p->link = new_node;
	}
}

ListNode* reverse(ListNode* head) {
	ListNode * p, * q, * r;
	q = NULL; // 새로 만들 리스트

	p = head;
	while (p != NULL) {
		r = q; // r은 임시
		q = p;
		p = p->link; // 다음 요소로 이동
		q->link = r; // 임시로 담아두었던 r(=이전 q값)
	}

	return q;
}

void display(ListNode* list) {

	printf(" -----------------【 성적표 순위별 】------------------ \n\n");
	printf("|   이 름\t언어\t수리\t컴퓨터\t 총점\t 등수 |\n");
	printf(" ======================================================\n");

	int i = 1;

	// 출력
	ListNode* p = list; // 복사본을 이용
	while (p != NULL) {
		printf("|%9s\t%5.1lf\t%5.1lf\t%5.1lf\t%5.1lf\t%3d   |\n", p->data.name, p->data.kor,
			p->data.math, p->data.com, p->data.total, i++);
		printf(" ------------------------------------------------------\n");
		p = p->link;
	}
	printf("\n\n");
}

void bubble(ListNode* head) {
	ListNode* p, * q;
	element tmp;

	for (p = head;p != NULL;p = p->link) {
		for (q = p;q != NULL;q = q->link) {
			if (q->data.total > p->data.total) // q의 total이 p의 total보다 크면
			{
				// q와 p의 swap
				tmp = p->data;
				p->data = q->data; // q와 p의 자리 바꿔줌
				q->data = tmp;
			}
		}
	}
}

void free(ListNode* head) {
	ListNode* p = head, *next;
	while (p != NULL) {
		next = p->link;
		free(p);
		p = next;
	}
}

 

 

 

typedef struct element {
	char name[20];
	double kor, math, com, total;
}element;

typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

 

구조체 구현

 

연결리스트는 데이터 필드와 링크 필드로 구성되는데, 데이터 필드의 데이터를 하나의 구조체로 선언하였다.

 

- 리스트의 구조체 ListNode는 data 멤버 변수와 다음 노드를 가리키는 link 구조체 포인터를 멤버로 포함한다.

- 길이가 20인 name 문자열 배열과, kor, math, com, total의 double 실수형을 멤버로 하는 element 구조체이다.

 

 

 

	while (!feof(fp)) {
		// char배열, 3개 double
		fscanf(fp, "%s %lf %lf %lf ", tmp.name, &tmp.kor, &tmp.math, &tmp.com);
		tmp.total = tmp.kor + tmp.math + tmp.com;

		// 새로운 다음 노드 생서 - create node(element, link)
		insert_node(&list1, NULL, create_node(tmp, NULL)); // list1= 연결리스트의 헤드 노드, 포인터 가리키는 앞에 추가, 추가하고자 하는 노드
	}

	list1=reverse(list1); // 리스트 노드 뒤집는다.
	
	// after reverse
	display(list1); // 출력

	free(list1); // 메모리 반환

 

main 함수의 함수 호출

 

파일을 연 뒤, 다음과 같이 동작하게 된다.

파일에서 char 문자배열, 그리고 세 개의 double형 변수를 한 묶음으로 읽어 tmp 변수에 저장한다.

list1의 주소, NULL값, create_node(tmp, NULL) 을 인수로 전달하며 insert_node 함수를 호출한다.

 

파일로부터 읽어 연결 리스트 전체를 생성하고 난 뒤에는,

리스트의 주소를 인수로 전달하여 리스트 노드를 뒤집어 다시 저장하도록 한다.

 

화면에 출력하고, 메모리를 반환하는 작업을 한 뒤 프로그램을 종료시킨다.

 

 

 

 

 

ListNode* create_node(element data, ListNode* link) {
	ListNode* new_node;
	new_node = (ListNode*)malloc(sizeof(ListNode));

	// 새로운 동적 할당에 실패하면 프로그램 실행 종료
	if (new_node == NULL) {
		printf("memory allocation failure\n");
		exit(1); 
	}

	new_node->data = data; // 입력 받은 data구조체를 저장
	new_node->link = link; // 다음 링크 필드 저장(NULL값)

	return new_node;
}

 

1. ListNode* create_node(element data, ListNode *link);

새로운 노드를 생성하는 함수이다.

 

ListNode 구조체 포인터 new_node에 ListNode 크기의 메모리를 동적 할당하고,

첫번째 매개 변수로 전달 받은 data를 new_node의 데이터 필드에 대입한다.

new_node의 링크 필드에는 두번째 매개 변수인 link 포인터를 대입한다. (main함수에서 이는 NULL값이다.)

 

 

void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	// empty linked list인 경우 (empty list = > first insertion case)
	if (*phead == NULL) {
		new_node-> link = NULL; // 빈 리스트의 첫 노드가 되어 다음 링크의 값은 null
		*phead = new_node; // 리스트의 헤드에 저장하게 됨
	}
	else if (p == NULL) { // list의 가장 앞에 추가
		new_node->link = *phead; // previous first node와 phead 사이에 new_node를 끼워넣음
		*phead = new_node;
	}
	else { // p가 NULL이 아니고, new_node를 p 뒤에 추가
		new_node->link = p->link;
		p->link = new_node;
	}
}

 

2. void insert_node(ListNode **phead, ListNode *p, ListNode *new_node);

새로 생성한 new_node를 리스트에 삽입하는 함수이다.

 

매개 변수

첫번째 매개 변수인 phead는 이중 포인터 값을 전달받게 된다.

main 함수 부분을 살펴보면, 전달되는 인자는 헤드 포인터인 'list'의 주소이다.

list라는 포인터를 전달하게 되면, 리스트의 첫번째 주소를 전달하는 것인 반면,

헤드 포인터인 list의 주솟값, 이중 포인터를 전달하는 것은 헤드 포인터 자체를 변경할 수 있다는 의미이다.

 

두번째 매개 변수인 구조체 포인터 p는 삽입하고자 하는 노드의 앞 노드에 대한 포인터이다.

함수 내에서 else 구문을 살펴보면, 삽입되는 new_node가 p의 뒤에 삽입되는 코드임을 알 수 있다.

 

마지막 매개 변수 new_node는 새로 생성되어 삽입되는 구조체 포인터이다.

main 함수를 보면, new_node는 create_node 함수 내에서 동적 할당을 받아 생성되어 반환되는 노드값임을 알 수 있다.

이 때, 삽입되는 new_node의 데이터 필드와 링크 필드는 이미 모두 초기화되어 있는 상태이다.

 

 

조건문

첫번째는 이중 포인터였던 phead에 대하여 포인터 phead 값이 비어 있을 때이다. 이는 헤드 포인터가 NULL값이라는 의미이다.

main함수에서 null로 선언된 list값이 전달되었기 때문에, 처음 생성되는 노드에 대해서는 첫번째 조건에 해당하여 phead 포인터 값이 new_node가 된다.

 

두번째 else if 문은 *phead가 NULL이 아니면서 동시에 p가 null 값일 때이다.

이는 삽입할 노드가 특정한 p값 뒤에 오도록 하고 싶을 때 인수로 전달할 수 있는 포인터이다.

main함수에서는 null을 초기값으로 전달하기 때문에, 두번째로 삽입되는 노드부터는 이 두번째 조건에 대해 실행될 것이다.

첫번째 phead 포인터 값에 new_node를 대입하게 될 것이다. 계속해서 삽입되는 new_node는 p가 null인 전제 하에 리스트의 맨 첫번째 노드로 삽입된다.

 

마지막 else문은 new_node를 p가 가리키는 노드 뒤에 삽입하라는 문장이다.

 

 

연결리스트에서 이중 포인터를 사용하는 이유는 ? 

사용하는 이유 2

LinkedList 연결리스트 이중포인터 해드포인터 깔끔한 정리

 

 

 

data.txt의 순서대로, 가장 먼저 읽힌 '정우람'에 대한 노드가 리스트의 첫 노드로 생성된다.

이후, 파일의 차례대로 읽으며 new_node의 데이터에 각 데이터가 대입되고 리스트에 차례대로 삽입된다.

삽입이 완료되어 리스트가 생성된 후, 리스트를 차례대로 출력해보면, 파일에 저장되어 있는 것과 다르게 데이터가 거꾸로 저장됨을 볼 수 있다.

그 이유는 위에서 리스트의 삽입 위치가 맨 앞이기 때문이다.

 

 

 

 

3. ListNode* reverse(ListNode *head);

리스트의 순서를 역순으로 바꾸어 저장한 다시 반환하는 함수이다.

 

p, q, r 구조체 포인터를 선언한다.

p는 list의 첫번쨰 노드부터 시작하여 마지막 노드까지 차례대로 접근하여 이동하는 포인터이고,

r에는 반복해서 q가 대입되며, 이때 q는 p를 따라가며 링크 필드에 r을를 저장한다.

다시 q를 r에 대입하고, q는 정방향으로 가는 p를 따라가고, 다시 이 q의 링크 필드에 r이 저장된다.

링크 필드의 방향이 바뀌는 것이다. 

 

q의 링크 필드의 방향이 p의 링크 필드 방향과 정반대가 되었으므로,

이전에 삽입된 순서의 반대로 저장되었던 연결 리스트를 다시 본래의 순서대로 복귀하게 만든다.

따라서 p의 역순인 연결 리스트 q를 반환한다.

 

 

ListNode* reverse(ListNode* head) {
	ListNode * p, * q, * r;
	q = NULL; // 새로 만들 리스트

	p = head;
	while (p != NULL) {
		r = q; // r은 임시
		q = p;
		p = p->link; // 다음 요소로 이동
		q->link = r; // 임시로 담아두었던 r(=이전 q값)
	}

	return q;
}

 

 

4. void display(ListNode *list);

리스트를 출력하는 함수이다.

구조체 포인터 p가 리스트의 첫번째 포인터인 list에 대입되고,

각 노드에 접근할 때 마다 데이터를 출력하도록 한다.

 

void display(ListNode* list) {

	printf(" -----------------【 성적표 순위별 】------------------ \n\n");
	printf("|   이 름\t언어\t수리\t컴퓨터\t 총점\t 등수 |\n");
	printf(" ======================================================\n");

	int i = 1;

	// 출력
	ListNode* p = list; // 복사본을 이용
	while (p != NULL) {
		printf("|%9s\t%5.1lf\t%5.1lf\t%5.1lf\t%5.1lf\t%3d   |\n", p->data.name, p->data.kor,
			p->data.math, p->data.com, p->data.total, i++);
		printf(" ------------------------------------------------------\n");
		p = p->link;
	}
	printf("\n\n");
}

 

 

5. void bubble(ListNode* head);

리스트를 오름차순으로 정렬하는 buble sort(버블 정렬) 함수이다.

 

void bubble(ListNode* head) {
	ListNode* p, * q;
	element tmp;

	for (p = head;p != NULL;p = p->link) {
		for (q = p;q != NULL;q = q->link) {
			if (q->data.total > p->data.total) // q의 total이 p의 total보다 크면
			{
				// q와 p의 swap
				tmp = p->data;
				p->data = q->data; // q와 p의 자리 바꿔줌
				q->data = tmp;
			}
		}
	}
}

 

 

6. void free(ListNode *phead);

동적 할당한 리스트의 모든 노드들에 대하여 메모리를 반환하는 함수이다.

 

첫 노드부터 시작하여, 각 노드에 접근하며 메모리를 해제시킨다.

 

void free(ListNode* head) {
	ListNode* p = head, *next;
	while (p != NULL) {
		next = p->link;
		free(p);
		p = next;
	}
}