반응형
728x90
반응형

C++은 다른 언어들처럼 가비지 컬렉터가 없다ㅋㅋ 그래서 메모리 관리를 제대로 하지 않으면, 정확히 Heap 영역에 대한 메모리 관리가 제대로 되지 않는다면,

헬이다. 헬.

그러면 어찌해야하는가? RAII 라는 디자인 패턴이 있다.

Resource Acquisition Is Initialization 

위를 줄여서 RAII 라고 부른다.

RAII의 유래

그럼 왜 RAII일까? 유래를 좀 찾아봤는데 자원의 획득은 초기화이고, 반대로 자원의 반환은 객체 소멸 뭐 이런 식으로 확장하여 나타내는 어떤 관용구 같은 느낌의 디자인 패턴 개념이다.

RAII란?

좀 더 자세하게 관련해서 정의를 알아 보자면 RAII 는 객체의 생명주기에 관련된 내용으로, C++에서 객체가 생성되고 사용된 Scope를 벗어나면 객체의 자원을 해제해주는 방법을 이야기한다.

즉, 힙에 동적 할당되는 객체라고 해도, 프로그램 실행 흐름이 해당 객체의 유효 scope를 벗어나면 객체를 메모리 해체하도록 하는 것이 RAII라고 생각하면 될 것 같다.

근데 아쉽게도 힙 영역에 할당된 객체는 지역 scope를 벗어난다고해서 동적할당된 부분이 해체되지 않는다. 왜냐하면 동적할당이 이루어지는 해당 scope 내에는 객체 포인터가 스택에 쌓이고, 해당 scope가 끝나면 그 객체 포인터만 스택에서 소멸된다. 동적할당된 메모리는 힙 영역에 그대로 남아있다.

다음과 같이 말이다.

번호순으로 읽기

위의 사실을 응용하여,

어떤 scope에서 동적 할당이 이루어졌다면, 해당 scope에서 스택 영역에 할당되는 요소에게 동적 할당한 주소를 넘겨주고, 그 스택 영역에 할당된 요소는 스택에서 제거될 때, 넘겨받은 동적 할당된 주소를 함께 delete 하면서 제거되면 되지 않을까? 라는 발상이 떠오른다. 아래와 같이 말이다.

번호순으로 읽기

문제가 되는 부분

자, 일단은 문제가 되는 코드이다. 위의 그림과는 살짝 다르지만 문제 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
 
class R
{
    private:
        int *data;
    public:
        R(int len)
        {
            this->data = new int[len];
            std::printf("R() call! : new int[%d]\n",len);
        }
        ~R()
        {
            delete []this->data;
            std::printf("~R() call! : delete [] \n");
        }
};
 
void function(void)
{
    R * r = new R(1000);
 
    std::printf("function() 함수 종료\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs

위의 코드에서 function 함수라는 지역 scope 내에서 객체 R을 동적할당하고, function 함수를 그냥 종료하는 모습이다. 동적 할당된 R 은 소멸되지 않고 그대로 남다가 해당 프로세스가 종료될 때, 비로소 운영체제에 의해서 메모리 자원이 회수된다. 이런 회수를 원한게 아닌데 말이다.

그렇다면 실행 결과를 보자.

분명히, 소멸자가 호출되지 않은 모습이다. 이것이 바로 메모리 누수(Leak)

스마트 포인터

이를 해결할 방법으로 스마트 포인터라는 것이 등장한다. 포인터 역할을 하는 객체로 이 스마트 포인터를 스택 객체로 할당하고 동적 할당 주소를 넘겨주면 스마트 포인터 객체가 소멸될 때 동적 할당된 힙까지 알아서 똑똑하게 삭제를 해주기 때문이다.

이러한 스마트 포인터를 직접 구현해보았다. 다른 이미 구현된 스마트 포인터만큼 스마트하지는 못해서 그냥 오토 포인터라고 이름을 지었다ㅋㅋㅋ

뭐 아래의 연산자 오버로딩 포스팅 때, 구현을 이미 해봤지만 그래도 새롭게 참고하면서 구현해보았다.

 

21 연산자 오버로딩

연산자 오버로딩 연산자 오버로딩 C++언어에서는 연산자의 오버로딩을 통해서 기존에 존재하던 연산자의 기본 기능 이외에 다른 기능을 추가할 수 있다. 먼저 15번 라인을 통해서 operator+ 라는 함

typingdog.tistory.com

코드 및 실행결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
 
class R
{
private:
    int* data;
    int len;
public:
    R(int _len)
    {
        this->len = _len;
        this->data = new int[_len];
        for (int i = 0; i < _len; i++)
            this->data[i] = i * 100000;
        std::printf("R() call! : new int[%d]\n", _len);
    }
    ~R()
    {
        delete[]this->data;
        std::printf("~R() call! : delete [] \n");
    }
    void ShowData(voidconst
    {
        for (int i = 0; i < this->len; i++)
            std::printf("%d, "this->data[i]);
        std::cout << std::endl;
        return;
    }
};
 
template <typename T>
class AutoPointer
{
private:
     const T* ptr;
public:
    AutoPointer(T* _ptr) : ptr(_ptr)
    {
    }
    ~AutoPointer()
    {
        delete this->ptr;
    }
    const T& operator* () const
    {
        return *(this->ptr);
    }
    const T* operator-> () const
    {
        return this->ptr;
    }
};
 
void function(void)
{
    AutoPointer<R> r(new R(10));
    r->ShowData();
    std::printf("function() 함수 종료!\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs
힙 영역의 객체의 소멸까지 책임지는 스마트 포인터 똑똑해^^7

이렇게 힘들게 만들었는데 이미 C++ 11에서는 다음과 같은 문법을 제공한다.

 

unique_ptr<> : #include <memory>

이미 11 문법에서는 겁나 스마트한 포인터 객체로 제공을 해주었던 것이다... 사용 방법은 내가 만든 오토 포인터와 같으니 바로 예제로 들어가보겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <memory>
 
class R
{
    private:
        int *data;
    public:
        R(int len)
        {
            this->data = new int[len];
            std::printf("R() call! : new int[%d]\n",len);
        }
        ~R()
        {
            delete []this->data;
            std::printf("~R() call! : delete [] \n");
        }
};
 
void function(void)
{
    std::unique_ptr<R> r(new R(1000));//R * r = new R(1000);
    std::printf("function() 함수 종료\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs

불안정한 메모리 관리를 이러한 패턴으로 처리한다는게 정말 잔머리를? 기가막히게 잘 굴린듯한 느낌이다. 그래도 GC(가비지 컬렉터)가 제공되면 참 좋겠지만 이렇게라도 일부라도 관리를 틈틈이 하는게 좋은 것 같다.

다음 번 포스팅에서는 (공부하다가 필요한 부분부분 정리하는 포스팅이기 때문에 시리즈물처럼 바로 다음 번은 아니지만) 이 unique_ptr 외에 공유 가능한, 그리고 인자로의 전달 시 어떤 형태로 코드를 짜야하는 지 등에 대해서 올려볼 것이다.

728x90
반응형
728x90
반응형

그노므 DFS! DFS! 드디어 깔끔하게 정리를 한다. 이 탐색 기법 하나에 워낙 들어가는 내용이 많기 때문에 바로바로 정리하지 않으면 다시 처음부터 공부하는 수준으로 공부를 해야한다 흑흑...

이전의 포스팅의 내용을 기반으로 작성되기 때문에 이전 부분을 포스팅을 참고하라고 올려놓겠다.

 

C Data Structure - 그래프의 기본

드디어 그래프의 기본 코드이다. 이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법

typingdog.tistory.com

 

 

C Data Structure - 땡땡 우선 탐색(Depth or Breadth First Search Graph)

C Data Structure - 그래프란? 드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의

typingdog.tistory.com

 

중요 핵심

일단은 깊이 우선 탐색은 아래 세 가지가 핵심이다.

1. 깊이 접근하는 것
2. 왔던 경로를 되돌아오는 것
3. 정점 방문 여부를 기록하는 것

이 세 가지를 핵심으로 기록하겠다. 사용되는 예시는 간단하게 다음과 같다.

첫 번째, 깊이 접근한다는 것은 한 정점에서 연결되어 있는 정점 중 하나의 정점을 선택해서 파고 들어가고 또 그 정점에서 연결된 정점 중 하나의 정점을 파고 들어가는 식의 방법을 이야기 한다.

하나의 길만 만들어서 간다는 것이다.

1로 갈지, 2로 갈지는 중요하지 않다. 0이라는 정점에 연결 되어 있는 정점이 1 먼저 연결되있는지, 2 먼저 연결 되어있는지에 따라 다르다. 즉, 정점의 연결 정보를 나타내는 연결 리스트의 정렬 구조에 따라서 1 노드와 2 노드 중 어떤 것을 선택하게 될지 결정된다는 소리이다. 어찌됐건 우리는 순회 하는 것이 목적이므로 어딜 먼저 방문하는지는 의미가 없다.

두 번째, 왔던 경로를 되돌아오는 것되돌아오면서 놓친 정점을 순회해야하는 것이다. 이 때 경로를 다시 되돌아오려면 경로를 일단 기록을 해야하는데 역행이므로 스택의 형식대로 기록하면 된다. -> 방문 추적을 목적으로 스택을 사용한다.

세 번째, 정점 방문 여부를 기록한다는 것은 일반 순차 배열을 이용하여 기록한다. 다음 그림에 설명을 포함시키겠다.

 

주요 3가지 핵심에 대해서 살펴보았고 이번엔 그 순서대로 그려볼 것이다...

순회 프로세스

시작 정점 0을 방문된 상태로 시작한다. -> 방문 Flag 배열에서 정점 0을 True 처리.

연결된 인접 정점은 1 정점과 2 정점인데 방문 Flag 배열을 봐도 방문 처리가 False이기 때문에 두 정점 모두 접근이 가능하다. 이 예에서는 2 정점을 방문하겠지만 1 정점으로 방문해도 순회 순서만 다를 뿐 다른 의미는 없다.

2 정점을 방문하면서 방문 Flag 배열에서 2 정점을 True(방문) 처리하고, 떠나온 0 정점은 다시 돌아가기 위한 발자국으로 남기기 위해서 스택에 넣는다.

위와 마찬가지 과정을 통해 2 정점을 떠나면서 스택에 2 정점을 넣고, 3 정점을 방문한 뒤 방문 Flag 배열의 3 정점에 대한 방문 여부를 True로 변경한다.

또 마찬가지로 같은 과정을 반복하는데 3 정점에서는 1 정점과 4 정점에 접근 가능하다 어디로 가든 상관없지만 이번 예에서는 4 정점에 방문할 것이다.

4 정점에서는 인접한 정점이 모두 방문 처리 되었으므로 이제 스택에서 값을 POP 함으로써 되돌아 가면서 그냥 지나친 정점을 탐색한다.

3 정점으로 돌아왔을 때, 보니까 1 정점을 방문하지 않고 그냥 지나쳤었기 때문에 1 정점에 방문한다. 이 때, 1 정점에 방문하기 위해서 3 정점을 떠나는 것이니 1 정점 방문 이후 다시 돌아오기 위해 3 정점을 다시 스택에 넣는다. 그리고 1 정점에 대한 방문 처리를 진행한다.

그리고 1 정점에서 인접 정점 모두 방문 처리 되었으니 Pop을 통해 돌아가고, 3 정점에서도, 2 정점에서도 마찬가지로 인접 정점 모두 방문처리 되었으므로 Pop을 통해 돌아가다가 0 시작 정점까지 Pop하여 스택이 빈 경우 비로소 모든 순회가 끝난 것이다.

0 -> 2 -> 3 -> 4 -> 1 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

스택이 새롭게 사용되므로 스택에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 스택 코드를 활용할 것이다. 스택 설명 기록은 아래의 링크에서 확인하면 된다.

 

C Data Structure - 스택

스택이란 정말 간단하다. 분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다. 먼저, 스택이란 무엇

typingdog.tistory.com

먼저 바뀌는 부분과 추가되는 부분이다.

그래프 내의 방문 Flag 배열이 추가 된다.

방문 처리를 수행하는 함수가 추가된다.

깊이 우선 탐색을 수행하는 함수이다.

한 함수이지만 라인 수를 맞춰서 읽으면 된다... 이전 자료구조인 스택에 대한 사용 방법 또한 익혀야 하고 너무나도 추상적이라서 용어 설명이 너무 어려운 것 같다..ㅠ.ㅠ

그래프 종료 및 메모리 공간 해체 관련 코드이다.

 

전체 코드 및 실행 결과

전체 코드는 배열 기반의 스택변형된 연결리스트(오름차순으로 노드를 삽입; 이전에는 그냥 삽입했다.), DFS로 인해 변경된 그래프 코드 순으로 업로드 한다.

배열 기반의 스택 ArrayBasedStack.h -- -- -- -- --

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
    게시 완료
*/
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1// 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        //printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    //printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        //printf("스택이 이미 비어져 있습니다.\n");
        return -1// 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        //printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
cs

변형된 연결 리스트 linkedlistforgraph.h -- -- -- -- --

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
#pragma once
 
#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
    int data;
    struct ListNode* link;
};
 
struct ListManager
{
    struct ListNode* head;
    struct ListNode* ci; // current index; 
    struct ListNode* pi; // previous index;
    int (*comp)(int d1, int d2);
 
    int node_count; // data 값이 유효한 node의 수
    int malloc_count; // 할당된 수
};
 
void ListInit(struct ListManager* lm);
void LInsertNoSort(struct ListManager* lm, int data);
void FInsert(struct ListManager* lm, int data);
void SInsert(struct ListManager* lm, int data);
void LInsert(struct ListManager* lm, int data);
int LFirst(struct ListManager* lm, int* data);
int LNext(struct ListManager* lm, int* data);
int LCount(struct ListManager* lm);
int LRemove(struct ListManager* lm);
int WhoIsPrecede(int d1, int d2);
void SetSortRule(struct ListManager* lm, int (*comp)(int d1, int d2));
 
void* CreateNodeMemory(struct ListManager* lm, int len);
void ShowList(struct ListManager* lm);
void DeleteNode(struct ListManager* lm, struct ListNode* target);
void DeleteList(struct ListManager* lm);
 
 
 
void ListInit(struct ListManager* lm)
{
    // count 초기화
    lm->node_count = 0;
    lm->malloc_count = 0;
 
    // head 다음으로 항상 유지하는 빈 노드 생성
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    new_node->data = -1;
    new_node->link = NULL// 제일 끝이므로 무조건 NULL을 갖는다.
 
    // 연결리스트 헤드 초기화
    lm->head = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    lm->head->data = -1;
    lm->head->link = new_node;
 
    // 인덱스 초기화
    lm->ci = NULL;
    lm->pi = NULL;
 
    SetSortRule(lm, WhoIsPrecede);
    //lm->comp = NULL;
 
    return;
}
 
void LInsertNoSort(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
void FInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
void SInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    struct ListNode* pred = lm->head->link;
 
    new_node->data = data;
 
    while (pred->link != NULL && lm->comp(data, pred->link->data) != 0
        pred = pred->link;
    // predecessor이 마지막 노드이면 그냥 거기다가 추가하면 되기 때문에 마지막 노드까지 가지 아니한다.
 
    new_node->link = pred->link;
    pred->link = new_node;
 
    (lm->node_count)++;
    return;
}
 
 
void LInsert(struct ListManager* lm, int data)
{
    if (lm->comp == NULL)
    {
        printf("FInsert();\n");
        FInsert(lm, data);
    }
    else
    {
        printf("SInsert();\n");
        SInsert(lm, data);
    }
    return;
}
 
int LFirst(struct ListManager* lm, int* data)
{
    if (lm->node_count == 0)
    {
        printf("순회할 노드가 없습니다.\n");
        return false;
    }
    lm->ci = lm->head->link->link;
    lm->pi = lm->head->link;
 
    *data = lm->ci->data;
    return true;
}
 
int LNext(struct ListManager* lm, int* data)
{
    if (lm->ci->link == NULL)
        return false;
 
    lm->pi = lm->ci;
    lm->ci = lm->ci->link;
    *data = lm->ci->data;
    return true;
}
 
int LCount(struct ListManager* lm)
{
    return lm->node_count;
}
 
int LRemove(struct ListManager* lm)
{
    int remove_value = lm->ci->data;
    struct ListNode* rtarget = lm->ci;
 
    lm->pi->link = rtarget->link;
    lm->ci = lm->pi;
 
    DeleteNode(lm, rtarget);
    return remove_value;
}
 
int WhoIsPrecede(int d1, int d2)
{
    if (d1 < d2)
        return 0;    // d1이 정렬 순서상 앞선다.
    else
        return 1;    // d2가 정렬 순서상 앞서거나 같다.
}
 
void SetSortRule(struct ListManager* lm, int (*comp)(int d1, int d2))
{
    lm->comp = comp;
    return;
}
 
void* CreateNodeMemory(struct ListManager* lm, int len)
{
    lm->malloc_count++;
    return (void*)malloc(len);
}
 
void ShowList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
 
    if (lm->malloc_count == 0)
    {
        printf("head와 new node 및 일반 node들까지 모두 존재하지 않습니다.");
        return;
    }
    else if (lm->node_count == 0)
        printf("추가된 노드는 모두 제거된 상태이지만, head와 new node가 존재하고 추가 가능한 상태입니다.\n");
 
    for (index_node = lm->head; index_node != NULL; index_node = index_node->link)
    {
        printf("[%d|%p]", index_node->data, index_node);
        if (index_node->link != NULL)
            printf("->");
    }
    fputc('\n', stdout);
    return;
}
 
void DeleteNode(struct ListManager* lm, struct ListNode* target)
{
    if (target->data != -1)
        lm->node_count--;
 
    free(target);
    lm->malloc_count--;
 
    return;
}
 
void DeleteList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
    struct ListNode* next_node = NULL;
    for (index_node = lm->head; index_node != NULL; index_node = next_node)
    {
        next_node = index_node->link;
        DeleteNode(lm, index_node);
    }
    if (lm->malloc_count != 0)
        printf("메모리 해체에 문제가 있습니다\n");
    return;
}
 
 
cs

DFS로 인해 변경된 그래프 코드 DepthFirstSearchGraph.cpp -- -- -- -- --

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#include <memory.h>
#include "NonPublishing/Graph/linkedlistforgraph.h"
#include "NonPublishing/Graph/ArrayBasedStack.h"
 
#define TRUE 1
#define FALSE 0
 
struct DefaultGraph
{
    int vertex_number; // 정점의 수
    int edge_number; // 간선의 수
    struct ListManager* lm; // 정점 별 이어져 있는 간선들 관리.
    int* visit_flag_array; // 정점에 방문했는지 안했는지 여부를 저장.
};
typedef struct DefaultGraph dgraph;
 
void GraphInit(dgraph* graph, int vertex_number);
void AddEdge(dgraph* graph, int from, int to);
void ShowGraphEdgeInfo(dgraph* graph);
void DestroyGraph(dgraph* graph);
int VisitVertex(dgraph* graph, int vertex);
void ShowDFSVertexes(dgraph* graph, int start_vertex);
 
int main(void)
{
    dgraph graph;
    GraphInit(&graph, 7);
 
    //0 1 2 3 4
    AddEdge(&graph, 01);
    AddEdge(&graph, 03);
    AddEdge(&graph, 12);
    AddEdge(&graph, 32);
    AddEdge(&graph, 34);
    AddEdge(&graph, 45);
    AddEdge(&graph, 46);
 
    ShowGraphEdgeInfo(&graph);
 
    ShowDFSVertexes(&graph, 0); fputc('\n', stdout);
    ShowDFSVertexes(&graph, 2); fputc('\n', stdout);
    ShowDFSVertexes(&graph, 4); fputc('\n', stdout);
    ShowDFSVertexes(&graph, 6); fputc('\n', stdout);
 
    DestroyGraph(&graph);
 
    return 0;
}
 
void GraphInit(dgraph* graph, int vertex_number)
{
    int i = 0;
    graph->vertex_number = vertex_number;
    graph->edge_number = 0;
    graph->lm = (ListManager*)malloc(sizeof(ListManager) * vertex_number);
    graph->visit_flag_array = (int*)malloc(sizeof(int* vertex_number); // 정점의 수만큼을 크기로 한다.
 
    for (i = 0; i < vertex_number; i++)
        ListInit(&(graph->lm[i]));
 
    memset(graph->visit_flag_array, 0sizeof(int* vertex_number);
 
    return;
}
 
void AddEdge(dgraph* graph, int from, int to)
{
    if ((from >= graph->vertex_number) || (to >= graph->vertex_number))
    {
        printf("초과된 vertex 값이 왔습니다. \n");
        return;
    }
 
    if (from == to)
    {
        printf("잘못된 vertex 값이 왔습니다. \n");
        return;
    }
 
    LInsert(&(graph->lm[from]), to);
    LInsert(&(graph->lm[to]), from);
    graph->edge_number++;
 
    return;
}
 
int VisitVertex(dgraph* graph, int vertex)
{
    if (graph->visit_flag_array[vertex] == 0// 방문 가능한 상태인가?
    {
        graph->visit_flag_array[vertex] = 1// 방문 처리 했습니다.
        printf("정점 방문[%d], ", vertex);
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}
void ShowDFSVertexes(dgraph* graph, int start_vertex)
{
    stack history;
    int target_vertex = start_vertex;
    int next_vertex;
    int visit_flag = FALSE;
 
    StackInit(&history);
 
    // 시작 정점의 방문
    if (VisitVertex(graph, target_vertex))
        SPush(&history, target_vertex);
    else
        return;
 
    while (LFirst(&(graph->lm[target_vertex]), &next_vertex) == TRUE)
    {
        visit_flag = FALSE;
 
        if (VisitVertex(graph, next_vertex) == TRUE)
        {
            SPush(&history, target_vertex);
            target_vertex = next_vertex;
            visit_flag = TRUE;
        }
        else
        {
            while (LNext(&(graph->lm[target_vertex]), &next_vertex) == TRUE)
            {
                if (VisitVertex(graph, next_vertex) == TRUE)
                {
                    SPush(&history, target_vertex);
                    target_vertex = next_vertex;
                    visit_flag = TRUE;
                    break;
                }
            }
        }
 
        if (visit_flag == FALSE)
        {
            if (SIsEmpty(&history) == TRUE) 
                break;
            else
                target_vertex = SPop(&history);
        }
    }
    memset((void*)graph->visit_flag_array, 0sizeof(int* graph->vertex_number);
    return;
}
void ShowGraphEdgeInfo(dgraph* graph)
{
    int i = 0;
 
    for (i = 0; i < graph->vertex_number; i++)
    {
        printf("정점[%d] : ", i);
        ShowList(&(graph->lm[i]));
    }
    return;
}
 
void DestroyGraph(dgraph* graph)
{
    int i = 0;
 
    if (graph->lm == NULL)
        return;
 
    for (i = 0; i < graph->vertex_number; i++)
        DeleteList(&(graph->lm[i])); // 내부 연결된 노드를 모두 제거.
    free(graph->lm); // 정점들 자체를 제거.
    free(graph->visit_flag_array); // 정점 방문 여부를 제거. 
    return;
}
cs

 

728x90
반응형
728x90
반응형
 

C Data Structure - 그래프란?

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다. 그래프란? 먼

typingdog.tistory.com

 

 

C Data Structure - 그래프의 기본

드디어 그래프의 기본 코드이다. 이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법

typingdog.tistory.com

일단, 위의 그래프 기본들을 기반으로 작성되기 때문에.. 링크해둔다.

뭐 BFS니 DFS니 이상한 용어 써가면서 아는 척 오졌던 학과 동기들 보면 이제 이렇게 생각하라. 

대단한 친구들이네

근데 사실, 이상한 용어가 나와서 오히려 겁 먹고 어려울지 모르겠지만 조금만 이해하면 그렇게 어렵지 않다. 

BFS 나 DFS 모두 Search의 일종이다. 뭐 말로만 Search지 순회다 순회. 순회하면서 원하는 값이 나오면 조건문으로 캐치하면 그게 Search이지 무엇이겠는가?

아무튼 두 개념 모두 순회인데, 순회하는 방법이 다르다. 그래서 두 가지를 모두 동시에 기록해 두려고 한다.

DFS (Depth First Search)

DFS는 Depth First Search 로 깊이 우선 탐색이다. 말 그대로 우선적으로 그래프를 깊게 깊게 파고 들어간다는 것이다. 그렇게 전부 파고 들어 갔다면 다시 되돌아 나오면서 깊게 파면서 놓쳤던 주변을 살펴보며 나오는 형식이다.

위 그림과 같은 식인데, 윤성우 교수님의 자료구조 책에서는 다음과 같이 표현한다. "너니까 이야기해주는거야" 하면서 깊고 친한 관계라고 생각하는 친구들에게만 비밀 이야기를 전달한다. 그러다보니 3번과 같은 정점에게도 퍼져있는 비밀 이야기가 소문이 나는 상황에 비유를 하셨다ㅋㅋ

중요한 것은 돌아 나오는 것각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다.

첫째로 돌아 나온 다는 것은 그 발자취를 기록하면 된다. 기록할 때 그냥 순서대로 기록하고 기록한 순서대로 다시 보는게 아니라 돌아나가는 것은 역재생하는 것과 같으므로 스택 자료구조를 이용한다.

둘째로 정점들의 방문 여부는 인덱스 값과 정점 값을 매칭 시킨 flag 역할을 1차원 배열로 처리를 하면 된다.

참고>>

이런 경로 또한 가능하다. 구현해 보면 알겠지만 하나의 정점에 연결된 정점들 중 어떤 것을 선택하는지에 대한 로직은 순회 로직에 들어가지 않는다. 그러니까 시작 정점에서 왼쪽 정점으로 갈지, 오른쪽 정점으로 갈지를 중요시 하지 않는다는 소리이다. 이는 정점간 연결을 나타내는 자료구조 내에서 어떤 순서로 연결 정보를 저장했는지에 따라서 다르게 나온다. 그니까 어떤 경로든 해당 탐색의 기본 원리에만 들어 맞다면 경로 순서의 맞고 틀리고를 따지는건 의미가 없다는 소리이다.

BFS (Breadth First Search)

반면에 BFS는 Breadth First Search 로 너비 우선 탐색이다. 말 그대로 우선적으로 넓게 넓게 퍼뜨리며 그래프를 파고들겠다는 것이다. 그러니까 어떤 정점을 순회하기만 했다 하면 바로 그냥 그 해당 정점에 연결된 모든 정점에게 방문하는 것이다. 

이건 약간 예로 들자면, 정책 발표에 따른 메시지 퍼짐이다! 출발 지점에서 정책을 발표한다. 그 양 옆 정점은 그 해당 정책을 티비를 통해 실시간으로 들은 정점들이고, 그리고 나서 그 실시간으로 들은 정점들이 지인을 만날 때마다 그 정책에 대해서 이야기하는 모습 같다고 비유할 수 있다.

중요한 것은 방문/순회 차례에 대한 기록각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다. 

첫째로 물론 각 정점들의 방문 여부는 위에서와 마찬가지로 flag 역할의 1차원 배열로 충분하다. 

둘째로 방문/순회 차례에 대한 기록은 위 DFS와는 조금 다르다. 방문한 정점과 연결된 정점들을 모두 방문하고, 그 다음 순서까지 정한 뒤 넘어가야헌다 그것이 BFS에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 이다

이렇게 두 개념을 코드를 통해 구현해 볼 것이다 

728x90
반응형
728x90
반응형

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

 

삭제 연산

 

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

Front  노드  포인터가 NULL인지를 확인하면 된다.

메모리 관리

이번에는 연결 리스트 기반 스택으로 관리한다.

코드 및 실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <stdio.h>
#include <stdlib.h>
 
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
// 공통 노드 정의
struct node
{
    int data;
    struct node* next;
};
 
// 스택으로 메모리 관리.
struct array_stack
{
    struct node* stack_array[STACK_LEN];
    int top_index;
};
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
int SIsFull(stack* s); // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
void SPush(stack* s, struct node* data); // 증가시키고 대입.
struct node* SPop(stack* s);
struct node* SPeek(stack* s);
void ShowStack(stack* s);
 
struct node* CreateNodeAuto(stack* s);
void RemoveAllNodeAuto(stack* s);
 
// 리스트 기반 큐 자료구조(원형일 필요가 없음)
struct list_queue
{
    struct node* front;
    struct node* rear;
    int count;
};
typedef struct list_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, stack* s, int data);
void ShowQueue(queue* q);
 
// Main
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    printf("큐/스택 생성 시작 --- \n");
 
    Enqueue(&q, &s, 1); ShowQueue(&q);
    Enqueue(&q, &s, 2); ShowQueue(&q);
    Enqueue(&q, &s, 3); ShowQueue(&q);
    Enqueue(&q, &s, 4); ShowQueue(&q);
    Enqueue(&q, &s, 5); ShowQueue(&q);
 
    printf("큐 제거 시작 --- \n");
 
    ShowQueue(&q);
    while (!QisEmpty(&q))
    {
        Dequeue(&q);
        ShowQueue(&q);
    }
    fputc('\n', stdout);
 
    printf("스택 제거 시작 --- \n");
    RemoveAllNodeAuto(&s);
    return 0;
}
 
 
// 메모리 관리 스택 관련 함수
 
void StackInit(stack* s)
{
    int i = 0;
    s->top_index = -1;
    for (i = 0; i < STACK_LEN; i++// 순회를 위해서 모두 초기화
        s->stack_array[i] = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1)
        return TRUE;
    else
        return FALSE;
}
int SIsFull(stack* s) // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
{
    if ((s->top_index) + 1 < STACK_LEN)
        return FALSE;
    else
        return TRUE;
}
void SPush(stack* s, struct node* data) // 증가시키고 대입임 (top_index가 -1부터 시작하기 때문에)
{
    if (SIsFull(s))
    {
        printf("스택이 가득찼습니다\n");
        return;
    }
    s->stack_array[++(s->top_index)] = data;
    return;
}
struct node* SPop(stack* s)
{
    struct node* rtarget = NULL;
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    rtarget = s->stack_array[s->top_index];
    s->stack_array[s->top_index--= NULL;
    return rtarget;
}
struct node* SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    return s->stack_array[s->top_index];
}
 
void ShowStack(stack* s)
{
    int i = 0;
    printf("{(top:%d)} : ", s->top_index);
    for (i = 0; i < STACK_LEN; i++)
        printf("[%p]", s->stack_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
// 내가 정의하는 함수
 
struct node* CreateNodeAuto(stack* s)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL// tmp->next = s->head;
    // 메모리 스택에 추가
    SPush(s, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(stack* s)
{
    struct node* rtarget = NULL;
    ShowStack(s);
    while (!SIsEmpty(s))
    {
        rtarget = SPop(s);
        free(rtarget);
        ShowStack(s);
    }
    return;
}
 
// 큐 자료구조 관련 함수
 
void QueueInit(queue* q)
{
    q->front = q->rear = NULL;
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == NULL)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (QisEmpty(q))
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    // target 추출
    target = q->front;
 
    // front를 맨 앞 노드의 다음 노드로 변경
    q->front = q->front->next;
 
    // 카운트 감소
    q->count--;
    return target;
}
void Enqueue(queue* q, stack* s, int data)
{
    // 노드 생성
    struct node* new_node = CreateNodeAuto(s); // 추가되는 노드가 항상 마지막이 된다.
    new_node->data = data;
    new_node->next = NULL;
 
    ShowStack(s);
 
    if (QisEmpty(q)) // 노드가 처음 추가하는 노드라면 front와 rear 모두 갱신
    {
        q->front = q->rear = new_node;
    }
    else // 노드가 처음 추가하는 노드가 아니라면 rear만 갱신
    {
        q->rear->next = new_node;
        q->rear = new_node;
    }
 
    // 카운트 증가
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    struct node* index = NULL;
    printf("{(r:%p/f:%p)} : ", q->rear, q->front);
    for (index = q->front; index != NULL; index = index->next)
        printf("[%p(%d)]", index, index->data), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
 
 
 
 
 
 
cs

 

728x90
반응형
728x90
반응형

자 오늘도 학습했던 원형 양방향 연결 리스트를 정리할 때가 됐다. 이게 정리를 바로바로 안 하다보니 후, 코드를 다시 이해해야한다. 뭐 복습도 되고 참 좋다;;;

먼저 오늘 할 것은

원형 - 무한 순회가 가능한 -> 그래서 순회에 조건이 꼭 붙는,
양방향 - 노드의 양쪽 링크가 존재하는 -> 그래서 원형 순회 실현이 가능한
연결 리스트

를 포스팅 한다.

원형이라고 해서 개인적으로 위와 같은 형태로  생각하면 혼란만 가중할 것이라고 생각한다. 아래와 같이 말이다.

그래서 우리는 머릿속의 형태를 정해놓고 시작해보고자 한다.

이러한 형태 임을 꼭 기억하고 있어야 한다.

노드 삽입 연산

삽입 연산은 노드가 없을 때와 있을 때로 나눈다.

크 따로 부가 설명이 필요 없을 것 같다ㅋ 

노드 삭제 연산

삭제는 간단하다. 그림 하나로 표현 가능하다.

삭제의 기본이 되는 부분

 

그 이외에 순회 연산

순회 연산은 그냥 노드의 링크를 순방향/역방향으로 타는 인덱스 포인터를 만들어서 순회를 하면 된다. 다만, 원형 연결 리스트인 만큼 무한 반복에 빠질 수 있기 때문에 아래와 같은 조건을 넣어 무한 반복에서 탈출하도록 해야한다.

위 코드는 순방향 순회, 역방향 순회 모두 마찬가지로 해당되는 부분이다.

 

메모리 관리 부분

해당 코드에서 또한 메모리 관리 부분이 따로 있기 때문에 삭제 연산 시에도 바로 메모리를 제거 하지 않고 프로그램 종료 전에 한꺼번에 모두 free 시키도록 되어 있다.

클래스로 stack 컨테이너 어댑터로 아래와 같이 구현되어 있다.

코드 및 실행 결과

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include <iostream>
#include <stack>
#include <stdio.h>
 
using namespace std;
 
// 구조체 존
struct node {
    int data;
    struct node* prev;
    struct node* next;
};
 
struct list {
    struct node* head;
    struct node* ci; // current index
    int count;
};
 
// 클래스 존
class NodeMemoryManager // 이 클래스 자체에 템플릿을 때려버리면 여러 타입에 대해서 관리할 수 있다ㅋ
{
private:
    int count; // 내부적인 교차 검증을 위한 count;
    stack<struct node*> allocated_node_address;
public:
    NodeMemoryManager()
    {
        this->count = 0;
    }
    ~NodeMemoryManager()
    {
        int free_count = 0;
        int stack_count = this->allocated_node_address.size(); // 제거하기 전 숫자.
 
        // 스택은 내부적으로 벡터니까 -> 임의 접근이 되지 않을까? -> 불가능 -> 그럴거면 벡터를 쓰지 왜 스택을 쓰나? 스택의 탄생 이유이다.
        while (!this->allocated_node_address.empty())
        {
            free(this->allocated_node_address.top()); // c에서 malloc 할 것이니, free 함수.
            this->allocated_node_address.pop();
            free_count++;
        }
        cout << "모든 메모리가 해체되었습니다[" << free_count << "/" << this->count << "(" << stack_count << ")]" << endl;
    }
    struct node* CreateNodeAuto(void)
    {
        struct node* tmp = (struct node*)malloc(sizeof(struct node));
        // 초기화
        tmp->data = 0;
        tmp->prev = NULL;
        tmp->next = NULL;
        // 스택 추가
        this->AddAllocatedNodeAddress(tmp);
        return tmp;
    }
    void AddAllocatedNodeAddress(struct node* addr)
    {
        this->allocated_node_address.push(addr);
        this->count++;
        return;
    }
    int GetCount()
    {
        return this->count;
    }
    int GetCountByStack()
    {
        return this->allocated_node_address.size();
    }
};
 
// 재정의 존
typedef struct list List;
 
// 함수 선언 존
void ListInit(List* list);
void LInsert(List* list, int data);
int LFirst(List* list, int* data);
int LNext(List* list, int* data, int non_exit);
int LPrevious(List* list, int* data, int non_exit);
void LRemove(List* list);
 
// 전역 변수 존
NodeMemoryManager nmm;
 
//메인 함수
int main(void)
{
    List list;
    int data;
 
    ListInit(&list);
 
    // 값 1 ~ 값 8 까지 추가.
    LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5); LInsert(&list, 6); LInsert(&list, 7); LInsert(&list, 8);
 
    LFirst(&list, &data);
 
    // 한 칸 씩 이동
    printf("-------- previous zone \n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    printf("-------- next zone \n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    // 순회 및 삭제 처리
    printf("-------- remove zone \n\n");
    if (LFirst(&list, &data))
    {
        if (data == 2)
            LRemove(&list);
        while (LNext(&list, &data, 0))
        {
            if (data == 2)
                LRemove(&list);
        }
        while (LPrevious(&list, &data, 0))
        {
            if (data == 6)
                LRemove(&list);
        }
    }
 
    // 순회
    printf("-------- circuit zone \n");
    if (LFirst(&list, &data))
    {
        printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LNext(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LPrevious(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
    }
 
    printf("최종으로 남은 노드의 개수는? ( %d )\n", list.count);
 
    return 0;
}
 
// 함수 정의 존
void ListInit(List* list)
{
    // 헤더 생성 및 초기화
    list->head = NULL;
    // 카운트 초기화
    list->count = 0;
    // 인덱스 노드를 초기화
    list->ci = NULL;
 
    return;
}
 
void LInsert(List* list, int data)
{
    // 새 노드 생성
    struct node* new_node = nmm.CreateNodeAuto();
 
    // 새 노드 초기화
    new_node->data = data;
 
    if (list->head == NULL// 자료구조 자체가 비어있으면
    {
        new_node->prev = new_node->next = new_node;
    }
    else
    {
        // 새 노드의 양 링크를 연결.
        new_node->next = list->head; // 1. [새 노드] -> 기존 시작 노드 연결
        new_node->prev = list->head->prev; // 2. 기존 끝 노드 <- [새 노드] 연결
 
        // 양쪽 노드의 prev 링크들을 연결.
        new_node->next->prev = new_node; // 새 노드 <- [기존 시작 노드] 연결
        new_node->prev->next = new_node; // 새 노드 <- [기존 끝 노드] 연결
    }
 
    // 헤드와 빈 노드 연결
    list->head = new_node;
 
    // 노드 추가 완료 시, 카운트 증가
    list->count++;
 
    return;
}
 
int LFirst(List* list, int* data)
{
    // 헤드를 검사한다. 널이면 false 반환, 널이 아니면 진행
    if (list->head == NULL)
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->head;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LNext(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 다음 가리키는 것이 헤드가 가리키는 것과 같은지를 확인한다. -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    // 원형이기 때문에 검사가 필요한데, non_exit인자는 원점을 지나쳐 원형으로 계속해서 순회하기 위해서 넣음.
    if ((non_exit == false&& (list->head == list->ci->next))
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->ci->next;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LPrevious(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 해당 노드의 prev가 가리키는 것이 헤드가 가리키는 것과 같인지를 확인한다 -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    if ((non_exit == false&& (list->head == list->ci->prev))
        return false;
 
    // 인덱스를 역행으로 옮긴다.
    list->ci = list->ci->prev;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
void LRemove(List* list)
{
    // 타겟의 링크들이 끊기기 전에 따로 주소 값을 기록한다.
    struct node* target = list->ci;
 
    // 삭제할 타겟이 head가 가리키고 있는 노드라면
    if (list->head == target)
    {
        // 삭제할 타겟의 양 링크가 본인을 가리킨다면 삭제할 타겟은 하나!
        if (list->head == list->head->next) 
            list->head = NULL;
        else 
            list->head = target->next; // 헤드를 다음 노드로 옮겨준다.
    }
 
    // 타겟의 전 노드의 next 를 타겟의 next로 바꾼다
    target->prev->next = target->next;
 
    // 타겟의 다음 노드의 prev 를 타겟의 prev로 바꾼다
    target->next->prev = target->prev;
 
    // count를 줄인다.
    list->count--;
 
    // 메모리 해체는 NMM 객체가 알아서 해준다.
    return;
}
cs

728x90
반응형
728x90
반응형

스택을 연결리스트로 구현해 보았다.

일단 기본 구조에 대한 예시를 나타낸 것이다.

먼저, 왼쪽 구조를 보자. 우리 스택이라고 생각하는 구조이다. Head는 삽입 인덱스를 나타낸다. 소위 말하는 top 변수. 그 왼쪽의 구조를 단순화시켜서 보면 오른쪽처럼 나타낼 수 있다. 오른쪽 구조에서 Head 노드는 새롭게 노드가 삽입될 때 마다 가리키는 것을 갱신시키는데, 이 현상을 자세히 보면 왼쪽 구조에서 head가 옮겨다니는 것과 같다. 

다른 현상을 가지고 생각하기 나름으로 같은 본질을 끌어냈다 크.. 윤성우 교수님께 박수를...

암튼 왼쪽이든 오른쪽이든 위와 같은 본질의 구조를 구현할 것이다.

삽입 연산

1) 헤드와 기존 최 상단 노드의 연결을 끊고, 2) 새 노드와 최상단 노드를 연결하여 새 노드를 최상단 노드로 변경하고,  그 3) 최상단 노드를 헤드가 가리키도록 헤드 값을 갱신 

삭제 연산

삭제의 기본 동작은 노란색 글씨와 빨간색 글씨로 표현을 해두었다.

파란색 글씨는 대충 이런 말이다. 할당된 메모리는 따로 이전에 만들어 뒀던 자료구조로 따로 저장하여 관리하고 프로그램 종료 시, 일괄로 삭제하기 때문에 관련 포인터만 변경하고(모든 포인터 연결을 삭제 '처리') 삭제 되었다고 생각하고 진행하라는 의미이다. 

비어짐 확인

이런 구조에서 비어짐을 확인하려면 어떻게 하면 될까? 
> Head가 NULL을 가리키면 텅 빈 상태입니다. (O)
이런 구조에서 꽉 참을 확인하려면 어떻게 하면 될까?
> 연결 리스트 기반이라 꽉 찰 것을 걱정하지 않아도 됩니다.(O) 그 걱정대신 작성자 나이 걱정을.... (ㅜ.ㅜ)

뭐 더 쓸 말이 없다.

 

코드 및 실행 결과

프로그램 코드를 제출하기에 앞서 복습도 할 겸,
이전에 배웠던 원형 큐를 활용하여 메모리가 생성될 때마다 원형 큐에 메모리 주소를 넣고, 프로그램이 종료될 때 일괄적으로 free~~~~~~~ 된다. 그니까 생성만 했다하면 원형 큐에 넣어제끼고, 프로그램이 끝나기 직전에 다 소멸시켜버리는 것이다. 그래서 실행 결과가 지저분하여 실행결과도 약간의 설명을 넣을 예정이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <stdio.h>
#include <stdlib.h>
 
#define QUEUE_LEN 11
 
#define TRUE 1
#define FALSE 0
 
struct node
{
    int data;
    struct node* next;
};
 
struct list_stack
{
    struct node* head;
    int count;
};
typedef struct list_stack stack;
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
struct array_queue // 배열 기반 원형 큐 구현
{
    int front;
    int rear;
    int count;
    struct node* queue_array[QUEUE_LEN];
};
typedef struct array_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, struct node* data);
void ShowQueue(queue* q);
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
void RemoveAllNodeAuto(queue* q);
struct node* CreateNodeAuto(stack* s, queue* q);
 
// list stack 
void StackInit(stack* s);
int SIsEmpty(stack* s);
 
void SPush(stack* s, queue* q, int data);
int SPop(stack* s, queue* q);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    SPush(&s, &q, 1);
    SPush(&s, &q, 2);
    SPush(&s, &q, 3);
    SPush(&s, &q, 4);
    SPush(&s, &q, 5);
 
    while (!SIsEmpty(&s))
        printf("%d ", SPop(&s, &q));
    fputc('\n', stdout);
 
    ShowQueue(&q);
    printf("----------------------------------------------------------\n");
    RemoveAllNodeAuto(&q);
    return 0;
}
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = NULL// 큐 출력을 위한 초기화
 
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == q->rear)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    target = q->queue_array[q->front];
    q->queue_array[q->front= NULL;
    q->front = (q->front + 1) % QUEUE_LEN;
    return target;
}
void Enqueue(queue* q, struct node* data)
{
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    if ((q->rear + 1) % QUEUE_LEN == q->front// 가득 찬 경우,
    {
        printf("Queue가 가득 찼습니다.\n");
        return;
    }
    q->queue_array[q->rear] = data;
    q->rear = (q->rear + 1) % QUEUE_LEN;
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < QUEUE_LEN; i++)
        printf("[%2p]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
// 내가 정의하는 함수
struct node* CreateNodeAuto(stack* s, queue* q)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL// tmp->next = s->head;
    // 큐 추가
    Enqueue(q, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(queue* q)
{
    struct node* rtarget = NULL;
    while (!QisEmpty(q))
    {
        rtarget = Dequeue(q);
        printf("[%p/(%d)]가 제거되었습니다.\n", rtarget, q->count);
        ShowQueue(q);
 
        free(rtarget);
        q->count--;
    }
    return;
}
 
// list stack 
void StackInit(stack* s)
{
    s->count = 0;
    s->head = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(stack* s, queue* q, int data)
{
    // 추가해야할 새로운 노드 생성
    struct node* newnode = CreateNodeAuto(s, q);
    // 새로운 노드의 값 세팅 및 기존 노드로 next 연결
    newnode->data = data;
    newnode->next = s->head;
    // head를 새로운 노드와 연결
    s->head = newnode;
    // count 증가
    s->count++;
    return;
}
int SPop(stack* s, queue* q)
{
    struct node* target = s->head;
    // head 가 Null을 가리키고 있다면 스택이 비어있는 것. 조건 검사 진행
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    // head 를 target의 next, 다음 노드와 연결한다.
    s->head = target->next;
    // count 감소
    s->count--;
 
    return target->data;
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    return s->head->data;
}
 
cs

혹시 보는 사람이 있다면 스택 부분만 참고하면 될 듯 합니다. 앞으로도 쭉 요래요..ㅋㅋ

 

728x90
반응형
728x90
반응형

스택이란 정말 간단하다.

분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다.

먼저, 

스택이란 무엇인가?

우리는 스택을 이미 알고 있다. 스택은 프링글스이다. 아래의 그림을 보자.

우리는 세 개의 감자칩 중에서 어떤 감자칩이 제일 먼저 들어갔는지 알 수 있다. 바로 A이다. 어떻게 알았지? 출입구가 하나이고, 원통 내부의 크기는 서로가 뭐 어떻게 비집고 해서 바꿀 수 있는 사이즈가 아니다. 

A가 먼저 들어갔고 -> 그 다음 B가 그 위에 쌓이고 -> 그 후 C가 들어가면서 그 위에 쌓이는 것이다.

이렇듯 스택은 쌓이는 특징을 가지고 있다. 그렇다면 안의 감자칩을 꺼내먹을 때에는 어떻게 할까? 

가장 나중에 들어간 C가 제일 먼저 다시 나오고 -> 그 다음 B가 나오고 -> 가장 먼저 들어간 A가 제일 늦게 나온다. 

이렇게 나중에 들어간 값이 제일 먼저 나오는 구조를 후입선출 구조라고 한다.

단순 배열 기반 스택에서의 삽입

어려울 것이 전혀 없다. 그냥 값이 들어오는데로 쌓아올린다고 생각하고 인덱스를 증가시키면서 값을 추가하면 된다.

82를 삽입 전(왼) / 82를 삽입 후(오)

하나도 어렵지 않다. 이렇게 보면 그냥 배열 끝에 값을 추가하는 것 같다. 우리는 스택에 값을 추가하는 행위push 라고 할 것이다. 삭제 연산을 보자. 

단순 배열 기반 스택에서의 삭제

3 값이 튀어나가면서 삭제 처리가 되어 버리고, 삽입 인덱스가 하나 감소한다.

마지막 하나 남은 1이 튀어 나가며 값이 삭제 처리 되고, 삽입 인덱스가 갈 곳을 잃는데 이 때, 삽입 인덱스를 -1로 하자. 그러면 나중에 빈 스택 상태에서 값을 추가할 때, 삽입 인덱스를 증가시키면 [-1] 에서 [0]으로 바뀌어서 자연스럽게 값을 추가하면 될 뿐만 아니라, 스택이 비어있는지 비어있지 않는지 삽입 인덱스가 -1인지 아닌지를 보면 된다.

그리고 우리는 삭제하는 연산을 pop 한다고 할 것이다.

단순 배열 기반 스택에서의 비워짐과 꽉참을 확인

또한 간단하다.
인덱스가 비워져 있는지를 확인하기 위해선 아까 삭제 연산에의 약속대로 삽입 인덱스가 -1인지를 확인하면 된다. 
인덱스가 가득차 있는지를 확인하기 위해선 현재 삽입 인덱스가 배열의 길이랑 같은지를 확인하면 된다.

코드 및 실행 결과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    StackInit(&s);
 
    SPush(&s, 1);
    SPush(&s, 2);
    SPush(&s, 88);
    SPush(&s, 125);
    SPush(&s, 9912);
 
    while (!SIsEmpty(&s))
        printf("[%d] ", SPop(&s));
    fputs("\n", stdout);
 
    if (SIsEmpty(&s))
        printf("스택이 텅 비었습니다.\n");
    return 0;
}
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1// 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어져 있습니다.\n");
        return -1// 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
cs

728x90
반응형
728x90
반응형

오늘도 역시 공부해놨던 부분을 이제 포스팅하는 시간이다. 역시 미리미리 해야한다.

스택이란?

일단 그림이 먼저다.

A, B, C 순서로 사각형을 넣을 것이다.

이렇게 된다. 그렇다면 다시 뺀다면?

이 때, 담는 용기, 통! 이것이 스택 자료구조이다. 
먼저 들어간 사각형 A가 제일 늦게 나오는 구조인 것이다. 이러한 개념을 후입선출이라고 한다. 나중에 들어간 것이 먼저 나오는 구조!

이를 구현하면 아래와 같다.

코드 및 실행 결과

---

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    StackInit(&s);
 
    SPush(&s, 1);
    SPush(&s, 2);
    SPush(&s, 88);
    SPush(&s, 125);
    SPush(&s, 9912);
 
    while (!SIsEmpty(&s))
        printf("[%d] ", SPop(&s));
    fputs("\n", stdout);
 
    if (SIsEmpty(&s))
        printf("스택이 텅 비었습니다.\n");
    return 0;
}
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1// 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어져 있습니다.\n");
        return -1// 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
cs

---

중간 중간에 보완해야할 부분이 있지만 개념 부분에서는 충분하기 때문에 보완하지는 않았다.

728x90
반응형

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 큐  (0) 2021.01.08
C Data Structure - 퀵 정렬  (0) 2021.01.06
C Data Structure - 병합 정렬  (0) 2021.01.05
C Data Structure - 힙 정렬  (0) 2021.01.05
C Data Structure - 연결 리스트  (0) 2021.01.04

+ Recent posts