C언어로 구현한 자료구조 회고

https://github.com/IMGyuGo/data_structure_docker/tree/main/Data-Structures

data_structure_docker/Data-Structures at main · IMGyuGo/data_structure_docker

https://github.com/IMGyuGo/KraftonJungleTIL/tree/main/SQL%EC%B2%98%EB%A6%AC%EA%B8%B0/%EC%9A%94%EC%95%BD%EB%B3%B8

KraftonJungleTIL/SQL처리기/요약본 at main · IMGyuGo/KraftonJungleTIL

- 실제로 회고록이라 볼 필요는 없는데 제가 이번 주 한 주를 정리하면서 직접 보기 위해 만들어 놓은 바로가기 입니다.

- 만약 이 글을 보시는 분이 계신다면, 두번째에 있는 파일에서 sql 처리기 요약본.pdf를 다운받아 1~10page정도만 읽으면 C언어의 포인터에 대해 조금, c언어 내부 라이브러리에 대한 내용 조금 이해에 도움이 되실 수 있을 것 같아요~!

Linked List

노드가 데이터 + 다음 노드 주소(pointer)를 가지는 주소
메모리에 연속적으로 저장되지 않음

특징
삽입/삭제 빠름 : O(1)
탐색 느림 : O(n)
인덱스 접근 불가능

Stack & Queue

Stack
LIFO (Last In First Out)
마지막에 넣은 것이 먼저 나옴
Queue
FIFO (First In First Out)
먼저 들어온 것이 먼저 나옴

Binary Tree

각 노드가 최대 2개의 자식을 가지는 노드 (이진 트리)
마지막 리프 빼고 모두 꽉 차있고, 마지막 리프는 왼쪽 부터 채워지는 노드 (완전 이진 트리)
각 노드가 반드시 2개의 자식을 가지는 노드 (포화 이진 트리)

특징
계층 구조 표현에 적합
재귀적으로 다루기 쉬움

순회 방식
전위 (Preorder) : Root -> Left -> Right
중위 (InOrder) : Left -> Root -> Right
후위 (PostOrder) : Left -> right -> Root

 

Binary Seacrh Tree

이진트리 + 정렬조건
왼쪽 : 작은 값 , 오른쪽 : 큰 값

탐색/삽입/삭제 : 평균 O(log n)
최악 : O(n) [편향트리일 경우]

 

알고리즘 구현 복기

ⓐ. 구조체 설계(Linked List)

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode; // ListNode 구조체

// [ next : 다음 노드를 가리키는 포인터 ]
// [ item : 노드가 저장하는 실제 값 ]

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList; // LinkedList 구조체

// [ head : 첫번째 노드를 가리키는 시작점 ]
// [ size : linkedlist 안의 ListNode 개수 ]

ⓑ. 이미 구현되어 있던 함수 설명(Linked List)

// LinkedList 전체 item 출력
void printList(LinkedList *ll)
{
	// 현재 노드 생성
	ListNode *cur;
	if (ll == NULL)
		return;
    // 현재 linkedList의 첫번째 노드를 현재 노드에 할당
	cur = ll->head;

	// 만약 비어 있다면, Empty 출력
	if (cur == NULL)
		printf("Empty");
    // 현재가 NULL일 경우까지 돌면서 (*cur).item 출력
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}

// LinkedList 전체 item 제거
void removeAllItems(LinkedList *ll)
{
	// 현재 노드에 linkedlist의 첫번째 노드 할당
	ListNode *cur = ll->head;
    // tmp 노드 생성
	ListNode *tmp;

	// tmp 노드에 다음 값을 넣고 free로 메모리 반환 후 cur 노드에 다음 노드값 할당
	while (cur != NULL)
	{
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}

// LinkedList의 특정 index 값 출력
ListNode *findNode(LinkedList *ll, int index)
{
	// 임시 노드 생성
	ListNode *temp;

	// 만약 인덱스가 -1이 되거나, index가 size보다 크거나, ll이 비어있다면 종료
	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	// 임시 노드에 LinkedList의 첫번째 노드 할당
	temp = ll->head;

	// 임시노드가 비어있거나 index가 -1이 되면 종료 (index < 0은 위에 있으므로 필요없긴 함)
	if (temp == NULL || index < 0)
		return NULL;

	// 임시노드를 다음 노드로 옮기면서 index가 -1이 될때까지 반복
	while (index > 0)
	{
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

// LinkedList의 특정 index에 특정 value 값 삽입
int insertNode(LinkedList *ll, int index, int value)
{

	// 이전 노드와 현재 노드를 생성
	ListNode *pre, *cur;

	// index가 -1이거나 ll의 size보다 크거나 ll이 Null일 경우 종료
	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// 빈 리스트이거나 첫 노드에 삽입하는 경우 head 포인터를 갱신해야 함
	if (ll->head == NULL || index == 0)
	{
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// 삽입 위치의 이전 노드를 찾고
	// 새 노드를 생성해 링크를 다시 연결
	if ((pre = findNode(ll, index - 1)) != NULL)
	{
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

// 특정 index의 노드를 삭제
int removeNode(LinkedList *ll, int index)
{

	ListNode *pre, *cur;

	// 삭제 가능한 최대 인덱스는 size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// 첫 노드를 삭제하는 경우 head 포인터를 갱신해야 함
	if (index == 0)
	{
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	// 삭제 대상 위치의 이전/다음 연결을 확인하고
	// 대상 노드를 해제한 뒤 링크를 다시 연결
	if ((pre = findNode(ll, index - 1)) != NULL)
	{

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

LinkdedList 구현을 예로 들면, 위와 같은 함수가 우선 구현되어 있고 문제를 푸는 방식으로 진행했다.

/*
int insertSortedLL(LinkedList *ll, int item);
정수 하나를 입력받아, 오름차순 정렬 상태를 유지하도록 연결 리스트에 삽입하는 C 함수

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2);
두 번째 리스트의 노드를 첫 번째 리스트의 교차 위치에 삽입하는 함수

void moveOddItemsToBack(LinkedList *ll);
리스트의 홀수 값들을 뒤쪽으로 이동시키는 함수

void moveEvenItemsToBack(LinkedList *ll);
리스트의 짝수 값들을 뒤쪽으로 이동시키는 함수

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList);
단일 연결 리스트를 앞/뒤 두 개의 서브리스트로 분할하는 함수

int moveMaxToFront(ListNode **ptrHead);
정수 연결 리스트를 최대 한 번 순회하여, 가장 큰 값을 가진 노드를 리스트 맨 앞으로 이동시키는 함수

void RecursiveReverse(ListNode **ptrHead);
연결 리스트의 next 포인터와 head 포인터를 변경하여, 리스트를 재귀적으로 역순으로 바꾸는 함수
*/

int insertSortedLL(LinkedList *ll, int item);
void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2);
void moveOddItemsToBack(LinkedList *ll);
void moveEvenItemsToBack(LinkedList *ll);
void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList);
int moveMaxToFront(ListNode **ptrHead);
void RecursiveReverse(ListNode **ptrHead);

 

이것 말고 Stack & Queue, Binary Tree, Binary Search Tree에 대해서도 똑같이 이미 구현되어 있는 함수가 있고 그것 외로 구현해야할 목표에 따라 직접 풀어보는 방식으로 이번 한 주의 알고리즘 과정을 수행하였다.

 

C언어를 너무 오랜만에 하기도 하고 직접 개발해본 적이 없어 완전 어렵고 힘들줄 예상했는데 ‼️

생각보다 잘 주어져 있던 조건들 덕분에 구현하는 데 최대한 힘을 쓰지 않고 문제를 풀어보고 바로 답을 보면서 실제로 함수와 구조체를 통해 구현하는 과정과 흐름을 이해할 수 있었고, 무지몽매했던 C언어에 대해 어느정도 한을 풀어볼 수 있었던 한 주였다.