BOJ 1918 후위표기식

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

구조체로 스택을 만들고 다시 해보았습니다.(.cpp에서 돌려야합니다.)

설명은 이전의 글을 참조해주세요.

  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #define MAX_SIZE 10000
  ​
  typedef struct stack {
      char s[MAX_SIZE];
      int size;
  ​
      stack() {
          size = 0;
      }
  ​
      int empty() {
          if (size) return 0;
          else return 1;
      }
  ​
      void push(char c) {
          s[size] = c;
          size++;
      }
  ​
      void pop() {
          if (!empty()) {
              size--;
          }
      }
  ​
      char top() {
          return s[size - 1];
      }
  }stack;
  ​
  ​
  char* getPostOrder(char* str) {
      int len = strlen(str);
      char* ret = (char*)malloc(sizeof(char) * (len + 1));
      int retIdx = 0;
          
      stack s;
  ​
      for (int i = 0; i < len; i++) {
          if (str[i] == '+' || str[i] == '-') {
              while (!s.empty() && s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '*' || str[i] == '/') {
              while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.push(str[i]);
          }
          else if (str[i] == '(') {
              s.push(str[i]);
          }
          else if (str[i] == ')') {
              while (s.top() != '(') {
                  ret[retIdx++] = s.top();
                  s.pop();
              }
              s.pop();
          }
          else if (str[i] >= 'A' && str[i] <= 'Z') {
              ret[retIdx++] = str[i];
          }
      }
  ​
      while (!s.empty()) {
          ret[retIdx++] = s.top();
          s.pop();
      }
  ​
      ret[retIdx] = '\0';
  ​
      return ret;
  }
  ​
  int main() {
      char str[MAX_SIZE];
      scanf("%s", str);
  ​
      char *ret = getPostOrder(str);
      printf("%s", ret);
  ​
      free(ret);
  ​
      return 0;
  }

저작자표시

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

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


원형 큐입니다.


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


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

중위표기식의 식을 입력 받아서 후위 표기식으로 바꾼 후

계산하는 스택 계산기입니다.


후위로 바꾸는 방법을 모르신다면 아래의 글을 참고해주세요

http://donggod.tistory.com/45


그리고 정석적인 방법이 아닙니다!!!

그냥 제가 생각나는데로 코딩했기 때문입니다...ㅠ_ㅠ....(근데 이게 정석일수도? 냐하하..)


문자열로 받은 식을

후위로 바꿉니다.

후위로 바꿀 때 숫자 뒤에는 항상 '$'을 붙였습니다. 문자열이기 때문에 숫자라는 구분을 넣어준 것입니다.


예를들어 1000 + 300

이면

1000300+가 될텐데 1000300인건지 아니면 1000 300 인것인지 구분하기 위함입니다.

그래서 1000$300$+가 됩니다.


후위를 스택으로 계산하는 방법은

후위식에서 AB+C+라는 식이 있으면


A와 B를 스택에 삽입하고 기호를 만나면 스택에서 가장 위의 값 두개를 팝하고 +연산을 한 후에

다시 스택에 넣습니다.

과정을 보여드리자면


스택 : A,B

기호 : +


그럼 A와 B를 꺼내서 (A+B)라는 값이 만들어집니다


이것을 다시 스택에 넣습니다.


스택 : (A+B)

기호 : 


또 스택에 C가들어오겠죠

스택 : (A+B),C

기호 : +


또 두개를 꺼내서 계산합니다


(A+B+C)라는 값이 만들어지곘죠


스택 : A+B+C

기호 :


완성됐습니다!


아래는 코드입니다.

궁금한 점은 댓글 주세요


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
#include <cstdio>
#include <iostream>
#include <utility>
#include <stack>
#include <string.h>
using namespace std;
 
 
//이전 자료구조 글을 참고하세요 [1918] 후위표기식
// http://donggod.tistory.com/45
//그 코드에서 바뀐 부분만 주석 달겠습니다.
void prefix(char *str, char *output) {
    stack<char> s;
    int oIdx = 0;
 
    for (int i = 0; i < strlen(str); i++) {
        //A~Z가 아닌 숫자로 바뀜
        //숫자일 때 까지 output에 넣고
        //마지막에 '$'를 삽입
        //ex) 1000+30 이면 1000$30$+
 
        if (str[i] >= '0' && str[i] <= '9') {
            int j;
            for (j = i; str[j] >= '0' && str[j] <= '9'; j++) {
                output[oIdx++] = str[j];
            }
            output[oIdx++] = '$';
            i = j - 1;
        }
        else {
            if (str[i] == '(') s.push(str[i]);
            else if (str[i] == ')') {
                while (s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.pop();
            }
            else if (str[i] == '*' || str[i] == '/') {
                while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
            }
            else {
                while (!s.empty() && s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
 
            }
        }
    }
 
    while (!s.empty()) {
        output[oIdx++] = s.top();
        s.pop();
    }
    output[oIdx] = '\0';
}
 
//prefix로 바뀐 output, 인덱스를 포인터로 받음
//'$'를 만날 때 까지 10씩 곱해주며 숫자로 바꾼 후 리턴
int toInt(char *output, int* idx) {
    int ret = 0;
    for (; output[*idx] != '$'; (*idx)++) {
        ret *= 10;
        ret += output[*idx] - '0';
    }
    return ret;
}
 
int calcuration(char *output) {
    stack<int> s;
 
    for (int i = 0; i < strlen(output); i++) {
        if (output[i] >= '0' && output[i] <= '9') {
            int a = toInt(output, &i);//문자열을 숫자로 바꿈
            s.push(a);//스택에 삽입
        }
        else {
            int b = s.top();
            s.pop();
            int a = s.top();
            s.pop();
 
            switch (output[i]) {
            case '+':
                a += b;
                break;
            case '-':
                a -= b;
                break;
            case '/':
                a /= b;
                break;
            case '*':
                a *= b;
                break;
            }
            
            s.push(a);
        }
    }
 
    return s.top();
}
 
int main() {
    char str[10000];
    char output[10000];
 
    scanf("%s", str);
    prefix(str, output);
 
    printf("%d\n", calcuration(output));
 
    return 0;
}
cs


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

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

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


어떤 회사의 인턴 사전 시험에서 스택 계산기 문제가 나왔습니다.


식을 문자열로 받고 계산하는 문제였는데..


총 7문제?? 정도였던것 같은데.. 손코딩으로 해야해서..

시간이 모잘라서 못풀었습니다ㅠ_ㅠ

기억도 되살릴겸 다시 풀어봤습니다!

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


어떤식을 후위연산으로 바꿀 때 중요한 것은

기호들의 우선순위 입니다.

*, / 곱하기와 나누기는 우선순위가 같습니다.

+, - 플러스와 마이너스는 우선순위가 같습니다.


위 두개의 우선순위는 ('+', '-') < ('*', '/') 이렇게 됩니다.

곱하기와 나누기가 플러스 마이너스 보다 우선순위가 높은 것이지요.


예를 들어 설명해드리자면!


3 + 4 * 8 이라는 식이 있으면 답은 3 + 32 = 35 겠지요!?

여기서 * 곱하기를 먼저 계산하셨을겁니다! 이 우선순위를 말하는 것입니다!


ABC+*라는 식은 A * (B + C)입니다.

A * (B + C)라는 식을 후위연산으로 바꾸는 과정을 보여드릴게요!


스택은 왼쪽이 bottom 가장 오른쪽이 탑입니다.

출력은 그냥 왼쪽부터 오른쪽 순입니다.

먼저 A를 만났습니다.


1.

스택 :

출력 : A


가 되겠죠?

과정을 쭉 보여드릴게요오오~~


2.

스택 : *

출력 : A


3.

스택 : *(

출력 : A


4.

스택 : *(

출력 : AB


5.

스택 : *(+

출력 : AB



6.

스택 : *(+

출력 : ABC


7.
이제 여기서 중요합니다!
')' 기호를 만나면 ! 스택에서 '(' 까지 전부 pop 해줍니다!!!! 여기서는 + 밖에없으므로!

스택 : *(+

출력 : ABC


스택 : *
출력 : ABC+

가 됩니다!

이제 문자열이 끝났으니
스택에 남아있는것을 스택이 empty가 될때까지 비워주면서 차례차례 출력 문자열에 넣어줍니다!
결과 : ABC+*
가 됩니다!

ABC*+라는식은 A + B * C입니다.

A + B * C 를 한번 위의 절차처럼 따라해보세요!!!

주의할 점은 *가 +보다 우선순위가 높다는 점!


아래는 1918 문제의 코드입니다.

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
#include <cstdio>
#include <iostream>
#include <utility>
#include <stack>
#include <string.h>
using namespace std;
 
int main() {
    char str[1000]; //input
    char output[1000]; // output
 
    scanf("%s", str);
 
    stack<char> s; // +-*/(를 저장할 스택
    int oIdx = 0; // 출력 문자열의 인덱스
 
    // str의 문자열을 끝까지
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') output[oIdx++] = str[i]; // A~Z는 출력문자열에 추가
        else {
            //그게아니면 전부 기호이므로
            //아래처럼 처리
 
            if (str[i] == '(') s.push(str[i]); // '('문자는 무조건 스택에 추가
            else if (str[i] == ')') { // ')'문자는 '('문자를 만날 때까지 pop
                while (s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.pop();
            }
            else if (str[i] == '*' || str[i] == '/') {
                //우선순위가 나보다 높거나 같은것을 pop
                //( '/','*'보다 우선순위가 높은것은 없음)
                while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
            }
            else { // '+', '-' 인 경우
                while (!s.empty() && s.top() != '(') {
                    //우선순위가 나보다 높거나 같은것을 pop
                    //('+', '-'보다는 전부 우선순위가 높으므로 '('나 스택이 빌 때까지 pop)
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
 
            }
        }
    }
 
    //스택에 남아있는 것을 전부 pop
    while (!s.empty()) {
        output[oIdx++] = s.top();
        s.pop();
    }
    output[oIdx] = '\0';
 
    printf("%s\n", output);
 
    return 0;
}
cs


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

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

노드 구조체

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

티스토리툴바