Krafton_jungle 5기 27일차 TIL - 자료구조

자료구조

 

Stack and Queues 기본 제공 함수

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section C - Stack and Queue Questions
Purpose: Implementing the required functions for Question 1 */

//////////////////////////////////////////////////////////////////////////////////

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

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;	// You should not change the definition of ListNode

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;	// You should not change the definition of LinkedList


typedef struct _queue
{
	LinkedList ll;
} Queue;  // You should not change the definition of Queue

///////////////////////// function prototypes ////////////////////////////////////

// You should not change the prototypes of these functions
void createQueueFromLinkedList(LinkedList *ll, Queue *q);
void removeOddValues(Queue *q);

void enqueue(Queue *q, int item);
int dequeue(Queue *q);
int isEmptyQueue(Queue *q);
void removeAllItemsFromQueue(Queue *q);

void printList(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);
void removeAllItems(LinkedList *ll);

//////////////////////////// main() //////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////

void enqueue(Queue *q, int item) {
	insertNode(&(q->ll), q->ll.size, item);
}

int dequeue(Queue *q) {
	int item;

	if (!isEmptyQueue(q)) {
		item = ((q->ll).head)->item;
		removeNode(&(q->ll), 0);
		return item;
	}
	return -1;
}

int isEmptyQueue(Queue *q) {
	if ((q->ll).size == 0)
		return 1;
	return 0;
}

void removeAllItemsFromQueue(Queue *q)
{
	int count, i;
	if (q == NULL)
		return;
	count = q->ll.size;

	for (i = 0; i < count; i++)
		dequeue(q);
}

void push(Stack *s, int item)
{
	insertNode(&(s->ll), 0, item);
}

int pop(Stack *s)
{
	int item;
	if (s->ll.head != NULL)
	{
		item = ((s->ll).head)->item;
		removeNode(&(s->ll), 0);
		return item;
	}
	else
		return MIN_INT;
}

int isEmptyStack(Stack *s)
{
	if ((s->ll).size == 0)
		return 1;
	else
		return 0;
}


void removeAllItemsFromStack(Stack *s)
{
	if (s == NULL)
		return;
	while (s->ll.head != NULL)
	{
		pop(s);
	}
}



void printList(LinkedList *ll){

	ListNode *cur;
	if (ll == NULL)
		return;
	cur = ll->head;
	if (cur == NULL)
		printf("Empty");
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}


void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;
	ListNode *tmp;

	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}


ListNode * findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// If empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		if (ll->head == NULL)
		{
			exit(0);
		}
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}


	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		if (pre->next == NULL)
		{
			exit(0);
		}
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}


int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;
		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	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;
}

 

기본적으로 제공되는 함수들. 이 함수들을 사용해서 Stack and Queues를 구현할것이다.

 

Stack and Queues Q1 - createQueueFromLinkedList

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	if (isEmptyQueue(q)) {
		removeAllItemsFromQueue(q);
	}
	ListNode* cur = ll->head;
	while (cur != NULL) {
		enqueue(q, cur->item);
		cur = cur->next;
	}
}

LL을 받아와서 queue에 집어넣는 코드

현재 노드를 queue에 집어넣기만 하면 끝

 

 

Stack and Queues Q2 - createStackFromLinkedList

void createStackFromLinkedList(LinkedList *ll, Stack *s)
{
	if (isEmptyStack(s) == 1) {
		removeAllItemsFromStack(s);
	}
	ListNode* cur = ll->head;
	while (cur != NULL) {
		push(s, cur->item);
		cur = cur->next;
	}
}

이 코드도 마찬가지로 LL에 받아와서 stack에 집어넣는 코드.

기본적으로 제공해주는 함수를 이용하면 쉽게 구현할 수 있었음

 

 

Stack and Queues Q3 - isStackPairwiseConsecutive

int isStackPairwiseConsecutive(Stack *s)
{
    if(s->ll.size == 0 || s->ll.size % 2 != 0)
        return 0;

    while(!isEmptyStack(s))
    {
        //check difference in the pairs
        if(abs(pop(s) - pop(s)) != 1)
            return 0;
    }

    return 1;
}

스택에 저장된 값과 바로 다음 값이 연속되지 않았을때 False를 리턴하는 코드

절대값으로 계산해서 연속되는지 유무를 파악하고 있다.

 

 

Stack and Queues Q4 - reverse

void reverse(Queue *q)
{
	// 초기화 필수!
	Stack s;
	s.ll.head = NULL;
	s.ll.size = 0;

	while(!isEmptyQueue(q)) {
		int item = dequeue(q);
		push(&s, item);
	}
	while(!isEmptyStack(&s)) {
		int item = pop(&s);
		enqueue(q, item);
	}
}

말 그대로 queue를 뒤집는 코드.

스택의 특징을 사용해서 스택에 우선 값을 저장해놨다가, pop해서 queue에 다시 저장하는 식으로 구현했다.

 

 

Stack and Queues Q5 - recursiveReverse

void recursiveReverse(Queue *q)
{
	// 반환조건
	if (q->ll.head == NULL) return;
	int cur = dequeue(q);
	recursiveReverse(q);
	enqueue(q, cur);
}

queue가 빌때까지 dequeue로 값을 빼내서 다시 queue에 넣어버리는 간단한 코드

 

 

Stack and Queues Q6 - removeUntil

void removeUntil(Stack *s, int value)
{
	// 만약 stack 이 이미 비어있으면 return
	if (s->ll.size == 0) {
		return;
	}
	while (s->ll.head->item != value) {
		pop(s);
	}
}

지정한 값이 나올때까지 stack을 pop하는 간단한 로직

 

 

Stack and Queues Q7 - balanced

int balanced(char *expression)
{
	// 비어있는 stack 생성
	Stack s;
	s.ll.head = NULL;
	s.ll.size = 0;

	while (*expression) {
		char cur = *expression;
		if (cur == '(' || cur == '[' || cur == '{') {
			push(&s, cur);
		// 만약 닫는 문자열인데 stack에 아무런 값이 없으면
		} else if (cur == ')' || cur == ']' || cur == '}') {
			if (isEmptyStack(&s)) {
				return 1;
			}
			char pair = pop(&s);
			if (
				(cur == ')' && pair != '(') ||
				(cur == '}' && pair != '{') ||
				(cur == ']' && pair != '[')) {
				return 1;
			}
		}
		expression++;
	}
	if (!isEmptyStack(&s)) {
		return 1;
	}
	return 0;
}

예전 백준 문제에서 비슷한 문제를 풀어봐서 어렵지 않게 풀었음.

stack에 char를 넣어놨다가 대칭일때만 pop해주는 방법

 

 

Binary Tree 기본 제공 함수

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section E - Binary Trees Questions
Purpose: Implementing the required functions for Question 1 */

//////////////////////////////////////////////////////////////////////////////////

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

//////////////////////////////////////////////////////////////////////////////////
typedef struct _btnode{
	int item;
	struct _btnode *left;
	struct _btnode *right;
} BTNode;   // You should not change the definition of BTNode

/////////////////////////////////////////////////////////////////////////////////

typedef struct _stackNode{
    BTNode *btnode;
    struct _stackNode *next;
}StackNode;

typedef struct _stack{
    StackNode *top;
}Stack;

///////////////////////// function prototypes ////////////////////////////////////

// You should not change the prototypes of these functions
int identical(BTNode *tree1, BTNode *tree2);

BTNode* createBTNode(int item);

BTNode* createTree();
void push( Stack *stk, BTNode *node);
BTNode* pop(Stack *stk);

void printTree(BTNode *node);
void removeAll(BTNode **node);

///////////////////////////// main() /////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////////////

BTNode *createBTNode(int item){
    BTNode *newNode = malloc(sizeof(BTNode));
    newNode->item = item;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}


BTNode *createTree()
{
    Stack stk;
    BTNode *root, *temp;
    char s;
    int item;

    stk.top = NULL;
    root = NULL;

    printf("Input an integer that you want to add to the binary tree. Any Alpha value will be treated as NULL.\n");
    printf("Enter an integer value for the root: ");
    if(scanf("%d",&item) > 0)
    {
        root = createBTNode(item);
        push(&stk,root);
    }
    else
    {
        scanf("%c",&s);
    }

    while((temp =pop(&stk)) != NULL)
    {

        printf("Enter an integer value for the Left child of %d: ", temp->item);

        if(scanf("%d",&item)> 0)
        {
            temp->left = createBTNode(item);
        }
        else
        {
            scanf("%c",&s);
        }

        printf("Enter an integer value for the Right child of %d: ", temp->item);
        if(scanf("%d",&item)>0)
        {
            temp->right = createBTNode(item);
        }
        else
        {
            scanf("%c",&s);
        }

        if(temp->right != NULL)
            push(&stk,temp->right);
        if(temp->left != NULL)
            push(&stk,temp->left);
    }
    return root;
}

void push( Stack *stk, BTNode *node){
    StackNode *temp;

    temp = malloc(sizeof(StackNode));
    if(temp == NULL)
        return;
    temp->btnode = node;
    if(stk->top == NULL){
        stk->top = temp;
        temp->next = NULL;
    }
    else{
        temp->next = stk->top;
        stk->top = temp;
    }
}

BTNode* pop(Stack *stk){
   StackNode *temp, *top;
   BTNode *ptr;
   ptr = NULL;

   top = stk->top;
   if(top != NULL){
        temp = top->next;
        ptr = top->btnode;

        stk->top = temp;
        free(top);
        top = NULL;
   }
   return ptr;
}

void printTree(BTNode *node){
    if(node == NULL) return;

    printTree(node->left);
    printf("%d ",node->item);
    printTree(node->right);
}

void removeAll(BTNode **node){
    if(*node != NULL){
        removeAll(&((*node)->left));
        removeAll(&((*node)->right));
        free(*node);
        *node = NULL;
    }
}

마찬가지로 이 함수들을 응용해서 문제를 풀이할것이다.

 

 

Binary Tree Q1 - identical

int identical(BTNode *tree1, BTNode *tree2)
{
    // 두개의 트리가 모두 비어있으면
    if (tree1 == NULL && tree2 == NULL) {
        return -1;
    } 
    // 두개의 트리중 하나만 비어있으면
    if (tree1 == NULL || tree2 == NULL) {
        return 0;
    } 
    // 두개의 트리의 값이 다르면
    if (tree1->item != tree2->item) {
        return 0;
    } 
    // 재귀적으로 트리를 탐색
    return identical(tree1->left, tree2->left) && identical(tree1->right, tree2->right);
}

두개의 트리가 완전히 대칭인지 확인하는 함수.

재귀를 사용해서 모든 트리의 구조를 탐색하고, 결과값을 반환한다.

 

 

Binary Tree Q2 - maxHeight

int maxHeight(BTNode *node)
{
    if (node == NULL) {
        return -1;
    }
    else {
        int left_height = maxHeight(node->left);
        int right_height = maxHeight(node->right);
        if (left_height <= right_height) {
            return right_height + 1;
        } else {
            return left_height + 1;
        }
    }
}

가장 깊은 자식 노드의 계층을 찾는 코드.

재귀적으로 파고들며 가장 큰 값을 리턴하고, 만약 탐색하려는 노드가 NULL이면 -1연산을 수행해준다.

그렇게 나온 결과값에 가장 큰 수를 return

 

 

Binary Tree Q3 - countOneChildNodes

int countChildNodes(BTNode *node) 
{
    int count = 0;
    if (node->left != NULL) {
        count += 1;
    }
    if (node->right != NULL) {
        count += 1;
    }
    return count;

}


int countOneChildNodes(BTNode *node)

{
    if (countChildNodes(node) == 0) 
    {
        return 0;
    }

    int count = 0;

    if (countChildNodes(node) == 1) 
    {
        return 1;
    }
    count += countOneChildNodes(node->left);
    count += countOneChildNodes(node->right);

    return count;
}

자식 노드의 수가 1개인 노드의 개수를 return하는 함수

난 이 함수를 2개로 나눠서 구현했는데, 첫번째로는 해당 노드의 자식 노드를 탐색하는 함수,

두번째로는 모든 노드를 순회하며 첫번째 함수를 실행하는 함수를 작성해서 풀었다.

 

 

Binary Tree Q4 - sumOfOddNodes

int sumOfOddNodes(BTNode *node)

{
    int count = 0;
    if (node == NULL) {
        return 0;
    }
    if (node->item % 2 != 0) {
        return node->item;
    }
    count += sumOfOddNodes(node->left);
    count += sumOfOddNodes(node->right);
    return count;
}

노드의 item값이 홀수일때 그 값을 더한 count를 return하는 함수

 

 

Binary Tree Q5 - mirrorTree

void mirrorTree(BTNode *node)
{
    if (node == NULL) {
        return;
    }
    BTNode *tmp = node -> right;
    node -> right = node -> left;
    node -> left = tmp;
    mirrorTree(node->left);
    mirrorTree(node->right);
}

트리를 좌우대칭이 되도록 수정하는 함수.

설명듣고 겁먹었는데 생각해보니 그냥 좌우 노드만 바꿔주면 되는거라서 쉽게 풀었다.

 

 

Binary Tree Q6 - printSmallerValues

void printSmallerValues(BTNode *node, int m)
{
    if (node == NULL) {
        return;
    }

    if (node->item < m) {
        printf("%d ", node->item);
    }
    printSmallerValues(node->left, m);
    printSmallerValues(node->right, m);

}

내가 입력한 값보다 작은 값을 지닌 노드를 모두 출력하는 코드.

마찬가지로 재귀로 표현했다.

 

 

Binary Tree Q7 - smallestValue

int smallestValue(BTNode *node)
{
    if (node == NULL) {
        return __INT_MAX__;
    }
    int cur = node->item;
    int left = smallestValue(node->left);
    int right = smallestValue(node->right);

    if (cur <= left && cur <= right)
        return cur;
    else if (left <= cur && left <= right)
        return left;
    else
        return right;
}

모든 노드중 가장 작은 값을 출력하는 함수.

마찬가지로 재귀로 구현했으며 return 구문이 사용되는 부분은 자칫 복잡해보일수도 있으나 풀이해보면

max(cur, left, right)랑 똑같은 작업을 한다.

 

 

Binary Tree Q8 - maxHeght

int maxHeght(BTNode *node) 
{
    if (node == NULL) {
        return -1;
    }
    else {
        int left_height = maxHeght(node->left);
        int right_height = maxHeght(node->right);
        if (left_height <= right_height) {
            return right_height + 1;
        } else {
            return left_height + 1;
        }
    }
}


int hasGreatGrandchild(BTNode *node)
{
    if (node == NULL) {
        return 0;
    }
    int res = maxHeght(node);
    if (res > 3) 
    {
        printf("%d \n", node->item);
    }
    int res_left = hasGreatGrandchild(node->left);
    int res_right = hasGreatGrandchild(node->right);
	/* add your code here */
    return 1;
}

증손자 노드를 가지고 있는 노드만 출력하는 함수.

이번 코드도 2개의 기능을 하도록 나눴는데, 첫번째 함수는 자신의 자식 노드들이 몇계층까지 있는지 그 수를 반환하는 코드고,

두번째 함수는 그 수가 3개 이상이면 출력하고, 계속 탐색을 이어가는 함수이다.

 

 

 

지금은 binary search tree를 구현하고 있는데 모두 풀이하면 업로드 해야겠다.