Chater 2. 연결리스트를 사용해 영화 평점 관리 프로그램 만들기

홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀

Chapter 2. 연결리스트

🚀 배열과의 차이

✈ 배열

• 장점 👉 원소들이 연속적으로 저장되어 있기 때문에 [] 인덱스로 임의 접근이 가능함. O(1)
• 단점 👉 추가, 삭제시 효율이 낮다.
  • 추가할 때 추가할 자리 뒤에 있는 원소들은 전부 뒤로 한 칸씩 땡겼어야 함. 삭제할 때는 전부 앞 칸씩 땡기기.
  • 정적 배열은 사이즈가 고정적이고 동적 배열은 resize 가 좀 부담스러운 연산일 수 있음

✈ 연결리스트

순회 및 접근이 빈번할 경우 배열을, 추가 삭제가 빈번할 경우 연결리스트 사용.

• 배열과 달리 데이터들이 연속해서 같이 있지 않는다.
  • 방향 포인터를 가지고 이를 통해 다음 데이터의 메모리 주소를 가리키게 된다.
  • 원소들이 메모리에 따로 따로 분포되어 있고 체인으로 데이터 하나하나가 연결되어 있는 식!
  • 배열처럼 바로 임의접근 할 수가 없다. 순차 접근만 가능함.
    • 순차적으로 HEAD가 가리키는 첫 번째 원소부터 시작하여 각 데이터들이 가지고 있는 포인터를 따라서 직접 순차적으로 해당 원소를 찾아가야 한다. 최악의 경우 O(n)
• 배열처럼 통째로 메모리를 다 받아오지 않고, 원소 하나하나를 따로 메모리 할당 받는다.
  • 배열처럼 미리 할당 받아놓는 예비 메모리, 아직 쓸모 없는 메모리를 비효율적으로 미리 가지고 있을 필요가 없게 된다.
• 접근은 순차접근이라 느릴 수 있지만 추가, 삭제는 빠르다.
  • A B 사이에 C 를 추가하고자 한다면 A 의 다음 원소를 C 로 하고 C 의 다음 원소를 B 라고 명명만 해주면 땡이기 때문이다. 배열처럼 뒤에 있는 원소들 전부 다 한칸씩 떙기고 밀고 할 필요가 없음!

• 동적인 노드 개수! 👉 그때 그때 노드(데이터)를 생성함.
• 사실 연결리스트에서 추가적으로 필요한 포인터 메모리는 배열의 남는 메모리에 비하면 아무 것도 아니다..☆

🚀 연결리스트 구현하기

✈ 노드

#define TSIZE 45  

struct movie
{
	char title[TSIZE];
	float rating;
	struct moive* next; // 연결리스트의 다음 포인터
};

typedef struct movie* p_movie;

• 영화 노드
  • 제목
  • 점수
  • 다음 영화를 가리키는 포인터
• strcut movie*은 p_movie라고 명명

✈ 노드 출력

void print_all(struct movie* head)
{
	printf("===========================================\n");
	printf("Head adress = %zd\n", (size_t)head);
	
	struct movie* search = head;
	while (search != NULL)
	{
		printf("%zd \"%s\" %.1f %zd\n", (size_t)search, search->title, search->rating, (size_t)search->next);
		search = search->next;
	}
}

• 연결 리스트의 모든 노드들을 출력하는 함수
  • head부터 시작하여 다음 포인터, 다음 포인터 이렇게 순차적으로 모든 노드들에 차례 대로 접근한다.

✈ 첫 번째 노드 추가

	p_movie head = NULL;


	/* First Node */
	p_movie new_node = malloc(sizeof(struct movie));
	if (new_node == NULL)
	{
		printf("ERROR: malloc failed.");
		exit(1);
	}
	strcpy(new_node->title, "Avatar");
	new_node->rating = 9.5f;
	new_node->next = NULL; // 유일한 노드이므로 마지막 노드라 다음 노드는 없다.

	if (head == NULL)
		head = new_node;

	print_all(head);

💎출력💎

===========================================
Head adress = 15228696
15228696 "Avatar" 9.5 0

• 빈 리스트에 첫 번째 노드를 추가하는 것이므로 head에 첫 번째 노드의 주소를 저장하면 땡이다!

✈ 두 번째 노드 추가 : 맨 앞에 추가

	/* Second Node */
	new_node = malloc(sizeof(struct movie));
	if (new_node == NULL)
	{
		printf("ERROR: malloc failed.");
		exit(1);
	}
	strcpy(new_node->title, "Aladdin");
	new_node->rating = 8.0f;
	new_node->next = NULL;

	/* Add front */
	p_movie temp = head;
	head = new_node;
	new_node->next = temp;

	print_all(head);

💎출력💎

===========================================
Head adress = 15228368
15228368 "Aladdin" 8.0 15228696
15228696 "Avatar" 9.5 0

• 맨 앞에 추가하기
  • head가 가리키던 추가하기 전의 맨 앞 노드를 추가하려는 노드의 다음 노드로 지정한다.

✈ 세 번째 노드 추가 : 맨 뒤에 추가

	/* Third Node */
	new_node = malloc(sizeof(struct movie));
	if (new_node == NULL)
	{
		printf("ERROR: malloc failed.");
		exit(1);
	}
	strcpy(new_node->title, "Wonder Woman");
	new_node->rating = 8.5f;
	new_node->next = NULL;

	/* Add back */
	// 1. find last node
	p_movie search = head;
	while (search->next != NULL)
		search = search->next;
	// 2. link
	search->next = new_node;

	print_all(head);

💎출력💎

===========================================
Head adress = 15228368
15228368 "Aladdin" 8.0 15228696
15228696 "Avatar" 9.5 15262064
15262064 "Wonder Woman" 8.5 0

• 맨 뒤에 추가하기
  • 마지막 노드를 찾는다. 👉 head 처음부터 순차적으로 찾아야 한다. 다음 노드가 NULL 인 노드가 바로 마지막 노드다.
  • 원래의 마지막 노드의 다음 노드에 연결해주면 된다.

✈ 삭제

	/* Find and delete an item */
	search = head;
	p_movie prev = NULL;
	// 삭제할 노드 찾기
	int count = 0;
	while (search != NULL)
	{
		if (strcmp(search->title, "Avatar") == 0) break;

		prev = search;
		search = search->next;
		count++;
	}
	
	if (search == NULL)
	{
		printf("Wrong index\n");
		return;
	}
	// 삭제하기
	if (prev == NULL)
		head = search->next;
	else
		prev->next = search->next;
	free(search);

	print_all(head);

💎출력💎

===========================================
Head adress = 15228368
15228368 "Aladdin" 8.0 15262064
15262064 "Wonder Woman" 8.5 0

• 삭제할 노드를 검색한다. 그 노드의 주소를 search에 담고 그 노드의 이전 노드도 prev에 담는다.
• 이전 노드와 삭제할 노드의 다음 노드를 연결한다. 그리고 삭제할 노드는 해제 시킴!

🚀 연결리스트로 구현한 영화 평점 관리 프로그램

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define TSIZE 45  

struct movie
{
	char title[TSIZE];
	float rating;
	struct movie* next;
};

typedef struct movie* p_movie;

// p_movie* p_head -> 이중 포인터 : head 값이 바껴야 하므로 Call by Reference
void read_file(p_movie* p_head);
int input_menu();
unsigned int count_items(const p_movie head);
void print_all(p_movie head);
void print_an_item(p_movie head);
void edit_an_item(p_movie head);
void add_an_item(p_movie* p_head); // ☆☆ 이중 포인터
void insert_an_item(p_movie* p_head); // ☆☆ 이중 포인터
void delete_an_item(p_movie* p_head);
void delete_all_item(p_movie* p_head);
void write_file(p_movie head);
void search_by_name(p_movie head);

int main()
{
	p_movie head = NULL;

	read_file(&head);

	while (1)
	{
		printf("\n");

		int s = input_menu();

		switch (s)
		{
		case 1:
			print_all(head);
			break;
		case 2:
			print_an_item(head);
			break;
		case 3:
			edit_an_item(head);
			break;
		case 4:
			add_an_item(&head);
			break;
		case 5:
			insert_an_item(&head);
			break;
		case 6:
			delete_an_item(&head);
			break;
		case 7:
			delete_all_item(&head);
			break;
		case 8:
			write_file(head);
			break;
		case 9:
			search_by_name(head);
			break;
		case 10:
			printf("Good bye\n");
			delete_all_item(&head);
			exit(0);
		default:
			printf("%d is not implenmented. \n", s);
		}
	}
}



void read_file(p_movie* p_head) 
{
	char filename[TSIZE] = { 0, };

	printf("Please input filename to read and press Enter.\n");
	printf(">> ");

	if (scanf("%[^\n]%*c", filename) != 1)
	{
		printf("Wrong input. Terminating.\n");
		exit(1);
	}

	FILE* file = fopen(filename, "r");

	if (file == NULL)
	{
		printf("ERROR: Cannot open file. \n");
		exit(1);
	}

	int num;
	if (fscanf(file, "%d%*c", &num) != 1)
	{
		printf("ERROR: Wrong file format. \n");
		exit(1);
	}

	p_movie prev = *p_head;

	for (int n = 0; n < num; ++n)
	{
		p_movie new_movie = (p_movie)malloc(sizeof(struct movie));
		if (new_movie == NULL)
		{
			printf("Malloc failed.\n");
			exit(1);
		}
		
		new_movie->next = NULL;

		if (fscanf(file, "%[^\n]%*c", new_movie->title) != 1 ||
			fscanf(file, "%f%*c", &new_movie->rating) != 1)
		{
			printf("ERROR: Wrong file format. \n");
			exit(1);
		}

		if (prev == NULL)
		{
			*p_head = new_movie;
			prev = new_movie;
		}
		else
		{
			prev->next = new movie;
			prev = new_movie;
		}
	}

	fclose(file);

	printf("%d items have been read from the file.\n", num);
}



int input_int()
{
	int input;

	while (1)
	{
		printf(">> ");
		if (scanf("%d%*c", &input) == 1) return input;
		else
		{
			printf("Please input an integer and press enter. Try again.\n");
			while (getchar() != '\n') continue;
		}
	}
}

int input_menu()
{
	while (1)
	{
		printf("Please select an option and press enter.\n");
		printf("1. Print all items			2. Print an item\n");
		printf("3. Edit an items			4. Add an item\n");
		printf("5. Insert an items			6. Delete an item\n");
		printf("7. Delete all items			8. Save file\n");
		printf("9. Search by name			10. Quit\n");

		int input = input_int();

		if (input >= 0 && input <= 10) return input;
		else printf("%d is invlid. Please try again.\n", input);
	}
}



unsigned int count_items(const p_movie head)
{
	unsigned int count = 0;
	p_movie pnode = head;

	while (pnode != NULL)
	{
		count += 1;
		pnode = pnode->next;
	}

	return count;
}



void print_all(p_movie head)
{
	p_movie pnode = head;

	int count = 0;
	while (pnode != NULL)
	{
		printf("%d : \"%s\", %.1f\n", count, pnode->title, pnode->rating);
		pnode = pnode->next;
		count++;
	}
}

void print_an_item(p_movie head)
{
	printf("Input the index of item to print.\n");
	int index = input_int();

	p_movie pnode = head;

	int count = 0;

	while (pnode != NULL)
	{
		if (count == index) break;
		
		pnode = pnode->next;
		count++;
	}

	if (pnode != NULL)
		printf("%d : \"%s\", %.1f\n", count, pnode->title, pnode->rating);
	else
		printf("Invalid item.\n");
}



void edit_an_item(p_movie head)
{
	printf("Input the index of item to edit.\n");
	int index = input_int();

	p_movie pnode = head;

	int count = 0;

	while (pnode != NULL)
	{
		if (count == index) break;

		pnode = pnode->next;
		count++;
	}

	if (pnode != NULL)
	{
		printf("%d : \"%s\", %.1f\n", index, pnode->title, pnode->rating);

		printf("Input new title and press enter.\n");
		printf(">> ");
		int f = scanf("%[^\n]%*c", pnode->title);
		printf("Input new rating and press enter.\n");
		printf(">> ");
		f = scanf("%f%*c", pnode->rating);

		printf("%d : \"%s\", %.1f\n", index, pnode->title, pnode->rating);
	}
	else
		printf("Invalid item.\n");
}



void add_an_item(p_movie* p_head) // 맨 뒤에 추가ㅣ
{
	printf("Input title and press enter.\n");
	printf(">> ");

	p_movie new_movie = (p_movie)malloc(sizeof(struct movie));
	if (new_movie == NULL)
	{
		printf("Malloc failed\n");
		exit(1);
	}
	
	new_movie->next = NULL;
	
	int f = scanf("%[^\n]%*c", new_movie->title);
	printf("Input rating and press enter.\n");
	printf(">> ");
	f = scanf("%f%*c", &new_movie->rating);

	int count = 0;
	p_movie pnode = *p_head;

	if (pnode == NULL)
		*p_head = new_movie;
	else
	{
		while (pnode->next != NULL)
		{
			pnode = pnode->next;
			count++;
		}
		pnode->next = new_movie;
		count++;
	}

	printf("%d : \"%s\", %.1f\n", count, pnode->title, pnode->rating);
}



void insert_an_item(p_movie* p_head) // 중간에 추가
{
	printf("Input the index of item to insert.\n");
	int index = input_int();

	p_movie pnode = *p_head;
	p_movie prev = NULL;

	int count = 0;
	while (pnode != NULL)
	{
		if (count == index) break;

		prev = pnode;
		pnode = pnode->next;
		count++;
	}

	if (pnode == NULL)
	{
		printf("Wrong index\n");
		return;
	}

	p_movie new_movie = (p_movie)malloc(sizeof(struct movie));
	if (new_movie == NULL)
	{
		printf("Malloc failed\n");
		exit(1);
	}

	new_movie->next = NULL;

	printf("Input title and press enter.\n");
	printf(">> ");
	int f = scanf("%[^\n]%*c", pnode->title);
	printf("Input rating and press enter.\n");
	printf(">> ");
	f = scanf("%f%*c", &pnode->rating);

	printf("%d : \"%s\", %.1f\n", index, pnode->title, pnode->rating);

	if (prev == NULL)
		*p_head = new_movie;
	else
		prev->next = new_movie;
	new_movie->next = pnode;
}



void delete_an_item(p_movie* p_head)
{
	printf("Input the index of item to delete.\n");
	int index = input_int();

	p_movie pnode = *p_head;
	p_movie prev = NULL;

	int count = 0;
	while (pnode != NULL)
	{
		if (count == index) break;

		prev = pnode;
		pnode = pnode->next;
		count++;
	}

	if (pnode == NULL)
	{
		printf("Wrong index\n");
		return;
	}

	if (prev == NULL)
		*p_head = pnode->next;
	else
		prev->next = pnode->next;
	free(pnode);
}



void delete_all_item(p_movie* p_head)
{
	if (*p_head == NULL)
	{
		printf("Nothing to delelte.\n");
		return;
	}

	p_movie search = *p_head;
	p_movie temp = NULL;

	int count = 0;
	while (search != NULL)
	{
		printf("%s is deleted.\n", search->title);
		temp = search->next;
		free(search);
		search = temp;
		count++;
	}

	*p_head = NULL;
	printf("%d items deleted.\n", count);
}



void write_file(p_movie head)
{
	char filename[TSIZE] = { 0, };

	printf("Please input filename to read and press Enter.\n");
	printf(">> ");

	if (scanf("%[^\n]%*c", filename) != 1)
	{
		printf("Wrong input. Terminating.\n");
		exit(1);
	}

	FILE* file = fopen(filename, "w");

	if (file == NULL)
	{
		printf("ERROR: Cannot open file. \n");
		exit(1);
	}

	int count = 0;

	fprintf(file, "%d\n", (int)count_items(head));
	
	p_movie pnode = head;

	while (pnode != NULL)
	{
		fprintf(file, "%s\n", pnode->title);
		fprintf(file, "%.1f\n", pnode->rating);

		pnode = pnode->next;

		count++;
	}

	fclose(file);

	assert(count == (int)count_items(head));

	printf("%d items have been saved to the file.\n", count);
}



void search_by_name(p_movie head)
{
	printf("Please input title to search and press Enter.\n");
	printf(">> ");

	char title[TSIZE] = { 0, };
	if (scanf("%[^\n]%*c", title) != 1)
	{
		printf("Wrong input.\n");
		return;
	}

	p_movie pnode = head;

	int count = 0;
	while (pnode != NULL)
	{
		if (strcmp(pnode->title, title) == 0) break;
		pnode = pnode->next;
		count++;
	}

	if (pnode == NULL)
	{
		printf("No movie found : %s\n", title);
		return;
	}

	printf("%d : \"%s\", %.1f\n", count, pnode->title, pnode->rating);
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

DataStructure2 카테고리 내 다른 글 보러가기