안경잡이개발자

728x90
반응형

  스택(Stack)을 구현하는 방법은 크게 단순 배열(Array)을 이용한 방법과 단방향 연결 리스트(Linked List)를 이용한 방법이 있습니다. 이번 시간에는 연결 리스트(Linked List)를 이용한 방법에 대해 간단히 알아보도록 하겠습니다.


※ 스택 선언하기 ※


  스택 선언은 기존의 연결 리스트와 동일하게 진행합니다.


----------------------------------------------------------------


#include <stdio.h>

#include <stdlib.h>


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

} Node;


NodePointer top = NULL;


----------------------------------------------------------------


※ 스택에 삽입하기 ※


  스택 삽입도 기존의 연결 리스트와 흡사하게 진행합니다. 다만 단방향이라서 top을 기준으로만 삽입해주면 됩니다.


----------------------------------------------------------------


int push(int data) {

NodePointer ptr;

ptr = (NodePointer) malloc(sizeof(Node));

// 컴퓨터에 남은 메모리가 없는 경우 

if(ptr == NULL) {

printf("메모리 할당에 실패했습니다.\n");

return -1;

}

ptr->data = data;

// 스택이 비어있는 경우 

if(top == NULL) {

ptr->next = NULL;

}

// 스택이 비어있지 않은 경우

else {

ptr->next = top;

}

// 새 노드를 최상단 노드로 설정합니다. 

top = ptr;

return 1;

}


----------------------------------------------------------------


※ 스택 정보 출력하기 ※


  top부터 출발해서 NULL을 만날 때까지 모든 원소를 출력해주기만 하면 됩니다.


----------------------------------------------------------------


void show() {

NodePointer ptr = top;

while(ptr != NULL) {

printf("%d\n", ptr->data);

ptr = ptr->next;

}

}


int main(void) {

push(5);

push(7);

push(3);

show();

return 0;

}


----------------------------------------------------------------


  실행 결과는 다음과 같습니다.




728x90
반응형

728x90
반응형

  이번 시간에는 이중 연결 리스트(Double Linked List)에 대해서 알아보도록 하겠습니다. 이중 연결 리스트는 말 그대로 모든 노드가 이전 노드와 다음 노드에 대한 정보를 모두 저장하고 있는 리스트를 의미합니다. 표현해보면 다음과 같이 표현할 수 있습니다.



※ 선언하기


------------------------------------------------------------


#include <stdio.h>

#include <stdlib.h>


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer prev;

NodePointer next;

} Node;


NodePointer head, tail;


------------------------------------------------------------


※ 삽입 함수 ※


  삽입이 이루어질 때는 기본적으로 자신이 들어갈 위치를 찾습니다. 저는 data를 기준으로 오름차순 정렬이 이루어지도록 삽입 함수를 작성했습니다. 이 때 i라는 별도의 변수가 사용됩니다. 결과적으로 i는 삽입될 직전의 위치를 알려주는 역할을 수행합니다. 이후에 총 4번 링크를 수행해 새로운 변수를 삽입하게 됩니다. 그 형태는 다음과 같습니다.



------------------------------------------------------------


void insert(int data) {

NodePointer i, element;

i = head->next;

while(i->data <= data && i != tail)

i = i->next;

element = (NodePointer) malloc (sizeof(Node));

element->data = data;

i->prev->next = element;

element->prev = i->prev;

i->prev = element;

element->next = i;

}


------------------------------------------------------------


※ 출력하기 ※


  출력할 때는 head의 next부터 하나씩 tail에 도달하기 전까지 노드를 방문해 출력하면 됩니다.


------------------------------------------------------------


void show() {

NodePointer i;

i = head->next;

while(i != tail) {

printf("%d ", i->data);

i = i->next;

}

}


------------------------------------------------------------


※ 실제로 사용하기 ※


  초기 상태를 다음과 같이 설정해주어야 한다는 것만 잊지 않으시면 됩니다.



------------------------------------------------------------


int main(void) {

head = (NodePointer) malloc (sizeof(Node));

tail = (NodePointer) malloc (sizeof(Node));

head->next = tail;

head->prev = head;

tail->next = tail;

tail->prev = head;

insert(7);

insert(1);

insert(8);

show();

return 0;

}


------------------------------------------------------------


  실행 결과는 다음과 같습니다.



728x90
반응형

728x90
반응형

  연결 리스트(Linked List)포인터를 이용한 선형 구조로서 다양한 종류가 있습니다. 대표적인 것이 선형 리스트, 원형 리스트, 연결 스택, 연결 큐 등이 있습니다. 연결 리스트는 일반적으로 시험 문제로 출제가 될 때 실제 소스코드 구현과 관련한 문제가 출제된다는 점에서 포인터(Pointer)를 활용한 실질적인 구현 방법에 대해서 이해하고 있으셔야 합니다. 다만 이후에 트리(Tree) 구조 등과 관련한 개념에서는 실질적인 구현을 물어보지는 않고 그 동작 원리에 대해서만 자세히 물어본다는 특징이 있습니다.


  사실 연결 리스트는 단일 연결리스트만 확실히 이해해도 다른 것들은 무난하게 넘어가실 수 있습니다. 대표적인 단일 연결 리스트(Singly Linked List)의 예제에 대해서 알아보도록 합시다.


※ 삽입 함수 ※


-----------------------------------------------


struct Student {

int id; /* 학번 */

int score; /* 학생 성적 */

struct Student *next; 

};


-----------------------------------------------

  위와 같이 하나의 학생(Student)이라는 노드를 정의해봅시다. 이를 단일 연결리스트로 표현하면 다음과 같은 형태가 될 것입니다.



  삽입 함수는 매우 기본적인 로직을 따릅니다. 단순히 자신이 들어갈 위치까지 계속해서 넘어가다가 들어갈 위치를 찾으면 비로소 그 때 들어가면 됩니다. 기본적으로 사용자 정보들은 학번을 기준으로 오름차순으로 정렬되고, 동일한 학번은 입력되지 않는다고 했을 때 삽입(Insert) 함수는 다음과 같이 작성될 수 있습니다.


-----------------------------------------------


void insert(struct Student **head, int id, int score) {

struct Student *prevptr; // 삽입하려는 위치의 직전 노드 

struct Student *ptr; // 삽입하려는 위치의 노드

struct Student *element; // 삽입하려는 노드

element->id = id;

element->score = score;

element->next = NULL;

// 리스트가 비어있는 경우 

if((*head) == NULL) {

(*head) = element;

return;

// 리스트가 비어있지 않은 경우 

prevptr = NULL;

ptr = (*head);

while(ptr != NULL) {

// 들어갈 위치를 찾지 못한 경우 

if(ptr->id < id) {

prevptr = ptr;

ptr = ptr->next;

}

// 들어갈 위치를 찾은 경우 

else {

// 첫 번째 원소로 들어가는 경우 

if(prevptr == NULL) (*head) = element;

// 첫 번째 원소로 들어가지 않는 경우 

else prevptr->next = element;

element->next = ptr;

return;

}

}

// 마지막 원소로 들어가는 경우

ptr->next = element; 

}


-----------------------------------------------


※ 역체인 ※


  역체인(Reverse Chain)은 연결리스트를 뒤집는 함수입니다. 만약 1부터 4까지 데이터가 노드로 연결이 되어있다면 다음과 같이 4부터 1까지 데이터가 노드로 연결이 되도록 바꾸는 과정이 역체인 과정이라고 할 수 있습니다.



-----------------------------------------------


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

};


-----------------------------------------------


  위와 같이 노드가 선언이 되어있다고 했을 때 역체인 함수는 다음과 같이 구현할 수 있습니다.


-----------------------------------------------


void reverse(NodePointer *head) {

NodePointer one, two, three;

int cout = 0;

two = NULL;

one = three = *head;

while(three != NULL) {

three = three->next;

// 실질적으로 역체인이 수행되는 라인 

two->next = one; 

one = two;

two = three;

}

}


-----------------------------------------------

  처음 보았을 때는 어렵게 느껴질 수 있는데 간단히 생각해보면 다음과 같이 동작하는 겁니다. 연결되어있는 링크의 위치를 반대로 뒤집으려면 총 세 개의 변수가 필요한데 one, two, three 변수를 계속해서 오른쪽으로 이동시켜가며 역으로 연결해주는 거에요.





728x90
반응형

728x90
반응형

본 포스팅에는 오류가 있습니다. 시간날 때 수정하겠습니다.


  일반적으로 우리가 알고 있는 대수학의 표기법인 중위 표기법을 컴퓨터에게 계산하도록 만들고 싶으면 후위 표기법으로 변환한 뒤에 계산하는 과정이 필요합니다. 실제로 계산기 등이 내부적으로 수행하고 있는 방법이기도 합니다. 재미있는 점은 중위 표기법을 후위 표기법으로 바꿀 때는 오직 스택(Stack)만 있으면 됩니다. 스택을 적절히 활용하면 처리할 수 있다는 점이 매우 큰 특징입니다.


  컴퓨터가 수식을 계산하는 방법은 다음의 두 절차를 따르면 됩니다.


 ① 중위 표기법을 후위 표기법으로 변환하기


  중위 표기법을 후위 표기법으로 바꿀 때는 다음의 절차를 따르면 됩니다.


  1) 피연산자가 들어오면 바로 출력합니다.

  2) 연산자가 들어오면 자기보다 우선순위가 높거나 같은 것들을 빼고 자신을 스택에 담습니다.

  3) 여는 괄호 '('를 만나면 무조건 스택에 담습니다.

  4) 닫는 괄호 ')'를 만나면 '('를 만날 때까지 스택에서 출력합니다.


  한 번 중위 표기식 ( a + b - c ) * d * e을 위 공식에 따라서 후위 표기법으로 변환해봅시다.


  변환 결과: a b + c - d e * *


  숫자를 이용해 표현해봅시다. ( 5 + 6 - 7 ) * 1 * 5 이 경우도 다음과 같이 변환할 수 있습니다.


  변환 결과: 5 6 + 7 - 1 5 * *


  이러한 과정을 의사코드로 표현하면 다음과 같습니다.


------------------------------------------------------------------------------------------------


void translation(exp) {

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) print(token);

else if(token == ')') {

while(stack[top] != '(') print(pop());

pop();

}

else {

while(getPriority(stack[top]) >= token) print(pop());

push(token);

}

}

while((token = getChar(exp)) != NULL) print(token);

}


------------------------------------------------------------------------------------------------

 ② 후위 표기법을 계산하기


  후위 표기법을 계산할 때는 다음의 절차를 따르면 됩니다.


  1) 피연산자를 만나면 스택에 담습니다.

  2) 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤에 그 결과를 스택에 담습니다.

  3) 연산을 마치고 스택에 남아있는 하나의 피연산자가 연산 수행 결과입니다.


  후위 표기식: 5 6 + 7 - 1 5 * *

  계산 결과: 20


  이러한 과정을 의사코드로 표현하면 다음과 같습니다.


------------------------------------------------------------------------------------------------


void calculate(exp) {

int x, y, z;

while((token = getChar(exp)) != NULL) {

if(token == 피연산자) push(token);

else if(token == 연산자) {

x = pop();

y = pop();

z = y 연산자 x;

push(z); 

}

}

print(pop());

}


------------------------------------------------------------------------------------------------


728x90
반응형

728x90
반응형

 선형 구조와 수식 계산


  자료구조에서 선형 구조(Linear Structure)는 말 그대로 데이터를 선형적으로 표현하는 자료구조를 의미합니다. 선형구조에는 배열(Array), 스택(Stack), 큐(Queue), 연결 리스트(Linked List) 등이 포함됩니다. 스택은 일반적으로 수식 계산에 가장 많이 사용됩니다. 공무원 시험이나 대학원 시험 등 어떠한 시험을 치를 때에도 스택과 관련한 문제가 굉장히 많이 출제되므로 모든 선형 구조 중에서 스택은 꼭, 반드시 알고 있어야 합니다. 또한 추가적으로 스택과 큐가 함께 사용되는 구조를 데큐(Deque)라고 합니다.


  일반적으로 소프트웨어에서 수식을 계산할 때는 스택(Stack)을 사용합니다. 이는 컴퓨터의 내부적인 처리 방식과도 연관이 깊습니다. 스택에 대한 자세한 설명은 네이버 블로그 https://blog.naver.com/ndb796/221230937978에서 제가 이전에 정리한 바가 있습니다.


 표기 방식의 세 가지 종류


 ▶ 위 표기(Prefix)


  전위 표기란 연산자를 피연산자 앞에 표기하는 방법입니다.


  EX) * - + a b c * c a


  중위 표기(Infix)


  중위 표기란 연산자를 피연산자의 가운데에 표기하는 방법입니다. 일반적으로 대수학에서 사용되는 표기법입니다.


  EX) ( a + b - c ) * d * e


 ▶ 후위 표기(Postfix)


  후위 표기란 연산자를 피연산자의 뒤에 표기하는 방법입니다. 컴퓨터가 처리하기에 가장 적합한 표기법입니다.


  EX) a b + c - d e * *


  위 세 가지 표기법에서 예시로 든 수식은 사실 모두 동일한 수식입니다. 이를 가장 먼저 전위 표기법을 이진 트리로 표현함으로써 증명해보겠습니다. * - + a b c * c a는 다음과 같이 연산 우선순위를 설정할 수 있습니다.



  이제 이걸 토대로 바로 다음과 같이 이진 트리로 표현할 수 있습니다.



  이진 트리로 표현한 뒤부터는 전위 표기, 중위 표기, 후위 표기로 나타내는 것은 매우 쉽습니다. 전위 표기법으로 표현할 때는 바로 부모 노드를 출력하고, 왼쪽 노드 및 오른쪽 노드에 방문하면 됩니다. 중위 표기법으로 표현할 때는 왼쪽 노드, 부모 노드, 오른쪽 노드로 방문하면 됩니다. 마지막으로 후위 표기법은 왼쪽 노드, 오른쪽 노드, 부모 노드를 차례대로 방문하면 됩니다.


  또한 재미있는 점은 중위 표기법을 제외하고 전위 표기법 및 후위 표기법에서는 괄호가 들어가지 않습니다. 괄호 없이 처리할 수 있다는 점에서 컴퓨터가 처리하기에 있어서는 가장 편리하고 간단한 표기 방식이라고 할 수 있습니다.


 ▶ 중위 표기 및 후위 표기 변환기: https://www.mathblog.dk/tools/infix-postfix-converter/


  또한 이 사이트에서는 중위 표기와 후위 표기를 마음대로 변환할 수 있도록 해줍니다. 상당히 유용해요.






728x90
반응형