미누에요

스택 응용 문제 중 가장 대표적인 문제가 중위식(Infix)를 후위식(Posfix)로 변환하는 것이다. 우선, 중위식과 후위식에 대해서 간단히 설명하겠다.중위식(Infix)우리가 일반적으로 사용하는 식의 형태연산자가 두 피연산자의 가운데에 위치한다.ex) 2 + 3 * 5 후위식(Posfix) 컴퓨터가 연산을 수행할 때 사용하는 식의 형태연산자가 두 피연산자의 뒤에 위치한다.ex) 2 3 4 * +  우리는 중위식을 입력으로 받아 후위식으로 변환하는 코드를 작성해보겠다.스택을 사용할 것이니 우선 스택 구조를 먼저 작성해준다.#include#define MAX_SIZE 8int top = -1;int stack[MAX_SIZE];int isEmpty(){ if(top==-1) return..

큐(Queue) 위 이미지와 같이 들어온 순서대로 나가게 되는 자료구조이다.First In First Out의 구조를 갖는다.  각 함수에 대해서 간략히 설명하고 넘어가겠다. isEmpty()큐가 비어있는지 검사하는 함수비어있으면 1 반환비어있지 않으면 0 반환 isFull()큐가 가득 차있는지 검사하는 함수연결리스트는 계속해서 확장할 수 있으므로 isFull함수를 사용하지 않는다. Enqueue()큐에 새로운 데이터를 삽입하는 함수새로운 노드를 생성하여 데이터를 저장하고, 그 새로운 노드와 head 노드를 연결한다. Dequeue()큐에 있는 데이터를 삭제, 반환하는 함수가장 처음 들어온 노드의 값을 찾아 반환해야한다.이전 노드의 위치도 기억해야 하므로 prev 포인터 노드와 temp 포인터 노드 두 ..

스택(Stack)    스택은 위 그림과 같이 겹겹이 쌓이는 구조를 뜻한다. 각 함수에 대해서 간략하게 설명하겠다.  isEmpty()스택이 비어있는지 확인하는 함수비어있다면 1을 반환비어있지 않다면 0을 반환 isFull()스택이 가득 차있는지 확인하는 함수연결리스트를 활용한 스택 구현에서는 필요 X연결리스트는 계속해서 연결이 가능하기 때문 Push()값을 삽입하는 함수새로운 노드를 생성하여 값을 저장하고, 기존 연결리스트에 연결한다. Pop()값을 삭제, 반환하는 함수마지막 노드의 값을 임시로 저장해두고, 삭제한 후에 임시로 저장한 값을 반환한다. printData()연결리스트에 연결된 값들을 차례로 출력하는 함수   구현한 코드#include#includetypedef struct _stack { ..

전위 표기법(prefix)연산자가 피연산자의 앞에 오게되는 표기법을 의미한다.+32 예를 들어, 3+5*2라는 식을 전위 표기법으로 바꾼다면, 우선순위를 정하여 괄호를 친다.(3+(5*2)) -> 3+(*52) -> +3*52 위와 같은 순서로 전위식을 구해낼 수 있다.   중위 표기법(infix)우리가 보통 수식을 적을 때 사용하는 방법이다.3+2 중위 표기법은 사람이 보통 사용하는 방법이기에, 컴퓨터가 인식할 수 있도록 변환하여 사용하게 된다.   후위 표기법(postfix)연산자가 뒤쪽에 있고 피연산자가 앞쪽에 위치한 식을 의미한다.32+ 컴퓨터는 수식을 후위 표기법 방식으로 인식한다. 중위식인 3+5*2를 마찬가지로 후위식으로 변환한다면, 괄호를 사용하면 쉽다.3+5*2 -> (3+(5*2)) -..

문제 보통 자료구조 과목에서 중위 표기법의 소괄호 출력까지 신경을 쓰지는 않는다.순회 자체를 더 중요시하기 때문이다.하지만 이는 여러분이 궁금해 할 수 있는 부분이다.그래서 소괄호의 출력을 위한 힌트를 제시하고 문제의 해결을 돕기로 하겠다. 먼저 다음 세 중위 표기법을 보자. 3 + 2 * 73 + ( 2 * 7 )( 3 + ( 2 * 7 ) )셋 다 그 내용이 동일한 수식이다. 따라서 이를 수식 트리로 표현하면 그 결과는 당연히 같을 수밖에 없다. 같지 않다면 잘못된 것이다. 자! 그럼 생각해보자. 위 수식을 표현한 수식 트리 각각을 대상으로 다음과 같이 요청을 한다면,이 수식 트리에 담긴 수식을 중위 표기법의 수식으로 출력하여라!어떻게 출력이 이루어지겠는가 ? 첫 번째 수식을 대상으로 만들어진 수식 ..

문제 우리가 구현한 이진 트리에는 소멸관련 함수가 정의되어 있지 않다. 때문에 예제에서는 동적으로 할당된 노드를 소멸시키지는 않고 프로그램 종료하였다.따라서 이진트리를 완전히 소멸시키는 함수를 다음과 같이 선언하고 정의하고자 한다. void DeleteTree(BTreeNode * bt); 위 함수가 정의되면, 이는 다음과 같이 호출되어야한다. int main(void){ BTreeNode * bt1 = MakeBTreeNode(); . . . . DeleteTree(bt1); . . . .}  그리고 위와 같이 DeleteTree 함수가 호출되면, bt1 이 가리키는 노드를 루트 노드로 하는 트리 전부가 완전히 소멸되어 한다. 그럼 앞서 완성한 BinaryTree.h 와 BinaryTre..

큐(Queue) 선입선출(FIFO, First in Finst out)의 구조이다.일상생활에서 많이 사용되는 자료구조이다.대기번호처럼 순서대로 출력과 입력이 이루어진다.변수로는 front, rear를 사용한다.두 변수의 초기값은 -1이며, Enqueue(삽입)은 rear에서, Dequeue(삭제)는 front에서 이루어진다.  배열을 사용한 큐배열을 사용하면 공간의 크기가 정적이다.이러한 점을 보완하기 위해 원형 배열을 사용한다.     isEmpty()front와 rear가 같은 값이라면 그 큐는 비어있는 상태이다.int isEmptyQ(){ if (front == rear) return 1; else return 0;}  isFull()front가 rear의 바로 ..

스택(Stack)선입후출(First-in Last-out)의 구조이다.자료들이 계속해서 겹겹이 쌓이는 형태를 나타낸다.상단의 위치를 나타내는 top을 변수로 가진다.top의 초기값은 -1이다.top이 -1일 때 이 스택은 비어있는 스택이다.   isEmpty()top이 -1이라면 true그 외의 경우는 falseint isEmpty(){ if (top == -1) return 1; else return 0;}  isFull()top이 (스택 크기-1)이면 true를 반환그 외의 경우는 falseint isFull(){ if (top == STACK_SIZE - 1) return 1; else return 0;}  Push(int va..

양방향 연결리스트(Doubly Linked List)연결 리스트에서 데이터의 삽입을 할 때, head 의 위치에 따라 마지막 노드의 위치를 찾아야하는 경우가 발생한다.기존의 연결 리스트는 이전 노드로 돌아가지 못한다. 양방향 연결리스트는 노드의 링크가 두 개씩 달려있다.typedef struct _doubNode{ struct _doubNode *prev; int data; struct _doubNode *next;} DNode;  다음으로 각 기능별 함수에 대해 설명하겠다. 1. 앞 부분에서 데이터를 삽입하는 함수 양쪽 다 link가 있으므로 모두 수정해줘야 한다.void AddFront(DNode **head, int val){ DNode *temp = *head; DNod..

원형 연결 리스트(Circular Linked List) - 마지막 노드가 처음의 노드를 가리키는 형태(마지막 노드가 NULL이 아닌 처음 노드를 가리킨다.)   일반적인 단일 연결 리스트(Single Linked List)와 가장 큰 차이점은 마지막 노드의 link가 NULL이 아닌 처음 노드를 가리킨다는 것이다.대략적으로 나타낸다면 아래와 같을 것이다.마지막노드.link = head;  이제 원형 연결 리스트의 각 함수들에 대하여 알아보겠다.  1. 원형 리스트의 앞부분에 노드를 삽입 위 순서대로 코드를 구현하면 된다.여기서 신경써야 할 점은 연결 리스트를 탐색하며 마지막 노드를 찾아야 한다는 점이다. void FAddNode(Node **head, int val){ Node *newnode =..