[ 자료구조 ] 5. 연결리스트를 이용한 스택(Stack)
스택(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;
}
----------------------------------------------------------------
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 4. 이중 연결 리스트(Double Linked List) (0) | 2018.06.04 |
---|---|
[ 자료구조 ] 3. 연결 리스트(Linked List) (0) | 2018.06.04 |
[ 자료구조 ] 2. 중위 표기법을 후위 표기법으로 변환하여 계산하기 (5) | 2018.06.04 |
[ 자료구조 ] 1. 선형 구조와 수식 계산 (0) | 2018.06.04 |
[ 자료구조 ] 4. 이중 연결 리스트(Double Linked List)
이번 시간에는 이중 연결 리스트(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;
}
------------------------------------------------------------
실행 결과는 다음과 같습니다.
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 5. 연결리스트를 이용한 스택(Stack) (0) | 2018.06.05 |
---|---|
[ 자료구조 ] 3. 연결 리스트(Linked List) (0) | 2018.06.04 |
[ 자료구조 ] 2. 중위 표기법을 후위 표기법으로 변환하여 계산하기 (5) | 2018.06.04 |
[ 자료구조 ] 1. 선형 구조와 수식 계산 (0) | 2018.06.04 |
[ 자료구조 ] 3. 연결 리스트(Linked List)
연결 리스트(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;
}
}
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 5. 연결리스트를 이용한 스택(Stack) (0) | 2018.06.05 |
---|---|
[ 자료구조 ] 4. 이중 연결 리스트(Double Linked List) (0) | 2018.06.04 |
[ 자료구조 ] 2. 중위 표기법을 후위 표기법으로 변환하여 계산하기 (5) | 2018.06.04 |
[ 자료구조 ] 1. 선형 구조와 수식 계산 (0) | 2018.06.04 |