원형 큐입니다.


원형 큐를 이해하기 위해서는 %(나머지) 개념을 잘 이해하시면 됩니다.


empty : 큐가 비었음을 의미하는 함수입니다. front와 rear가 같다면 큐는 비어있는 것입니다.

full : (rear + 1) % MAX_SIZE == front라면 큐가 꽉차 있음을 의미합니다.


다른 부분은 일반 큐와 같습니다.


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
#include <stdio.h>
 
#define MAX_SIZE 100
 
typedef struct round_queue {
    int queue[MAX_SIZE];
    int front, rear;
    int size;
 
    round_queue() {
        size = 0;
        front = 0;
        rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    int push(int value) {
        if ((rear + 1) % MAX_SIZE == front) {
            return 0;
        }
        size++;
        rear = (rear + 1) % MAX_SIZE;
        queue[rear] = value;
    }
 
    int pop() {
        if (empty()) {
            return -1;
        }
        size--;
        front = (front + 1) % MAX_SIZE;
        return queue[front];
    }
}round_queue;
 
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
 
        round_queue rq;
 
        for (int i = 0; i < N; i++)
        {
            int value;
            scanf("%d", &value);
            rq.push(value);
        }
 
        printf("#%d\n", test_case);
        while(!rq.empty()) printf("%d ", rq.pop());
    
        printf("\n");
    }
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[1918] 후위표기식  (0) 2017.11.27
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13

C언어의 구조체를 이용해서 우선순위 큐를 만들었습니다.


구조체는 아래처럼 정의했습니다.

1
2
3
4
5
6
7
8
9
typedef struct priority_queue {
    int heap[MAX_SIZE];
    int size;
    priority_queue();
    void swap(int *a, int *b);
    int push(int value);
    int pop();
    int empty();
}
cs


데이터를 저장할 heap과

heap의 사이즈를 나타낼 변수

그리고 데이터 swap함수

우선순위큐 push, pop, empty


입니다.


최대 힙으로 구현했고, 최소 힙은 부등호만 바꿔주면 됩니다.

양수에 대해서만 작동하는 힙입니다. 이유는 pop할 때 size == 0이면 -1을 리턴하게 했기 때문입니다.


input)

2

10

10 49 38 17 56 92 8 1 13 55

13 

4 22 50 13 5 1 22 35 21 7 99 100 14


출력결과)

2

10

10 49 38 17 56 92 8 1 13 55

#1

92 56 55 49 38 17 13 10 8 1

13

4 22 50 13 5 1 22 35 21 7 99 100 14

#2

100 99 50 35 22 22 21 14 13 7 5 4 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
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
#include <stdio.h>
 
#define MAX_SIZE 100
 
typedef struct priority_queue {
    int heap[MAX_SIZE];
    int size;
 
    priority_queue() {
        size = 0;
    }
 
    void swap(int *a, int *b) {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
 
    int push(int value) {
        if (size + 1 > MAX_SIZE) {
            return 0;
        }
 
        heap[size] = value;
 
        int current = size;
        int parent = (size - 1) / 2;
 
        while (current > 0 && heap[current] > heap[parent]) {
            swap(&heap[current], &heap[parent]);
            current = parent;
            parent = (parent - 1) / 2;
        }
 
        size++;
 
        return 1;
    }
 
    int pop() {
        if (size <= 0) return -1;
 
        int ret = heap[0];
        size--;
 
        heap[0] = heap[size];
        int current = 0;
        int leftChild = current * 2 + 1;
        int rightChild = current * 2 + 2;
        int maxNode = current;
 
        while (leftChild < size) {
            if (heap[maxNode] < heap[leftChild]) {
                maxNode = leftChild;
            }
            if (rightChild < size && heap[maxNode] < heap[rightChild]) {
                maxNode = rightChild;
            }
 
            if (maxNode == current) {
                break;
            }
            else {
                swap(&heap[current], &heap[maxNode]);
                current = maxNode;
                leftChild = current * 2 + 1;
                rightChild = current * 2 + 2;
            }
        }
        
        return ret;
    }
 
    int empty() {
        if (size == 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}priority_queue;
 
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
 
        priority_queue pq;
 
        for (int i = 0; i < N; i++)
        {
            int value;
            scanf("%d", &value);
            pq.push(value);
        }
 
        printf("#%d\n", test_case);
        while(!pq.empty()) printf("%d ", pq.pop());
    
        printf("\n");
    }
 
    return 0;
}
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[1918] 후위표기식  (0) 2017.11.27
[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13

https://www.acmicpc.net/problem/2263


헉헉..

엄청 어렵네요!!..


pre, in, post 각각의 순회는 이해했지만,

완벽히 이해한 것은 아니였나봅니다.


이 문제는

in과 post를 이용하여 pre를 유추하는 문제입니다.


post와 in의 특징을 제대로 이해하고 있다면

O(N)의 시간으로 해결할 수 있습니다.


우선 post에 특징에 대해서 말씀드리겠습니다.


post는 Left - Right - Root 순으로 순회를 합니다.

그렇다면 우리가 받는 post input에서 가장 끝이 트리의 root라는 것을 알 수 있습니다.


예제를 예로 들면 1 3 2 로 들어오니 2가 root라는 것을 알 수 있죠.


두번째로 in의 특징입니다.

in은 Left - Root - Right 순으로 순회를 합니다.

여기서 중요한 점!은 바로 in의 input을 그대로 받는 것이 아닌 그의 위치를 저장하는 것입니다.


예제를 예로 들면

1 2 3 이라는 input이 들어오니, pos[1] = 0, pos[2] = 1, pos[3] = 2

이런 식으로 위치를 저장합니다.

그 이유는


in을 사용해서 우리는 left, right 서브트리와 root로 구분을 지을 수 있기 때문입니다.


post를 이용하여 root를 찾았고, root가 무엇인지 안다면 in에서 그 root를 기준으로 left와 right 서브트리로 나눌 수 있습니다.


이러한 과정을 분할하면서 계속 반복한다면 원래의 트리 모양을 유추할 수 있겠지요.


pre는 Root - Left - Right 이므로 위의 특징들을 이용하여 root를 찾아낸 후 출력하고 in의 root를 기준으로

left서브트리의 노드 수와 right 서브트리의 노드 수를 체크하여 post트리에 적용한 후 그 노드 수를 기준으로 나눠주면 됩니다.



코드입니다.

pos배열을 선언할 때 배열의 개수가 MAX_SIZE + 1인 이유는 input이 1~N까지 들어오기 때문입니다.(이것 떄문에 엄청 틀렸습니다.)


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int post[MAX_SIZE];
int pos[MAX_SIZE + 1];
 
void order(int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return;
 
    int root = post[pe];
    cout << root << ' ';
 
    order(is, pos[root] - 1, ps, ps + pos[root] - is - 1);
    order(pos[root] + 1, ie, ps + pos[root] - is, pe - 1);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0, in; i < n; i++) {
        cin >> in;
        pos[in] = i;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
 
    order(0, n - 1, 0, n - 1);
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
이중 연결 리스트  (0) 2017.04.22

https://www.acmicpc.net/problem/1029



처음에 dfs로 방문체크를 하면서 cost가 크거나 같으면 이동하는 식으로 해서 해결해보려고 했으나

65프로에서 시간초과가 뜨더군요.

제한시간이 2초인데

dfs로 하면 최악의 경우 15!의 시간이 걸리기 때문에 해결할 수 없었습니다.


그래서 dp를 이용해야 했는데..

방문한 곳의 상태가 필요했기 때문에 비트마스크를 사용했습니다.


제 dp의 정의는


dp[1 << 15][15][10] : 방문상태, 아티스트 번호, 비용으로 정의했습니다.


아래는 코드입니다.


f함수의 매개변수는 방문상태, 아티스트 번호, 코스트, 깊이 입니다.



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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 15
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int dp[1 << MAX_SIZE][MAX_SIZE][10]; //state, artistNumber, cost
int cost[MAX_SIZE][MAX_SIZE];
int n;
 
int f(int state, int artist, int c, int d) {
    int &ret = dp[state][artist][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int i = 0; i < n; i++) {
        if (state & (1 << i) || cost[artist][i] < c) continue;
        ret = max(ret, f(state | (1 << i), i, cost[artist][i], d + 1));
    }
    return ret;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &cost[i][j]);
        }
    }
 
    printf("%d", f(1, 0, 0, 1));
    
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20

노드 구조체

1
2
3
4
5
6
typedef struct _node
{
    int data;
    struct _node* left;
    struct _node* right;
} Node;
cs


리스트 구조체

1
2
3
4
5
6
typedef struct _list
{
    Node* head;
    Node* tail;
    int size;
} List;
cs


List* create_list() : 리스트 생성 및 초기화

1
2
3
4
5
6
7
8
9
List* create_list()
{
    List* new_list = (List*)malloc(sizeof(List));
    new_list->head = NULL;
    new_list->tail = NULL;
    new_list->size = 0;
 
    return new_list;
}
cs


bool list_empty(List* L) : 리스트가 비어있으면 1 아니면 0 리턴

1
2
3
4
5
bool list_empty(List* L)
{
    if(L->size) return 0;
    else return 1;
}
cs


Node* create_node(int data) : 노드 생성 및 초기화

1
2
3
4
5
6
7
8
9
Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
 
    return new_node;
}
cs


void push_back(List *L, int data) : 리스트 맨 뒤에 푸시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void push_back(List *L, int data)
{
    Node* new_node = create_node(data);
 
    if(list_empty(L))
    {
        L->head = new_node;
        L->tail = new_node;
    }
    else
    {
        L->tail->right = new_node;
        new_node->left = L->tail;
 
        L->tail = new_node;
    }
 
    L->size++;
}
 
cs


void push_front(List *L, int data) : 리스트 맨 앞에 푸시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void push_front(List *L, int data)
{
    Node* new_node = create_node(data);
 
    if(list_empty(L))
    {
        L->head = new_node;
        L->tail = new_node;
    }
    else
    {
        L->head->left = new_node;
        new_node->right = L->head;
 
        L->head = new_node;
    }
 
    L->size++;
}
 
cs


void node_insert(List* L, int idx, int data) : 해당 인덱스에 데이터 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void node_insert(List* L, int idx, int data)
{
    if(idx == 0) push_front(L, data);
    else if(idx >= L->size - 1) push_back(L, data);
    else
    {
        Node* new_node = create_node(data);
 
        Node* now = L->head;
        for(int i = 0; i < idx; i++) now = now->right;
 
        new_node->left = now->left;
        new_node->right = now;
        now->left = new_node;
        new_node->left->right = new_node;
        L->size++;
    }
 
}
cs


void pop_back(List* L) : 리스트 맨 뒤에 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void pop_back(List* L)
{
    if(!list_empty(L))
    {
        if(L->size == 1)
        {
            free(L->head);
            L->head = NULL;
            L->tail = NULL;
        }
        else
        {
            Node* prev = L->tail->left;
            free(L->tail);
            prev->right = NULL;
            L->tail = prev;
        }
        L->size--;
    }
}
cs


void pop_front(List* L) : 리스트 맨 앞에 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void pop_front(List* L)
{
    if(!list_empty(L))
    {
        if(L->size == 1)
        {
            free(L->head);
            L->head = NULL;
            L->tail = NULL;
        }
        else
        {
            Node* next = L->head->right;
            free(L->head);
            next->left = NULL;
            L->head = next;
        }
        L->size--;
    }
}
cs


void node_delete(List* L, int idx) : 입력된 인덱스의 노드 삭제(인덱스가 벗어나면 맨 앞 혹은 맨 뒤 삭제)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void node_delete(List* L, int idx)
{
    if(!list_empty(L))
    {
        if(idx >= L->size - 1) pop_back(L);
        else if(idx <= 0) pop_front(L);
        else
        {
            Node* now = L->head;
            for(int i = 0; i < idx; i++) now = now->right;
 
            now->left->right = now->right;
            now->right->left = now->left;
 
            free(now);
            L->size--;
        }
    }
}
cs


실행 환경 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
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
#include <cstdio>
#include <cstdlib>
 
typedef struct _node
{
    int data;
    struct _node* left;
    struct _node* right;
} Node;
 
typedef struct _list
{
    Node* head;
    Node* tail;
    int size;
} List;
 
List* create_list()
{
    List* new_list = (List*)malloc(sizeof(List));
    new_list->head = NULL;
    new_list->tail = NULL;
    new_list->size = 0;
 
    return new_list;
}
 
Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
 
    return new_node;
}
 
bool list_empty(List* L)
{
    if(L->size) return 0;
    else return 1;
}
 
void push_back(List *L, int data)
{
    Node* new_node = create_node(data);
 
    if(list_empty(L))
    {
        L->head = new_node;
        L->tail = new_node;
    }
    else
    {
        L->tail->right = new_node;
        new_node->left = L->tail;
 
        L->tail = new_node;
    }
 
    L->size++;
}
 
void push_front(List *L, int data)
{
    Node* new_node = create_node(data);
 
    if(list_empty(L))
    {
        L->head = new_node;
        L->tail = new_node;
    }
    else
    {
        L->head->left = new_node;
        new_node->right = L->head;
 
        L->head = new_node;
    }
 
    L->size++;
}
 
void list_print(List* L)
{
    Node* tmp = L->head;
 
    while(tmp)
    {
        printf("%d ", tmp->data);
        tmp = tmp->right;
    }
    puts("");
}
 
void pop_back(List* L)
{
    if(!list_empty(L))
    {
        if(L->size == 1)
        {
            free(L->head);
            L->head = NULL;
            L->tail = NULL;
        }
        else
        {
            Node* prev = L->tail->left;
            free(L->tail);
            prev->right = NULL;
            L->tail = prev;
        }
        L->size--;
    }
}
 
void pop_front(List* L)
{
    if(!list_empty(L))
    {
        if(L->size == 1)
        {
            free(L->head);
            L->head = NULL;
            L->tail = NULL;
        }
        else
        {
            Node* next = L->head->right;
            free(L->head);
            next->left = NULL;
            L->head = next;
        }
        L->size--;
    }
}
 
void node_delete(List* L, int idx)
{
    if(!list_empty(L))
    {
        if(idx >= L->size - 1) pop_back(L);
        else if(idx <= 0) pop_front(L);
        else
        {
            Node* now = L->head;
            for(int i = 0; i < idx; i++) now = now->right;
 
            now->left->right = now->right;
            now->right->left = now->left;
 
            free(now);
            L->size--;
        }
    }
}
 
void node_insert(List* L, int idx, int data)
{
    if(idx == 0) push_front(L, data);
    else if(idx >= L->size - 1) push_back(L, data);
    else
    {
        Node* new_node = create_node(data);
 
        Node* now = L->head;
        for(int i = 0; i < idx; i++) now = now->right;
 
        new_node->left = now->left;
        new_node->right = now;
        now->left = new_node;
        new_node->left->right = new_node;
        L->size++;
    }
 
}
 
int main()
{
    List* new_list = create_list();
 
    for(int i = 1; i < 10; i++)
    {
        push_back(new_list, i);
        list_print(new_list);
    }
    for(int i = -10; i < 0; i++)
    {
        push_front(new_list, i);
        list_print(new_list);
    }
    for(int i = 0; i < 20; i++)
    {
        pop_front(new_list);
        list_print(new_list);
    }
 
    for(int i = 1; i < 10; i++)
    {
        push_back(new_list, i);
        list_print(new_list);
    }
 
    for(int i = 0; i < 10; i++)
    {
        node_delete(new_list, i);
        list_print(new_list);
    }
 
    for(int i = 1; i < 10; i++)
    {
        push_back(new_list, i);
        list_print(new_list);
    }
 
    puts("");
    for(int i = 2; i < 5; i++){
        node_insert(new_list, i, -1 - i);
        list_print(new_list);
    }
    return 0;
}
 
 
cs


'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
단순 연결 리스트  (0) 2017.04.22

노드 구조체

1
2
3
4
5
typedef struct _node
{
    int data;
    struct _node* next;
} Node;
cs


리스트 구조체

1
2
3
4
5
typedef struct _list
{
    Node* head;
    int size;
} List;
cs


List* create_list() : 리스트를 만들고 주소를 리턴

1
2
3
4
5
6
7
8
List* create_list()
{
    List* new_list = (List*)malloc(sizeof(List));
    new_list->head = NULL;
    new_list->size = 0;
 
    return new_list;
}
cs


Node* create_node(int data) : 노드를 만들고 주소를 리턴

1
2
3
4
5
6
7
8
Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
 
    return new_node;
}
cs


bool list_empty(List* L) : 리스트의 size가 0이면 1을 리턴 아니면 0을 리턴

1
2
3
4
5
bool list_empty(List* L)
{
    if(L->size) return 0;
    else return 1;
}
cs


void push_back(List* L, int data) : 리스트의 맨 뒤에 데이터 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push_back(List* L, int data)
{
    Node* new_node = create_node(data);
    Node* tmp = L->head;
 
    if(list_empty(L)) L->head = new_node;
    else
    {
        while(tmp->next) tmp = tmp->next;
        tmp->next = new_node;
    }
 
    L->size++;
}
cs


void node_insert(List* L, int idx, int data) : idx가 범위를 리스트 사이즈보다 크거나 같으면 push_back호출 아니면 해당 idx에 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void node_insert(List* L, int idx, int data)
{
    if(idx >= L->size) push_back(L, data);
    else
    {
        Node* new_node = create_node(data);
 
        if(idx == 0)
        {
            new_node->next = L->head;
            L->head = new_node;
        }
        else
        {
            Node* tmp = L->head;
            for(int i = 0; i < idx - 1; i++) tmp = tmp->next;
 
            new_node->next = tmp->next;
            tmp->next = new_node;
        }
        L->size++;
    }
}
cs


void node_delete(List* L, int idx) : idx가 범위를 벗어나면 맨 뒤를 삭제 아니면 해당 idx 노드 삭제

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
void node_delete(List* L, int idx)
{
    if(!list_empty(L))
    {
        Node* tmp = L->head;
 
        if(idx == 0)
        {
            L->head = tmp->next;
            free(tmp);
        }
        else if(idx >= L->size - 1)
        {
            Node* before = NULL;
            while(tmp->next)
            {
                before = tmp;
                tmp = tmp->next;
            }
 
            free(tmp);
            if(before != NULL) before->next = NULL;
            else L->head = NULL;
        }
        else
        {
            Node* before = NULL;
            for(int i = 0; i < idx; i++)
            {
                before = tmp;
                tmp = tmp->next;
            }
 
            before->next = tmp->next;
            free(tmp);
        }
 
        L->size--;
    }
}
cs


void list_print(List* L) : 리스트 데이터 전부 출력

1
2
3
4
5
6
7
8
9
10
11
void list_print(List* L)
{
    Node *tmp = L->head;
 
    while(tmp)
    {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    puts("");
}
cs


아래는 풀 코드 및 예제입니다.

실행 환경 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
#include <cstdio>
#include <cstdlib>
 
typedef struct _node
{
    int data;
    struct _node* next;
} Node;
 
typedef struct _list
{
    Node* head;
    int size;
} List;
 
List* create_list()
{
    List* new_list = (List*)malloc(sizeof(List));
    new_list->head = NULL;
    new_list->size = 0;
 
    return new_list;
}
 
Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
 
    return new_node;
}
 
bool list_empty(List* L)
{
    if(L->size) return 0;
    else return 1;
}
 
void push_back(List* L, int data)
{
    Node* new_node = create_node(data);
    Node* tmp = L->head;
 
    if(list_empty(L)) L->head = new_node;
    else
    {
        while(tmp->next) tmp = tmp->next;
        tmp->next = new_node;
    }
 
    L->size++;
}
 
void node_insert(List* L, int idx, int data)
{
    if(idx >= L->size) push_back(L, data);
    else
    {
        Node* new_node = create_node(data);
 
        if(idx == 0)
        {
            new_node->next = L->head;
            L->head = new_node;
        }
        else
        {
            Node* tmp = L->head;
            for(int i = 0; i < idx - 1; i++) tmp = tmp->next;
 
            new_node->next = tmp->next;
            tmp->next = new_node;
        }
        L->size++;
    }
}
 
void node_delete(List* L, int idx)
{
    if(!list_empty(L))
    {
        Node* tmp = L->head;
 
        if(idx == 0)
        {
            L->head = tmp->next;
            free(tmp);
        }
        else if(idx >= L->size - 1)
        {
            Node* before = NULL;
            while(tmp->next)
            {
                before = tmp;
                tmp = tmp->next;
            }
 
            free(tmp);
            if(before != NULL) before->next = NULL;
            else L->head = NULL;
        }
        else
        {
            Node* before = NULL;
            for(int i = 0; i < idx; i++)
            {
                before = tmp;
                tmp = tmp->next;
            }
 
            before->next = tmp->next;
            free(tmp);
        }
 
        L->size--;
    }
}
 
 
void list_print(List* L)
{
    Node *tmp = L->head;
 
    while(tmp)
    {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    puts("");
}
 
 
int main()
{
    List* new_list = create_list();
    for(int i = 0; i < 10; i++) push_back(new_list, i);
    for(int i = 0; i < 10; i++){
        node_delete(new_list, i);
        list_print(new_list);
        printf("size = %d\n", new_list->size);
    }
    return 0;
}
 
 
cs


'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
[2263] 트리의 순회  (1) 2017.08.27
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
이중 연결 리스트  (0) 2017.04.22

+ Recent posts

티스토리툴바