How We Coding

Week 8-2 : Binary Search Tree (종강) (추가:180814)

Tutoring/18-1 DS2018. 6. 8. 00:49

<180608>


<소스코드>


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
#include <cstdio>
 
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data) : data(data), left(0), right(0) {}
};
 
class bst {
private:
    Node *root;
 
public:
    bst() : root(0) {}
    
    void insert(int data) {
 
        if(!root) {
            root = new Node(data); 
            return ;
        }
 
        Node *p = 0;
        Node *cur = root;
        while(cur) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
        if(p->data < data) p->right = new Node(data);
        else p->left = new Node(data);
    }
 
    Node* getRoot() { return root; }
 
    void display(Node *root) {
        if(!root) return ; 
        display(root->left);
        printf("%d\n", root->data);
        display(root->right);
    }
 
    void remove(int data) {
        Node *p = 0;
        Node *cur = root;
        while(cur && cur->data != data) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
 
        if(!cur) return ;
 
        if(cur->left == NULL && cur->right == NULL) {
            if(p == NULL) root = NULL;
            else {
                if(p->left == cur) p->left = NULL;
                else p->right = NULL;
            }
        }
        else if(cur->left == NULL || cur->right == NULL) {
            Node *child = cur->left ? cur->left : cur->right;
 
            if(p == NULL) root = child; 
            else {
                if(p->left == cur) p->left = child;
                else p->right = child;
            }
        }
        else {
            Node *sp = cur;
            Node *sc = cur->right;
 
            while(sc->left != NULL) {
                sp = sc;
                sc = sc->left;
            }
            
            if(sp->left == sc) {
                sp->left = sc->right;     
            }
            else
                sp->right = sc->right;
 
            cur->data = sc->data;
            cur = sc;
        }
 
        delete cur;
    }
};
 
int main()
{
    bst *t = new bst();
    t->insert(5);
    t->insert(1);
    t->insert(3);
    t->insert(2);
    t->insert(10);
    t->insert(9);
    t->insert(7);
    t->insert(8);
    t->display(t->getRoot()); puts("");
    t->remove(2);
    t->display(t->getRoot()); puts("");
    t->remove(1);
    t->display(t->getRoot()); puts("");
    t->remove(9);
    t->display(t->getRoot()); puts("");
    return 0;
}
 
cs



1) 데이터의 삽입 과정


18 7 26 31 3 12 9 27




2) 데이터 찾기.



3) 데이터의 삽입



4) 데이터의 삭제


4-1) 타겟 노드가 단말노드인 경우


4-2) 타겟 노드가 자식을 하나만 가지고 있는 경우


4-3) 타겟 노드가 두개의 자식을 가지고 있는 경우


>> 타겟의 오른쪽 자식이 왼쪽 서브트리를 가진경우 or not



5) 데이터 탐색의 시간 복잡도

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-1 : Binary Tree 2  (0) 2018.06.05
Week 7-2 : Tree, Binary Tree  (0) 2018.05.27
Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08

Week 8-1 : Binary Tree 2

Tutoring/18-1 DS2018. 6. 5. 23:55

<180605>


0) 트리에서 노드의 갯수 구하기


1
2
3
4
5
int getNodeCnt(TreeNode *root)
{
    if(root == NULL) return 0;
    return 1+getNodeCnt(root->left)+getNodeCnt(root->right);
}
cs


>> 트리의 노드의 갯수 = 자기 자신 + 왼쪽 서브트리의 노드의 갯수  + 오른쪽 서브트리의 노드의 갯수



1) 단말노드의 갯수 구하기


1
2
3
4
5
6
int getLeafNode(TreeNode *root)
{
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL) return 1;
    return getLeafNode(root->left) + getLeafNode(root->right);
}
cs


>> 트리에서 단말노드의 갯수 = 왼쪽 서브트리에서의 단말노드의 갯수 + 오른쪽 서브트리에서의 단말노드의 갯수

>> 3 라인에서의 탈출조건이 필요하다. 이 코드가 없다면, root == NULL 인 경우 에러가 발생한다.

>> root 가 NULL 이라는 것은  root 가 가리키는 트리노드가 없다는 뜻이다. 그런데 root->left 가 의미하는 것은 root가 가리키는 변수의 멤버 left 가 된다.

     가리키는 변수가 없는데, 가리키는 변수의 멤버를 찾는 셈이 된다. 



2) 전위순회, 중위순회의 순서가 주어졌을 때, 후위순회의 순서 구하기

전위순회 순서 : 0 1 3 6 7 4 2 5 8 9

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9


1. 전위순회의 경우, 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 맨 왼쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며,  2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

    전위순회 순서 : [0] [1 3 6 7 4] [2 5 8 9]  

    중위순회 순서 : [6 3 7 1 4] [0] [2 8 5 9] 

    위와 같이 생각할 수 있다.


3.  이젠 왼쪽 서브트리에 대해 생각해보자. 

    전위순회 순서 : [1 3 6 7 4] 

    중위순회 순서 : [6 3 7 1 4] 

    위와 마찬가지로 전위 순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 1 이 this 서브트리의 루트라는 사실을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 후위순회를 구하면 된다...!!


>> 프로그래밍 해보고 싶다면 도전!! (http://boj.kr/4256)

>> 내가 푼 코드 (https://github.com/YongHoonJJo/BOJ/blob/master/4256.cpp)



3) 중위순회, 후위순회의 순서가 주어졌을 때, 전위순회의 순서 구하기.

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9

후위순회 순서 : 6 7 3 4 1 8 9 5 2 0


1. 후위순회의 경우, 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 순회를 한다. 그렇기 때문에 맨 오른쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며,  2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

3. 후위순회의 순서에서는 [6 7 3 4 1][8 9 5 2][0] 으로 생각할 수 있다.

    여기서도 왼쪽 서브트리인 [6 7 3 4 1] 에 대해서 생각해보자. 후위순회는 왼쪽 서브트리에 대해서도 후위순회를 한다. 

    그렇기 때문에 1이 왼쪽 서브트리의 루트라는 것을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다. 

    그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 전위순회를 구하면 된다...!!



4) 트리의 삭제


1
2
3
4
5
6
7
int removeTree(TreeNode *root)
{
    if(root == NULL) return ;
    removeTree(root->left);
    removeTree(root->right);
    free(root);
}
cs


>> 전위순회를 하면 왼쪽 서브트리와 오른쪽 서브트리의 루트를 찾아갈 수 없다.

>> 중위순회를 해도 오른쪽 서브트리의 루트를 찾아갈 수 없게 된다.

>> 그래서 후위순회로 삭제를 진행해야 한다.



5) 트리에서 데이터의 값이 홀수인 노드의 갯수를 구하기


1
2
3
4
5
6
7
\int getOddNode(TreeNode *root)
{
    int cnt=0;
    if(root == NULL) return 0;
    if(root->data & 1) cnt++;
    return cnt + getOddNode(root->left) + getOddNode(root->right);
}
cs


>> 트리에서 테이터의 값이 홀수인 노드의 갯수 = 자신(1 or 0) + 왼쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수 + 오른쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수


6) 디렉토리 용량 구하기.

>> 왼쪽 서브트리의 디렉토리의 용량 + 오른쪽 서브트리의 디렉토리의 용량 + 자기 자신의 용량


7) 수식트리

>> 단말노드에 피연산자가 들어있고, 그 외 노드에는 연산자가 들어있다.

>> 후위순회로 계산할 수 있다. 왼쪽 서브트리에서 계산한 결과와 오른쪽 서브트리에서 계산한 결과를 루트에 있는 연산자에 의한 연산을 하면 된다.


8) 레벨순회

- 큐 라는 자료구조를 사용하며, 나중에 배울 그래프에서의 너비우선탐색(BFS) 알고리즘과 완전히 동일하다.

- 또한 TreeNode의 포인터를 담아야 하므로,  23 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.

   (typedef element int 였다면 int를 TreeNode* 로 바꾸면 됬을텐데.. typedef element int 를 쓰는 이유를 다시한번 되새겨보자..!!)

- 알고리즘은 다음과 같다.

1) 우선 루트를 큐에 담는다.

2) 큐가 비어 있지 않다면, 

3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.

4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다(노드가 존재할 경우). 그리고 2)로 돌아간다.


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
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
// Tree
typedef struct TreeNode {
    int data;
    struct TreeNode * left;
    struct TreeNode * right;
} TreeNode;
 
TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) {
    TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode));
    tmp->data = data;
    tmp->left = left;
    tmp->right = right;
    return tmp;
}
 
// Queue
typedef struct queue {
    TreeNode * data[MAX];
    int front;
    int rear;
} Queue;
 
void init(Queue * q) {
    q->front = 0;
    q->rear = 0;
}
 
int isEmpty(Queue * q) {
    return (q->front == q->rear);
}
 
int isFull(Queue * q) {
    return (q->rear + 1) % MAX == q->front;
}
 
void enqueue(Queue * q, TreeNode * data) {
    if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
    else {
        q->rear = (q->rear + 1) % MAX;
        q->data[q->rear] = data;
    }
}
 
TreeNode* peek(Queue * q) {
    if (isEmpty(q)) {
        printf("(peek)큐가 비어있습니다. : ");
        return NULL;
    }
    return q->data[(q->front + 1) % MAX];
}
 
void dequeue(Queue * q) {
    if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
    else {
        q->front = (q->front + 1) % MAX;
    }
}
 
void level(TreeNode * root) {
    Queue q;
    init(&q);
 
    if (root) enqueue(&q, root);
 
    while (!isEmpty(&q)) {
        TreeNode * tmp = peek(&q); dequeue(&q);
        printf("%d ", tmp->data);
        if (tmp->left) enqueue(&q, tmp->left);
        if (tmp->right) enqueue(&q, tmp->right);
    }
}
 
int main()
{
    TreeNode * t8 = makeTreeNode(8, NULL, NULL);
    TreeNode * t4 = makeTreeNode(4, t8, NULL);
    TreeNode * t5 = makeTreeNode(5, NULL, NULL);
    TreeNode * t6 = makeTreeNode(6, NULL, NULL);
    TreeNode * t7 = makeTreeNode(7, NULL, NULL);
    TreeNode * t2 = makeTreeNode(2, t4, t5);
    TreeNode * t3 = makeTreeNode(3, t6, t7);
    TreeNode * t1 = makeTreeNode(1, t2, t3);
 
    TreeNode * root = t1;
    level(root);
}
 
cs


'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-2 : Binary Search Tree (종강) (추가:180814)  (0) 2018.06.08
Week 7-2 : Tree, Binary Tree  (0) 2018.05.27
Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08

Week 7-2 : Tree, Binary Tree

Tutoring/18-1 DS2018. 5. 27. 22:12

< 180517 >


1) 트리

- 계층구조를 표현하기 위한 비선형 자료구조. ex) 디렉토리

- 노드(형제, 부모, 자식, 루트, 단말)

- 서브트리의 개념 설명. 트리의 자식노드를 루트로 하는 트리.

- 레벨 : 루트노드 기준 노드까지의 거리. 루트의 레벨을 0 으로 두기도 하고, 1로 두기도 한다.

- 높이 : 최대레벨


- 트리의 예시 (그림 출처 : http://wwst.tistory.com/2)

 



- 트리의 종류 : 일반트리, 이진트리


2) 이진트리 (Binary Tree)

- 정의 : 각 노드별 자식노드가 두개 이하로 구성된 트리..(최대 두개의 자식노드)

- 성질 : 노드의 갯수 -1 = 간선의 수

- n 개의 노드로 최대 n 레벨을 만들수 있으며, 최소 ceil(log(n+1))의 레벨을 만들 수 있다. 로그의 밑은 2.

- 이진트리의 종류(일반 이진트리, 완전이진트리, 포화 이진트리)

- 포화이진트리 : 마지막 레벨까지 모든 레벨에 노드가 가득 차 있는 트리.

- 완전이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리.

- 일반이진트리 : 완전도 포화도 아닌 트리 (아래 그림에서 TreeA 는 일반 이진트리)


- 이진트리의 서브트리 (그림출처 : https://kks227.blog.me/221028710658)



>> 서브트리는 부모노드를 기준으로, 한 자식노드를 루트로 하는 트리



< 180529 >


- 이진 트리의 표현


1) 배열을 이용한 표션

>> 주로 힙(Heap)/우선순위 큐에서 사용

>> 구현의 편의상 0번째 인덱스를 사용하지 않는 경우가 많은 것 같다.

>> 현재노드 기준, 부모노드의 인덱스는 현재노드의 인덱스 / 2

>> 현재노드 기준, 왼쪽 자식의 인덱스는 현재노드의 인덱스 * 2

>> 현재노드 기준, 오른쪽 자식의 인덱스는 현재노드의 인덱스 * 2 + 1


2) 링크 표현

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


>> 노드는 이런식으로 디자인을 한다.



- 트리의 순회  (그림출처 : https://kks227.blog.me/221028710658)



전위순회 : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 탐색

중위순회 : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 탐색

후위순회 : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 탐색

레벨순회 : 큐를 이용, 구현은 다음 시간에..!


>> 전위순회의 경우, 왼쪽 서브트리를 순회할때, 재귀적으로 왼쪽 서브트리의 루트를 기준으로 전위순회를 한다.

Preorder : ( 0 ) ( 1 3 6 7 4 ) ( 2 5 8 9 ) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리)

왼쪽 서브트리의 경우 1 3 6 7 4 인데 마찬가지로 (1) (3 6 7) (4) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.

위에서 왼쪽 서브트리는 3 6 7 인데,  마찬가지로 (3) (6) (7) >>  (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.

>> 중위순회, 후위순회도 마찬가지..!!


>> 왼쪽 ,오른쪽이 아니다. 왼쪽 서브트리, 오른쪽 서브트리. 개념 확실히 잡고 넘어가자. 

>> 루트 기준 왼쪽 자식 노드는 왼쪽 서브트리의 루트가 되며, 루트 기준 오른쪽 자식노드는 오른쪽 서브트리의 루트가 된다..!!

>> 트리를 삭제할 때에는 후위순회를 사용해야 한다. 


- 구현


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct TreeNode {
   int data;
   struct TreeNode * left;
   struct TreeNode * right;
} TreeNode;
 
TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) {
   TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode));
   tmp->data = data;
   tmp->left = left;
   tmp->right = right;
   return tmp;
}
 
void preorderPrint(TreeNode * root) {
   if (root) {
      printf("%d ", root->data);
      preorderPrint(root->left);
      preorderPrint(root->right);
   }
}
 
void inorderPrint(TreeNode * root) {
   if(root){
      inorderPrint(root->left);
      printf("%d ", root->data);
      inorderPrint(root->right);
   }
}
 
void postorderPrint(TreeNode * root) {
   if(root) {
      postorderPrint(root->left);
      postorderPrint(root->right);
      printf("%d ", root->data);
   }
}
 
int nodeCount(TreeNode * root) {
   int count = 0;
   if (root) count = nodeCount(root->left) + nodeCount(root->right) + 1;
   return count;
}
 
int height(TreeNode * root) {
   int count=0;
   if (root) {
       int L = height(root->left);
       int R = height(root->right);
       count = (L > R ? L : R) + 1;
   }
   return count;
}
 
void clear(TreeNode * root) {
   if (root) {
      clear(root->left);
      clear(root->right);
      free(root);
   }
}
 
int main()
{
   TreeNode * t8 = makeTreeNode(8, NULL, NULL);
   TreeNode * t4 = makeTreeNode(4, t8, NULL);
   TreeNode * t5 = makeTreeNode(5, NULL, NULL);
   TreeNode * t6 = makeTreeNode(6, NULL, NULL);
   TreeNode * t7 = makeTreeNode(7, NULL, NULL);
   TreeNode * t2 = makeTreeNode(2, t4, t5);
   TreeNode * t3 = makeTreeNode(3, t6, t7);
   TreeNode * t1 = makeTreeNode(1, t2, t3);
 
   TreeNode * root = t1;
 
   preorderPrint(root);
   printf("\n");
   
   inorderPrint(root);
   printf("\n");
   
   postorderPrint(root);
   printf("\n");
 
   printf("노드 갯수 : %d\n", nodeCount(root));
   printf("Tree의 높이 : %d\n", height(root));
   level(root);
}
 
cs


>> 42 라인 : 트리에서 노드의 갯수는 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 1(기준 트리의 루트노드) 이다.

>> preorderPrint() 라는 함수는 한 트리의 루트를 매개변수로 전달 받는다.

    그리고 이 트리는 매개변수로 전달받은 루트를 기준으로 하는 트리에 대해 전위순회를 하는 함수이다.

    전위순호는 루트를 방문하고, 왼쪽 서브트리에 대해 전위순회를 하고, 오른쪽 서브트리에 대해 전위순회를 진행하면 된다.

    왼쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 왼쪽 서브트리의 루트를 매개변수로 전달하면 된다.

    마찬가지로 오른쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 오른쪽 서브트리의 루트를 매개변수로 전달하면 된다.

>> 48 라인 : 트리의 높이는 max(왼쪽 서브트리의 높이, 오른쪽 서브트리의 높이)+1 이 된다.

>> 58 라인 : 트리의 삭제, 후위순회 방식으로 진행한다.

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-2 : Binary Search Tree (종강) (추가:180814)  (0) 2018.06.08
Week 8-1 : Binary Tree 2  (0) 2018.06.05
Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08

Week 7-1 : Stack, Queue by Linked List

Tutoring/18-1 DS2018. 5. 19. 01:21

<180517>


- 연결리스트로 구현한 스택

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} Node;
 
typedef struct stack {
    Node *top;
} Stack;
 
void init(Stack *ps)
{
    ps->top = NULL;
}
 
int isEmpty(Stack *ps)
{
    return ps->top ==  NULL; 
}
 
void push(Stack *ps, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->link = NULL;
    if(!isEmpty(ps)) 
        newNode->link = ps->top;    
    ps->top = newNode;
}
 
int peek(Stack *ps)
{
    return ps->top->data;
}
 
int pop(Stack *ps)
{
    Node *delNode = ps->top;
    int ret = delNode->data;
 
    ps->top = ps->top->link;
    free(delNode);
    return ret;
}
 
int main()
{
    Stack s;
    init(&s);
    isEmpty(&s) ? puts("Empty") : puts("No");
 
    push(&s, 10);
    push(&s, 20);
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    if(!isEmpty(&s)) printf("%d\n", pop(&s));
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    return 0;
}
 
cs


>> 실행결과

Empty

20

20

10


- 연결리스트로 구현한 큐


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} Node;
 
typedef struct queue {
    Node *f, *r;
} Queue;
 
void init(Queue *pq)
{
    pq->f = pq->r = NULL;
}
 
int isEmpty(Queue *pq)
{
    return pq->f ==  NULL; 
}
 
void enqueue(Queue *pq, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->link = NULL;
 
    if(isEmpty(pq)) pq->f = newNode;
    else pq->r->link = newNode;
 
    pq->r = newNode;
}
 
int peek(Queue *pq)
{
    return pq->f->data;
}
 
int dequeue(Queue *pq)
{
    Node *delNode = pq->f;
    int ret = delNode->data;
 
    pq->f = pq->f->link;
    
    free(delNode);
    return ret;
}
 
int main()
{
    Queue q;
    init(&q);
    isEmpty(&q) ? puts("Empty") : puts("No");
 
    enqueue(&q, 10);
    enqueue(&q, 20);
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
    return 0;
}
cs


>> 실행결과

Empty

10

10

20

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-1 : Binary Tree 2  (0) 2018.06.05
Week 7-2 : Tree, Binary Tree  (0) 2018.05.27
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08

Week 6 : Maze(with stack) / Circular Queue

Tutoring/18-1 DS2018. 5. 16. 20:21

< 180515 > 


- 스택의 응용 : 미로탐색


<미로탈출 초기상태>

- 시작좌표는 (1, 0)

- 도착좌표는 (4, 5)

 

- 알고리즘

1) 시작좌표를 현재좌표로 설정

2) 현재좌표가 도착좌표가 아니면

2-1) 현재좌표를 방문체크.

2-2) 현재좌표 기준 상하좌우의 좌표를 스택에 넣음.

2-2-1) 스택에 넣기전, 미로의 영역을 벗어나거나, 이미 방문한 좌표는 스택에 넣지 않는다. (예외처리)

2-3) 스택이 비어 있는지 확인. 비어있다면, 탈출 불가능한 미로

2-4) 스택에서 좌표 하나를 꺼내어 현재 좌표로 변경 후 2)로 돌아간다.

3) 탈출성공.


- 현재좌표 기준 상하좌우 좌표


- 미로 탈출 과정 (현재 위치 : H, 방문체크 : -, 방문체크한 곳 기준 상하좌우의 좌표를 스택에 담음.)


>> 이러한 과정으로 진행이 된다.





- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조

- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐), 

            스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)



- 기본 큐 


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
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int q[MAX];
    int f, r;
} Queue;
 
void init(Queue * q) {
    q->f = q->r = 0;
}
 
int isEmpty(Queue * q) {
    return (q->f == q->r);
}
 
void enqueue(Queue * q, int data) {
    q->q[(q->r)++] = data;
}
 
int peek(Queue * q) {
    return q->q[q->f];
}
 
int dequeue(Queue * q) {
    return q->q[q->f++];
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
 
    return 0;
}
 
cs


>> 데이터의 삽입은 rear 가, 데이터의 삭제(꺼내기)는 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
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int q[MAX];
    int f, r;
} Queue;
 
void init(Queue * q) {
    q->f = q->r = 0;
}
 
int isEmpty(Queue * q) {
    return (q->f == q->r);
}
 
void enqueue(Queue * q, int data) {
    q->r = (q->r+1)%MAX;
    q->q[(q->r)] = data;
}
 
int peek(Queue * q) {
    return q->q[(q->f+1)%MAX];
}
 
int dequeue(Queue * q) {
    q->f = (q->f+1)%MAX;
    return q->q[q->f];
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
 
    return 0;
}
 
cs


>> 처음 비어있는 상태는 f와 r이 같은 곳을 가리킬때..!!

>> 원형큐는 한칸을 비워둔다. 그렇지 않으면 비어있는 상태와 가득차있는 상태를 구분할 수 없게 된다.

>> f가 가리키는 곳는 마지막으로 데이터를 꺼낸 곳이라고 생각하면 된다. 즉 비어있는 곳.

>> 마찬가지로 데이터의 삽입은 r 로, 데이터를 꺼내는 작업은 f 를 이용한다.

>> 원형큐이기 때문에 배열의 마지막 인덱스 다음에 0번째 인덱스로 와야 한다. 

     이를 해결해주는 방법이 배열의 다음 인덱스를 항상 배열의 크기로 나눈 나머지로 처리하면 된다. 

     모듈러 연산을 하면, 배열이 크기보다 작은 인덱스들은 자기 자신이 되지만, 

     마지막인덱스에서 다음으로 넘어가면 배열의 크기가 되는데, 이는 크기로 나눈 나머지를 계산하면 0이 된다.



- 원형큐에서의 문제.


1) 배열의 크기가 8이고, f가 3을, r이 5을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 2개

2) 배열의 크기가 8이고, f가 5을, r이 3을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 6개

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 7-2 : Tree, Binary Tree  (0) 2018.05.27
Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20

Week 5-2 : infix to postfix, exp(postfix)

Tutoring/18-1 DS2018. 5. 8. 23:51

< 180508 >



1) 후위식의 계산


- 피연산자를 만나면 push

- 연산자를 만나면 스택에 담겨있는 두개의 피 연산자를 꺼낸 다음(pop) 연산 후 다시 push


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
int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch(eq[i]) {
            case '+': push(&s, op1+op2); break;
            case '-': push(&s, op1-op2); break;
            case '*': push(&s, op1*op2); break;
            case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    printf("%d\n", exp("234*+"));       // 14
    printf("%d\n", exp("82/3-32*+"));   // 7
    return 0;
}
cs


>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.

>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.



2) 중위식을 후위식으로.


- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.


- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 push.

>> 스택 위에 있는 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력. 

    우선순위가 낮은 연산자를 만날 때 까지 반복 후 해당 연산자 push.

>> ( 가중치에 상관없이 스택에 쌓는다. 

>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.



- 빠르게 계산하기.

>> 후위식을 계산하는 방식에서 연산자 앞에는 두개의 피연산자가 있어야 하는 원리를 이용.


a / (b-c+d) * (e-a) * c 에서 밑줄 친 수식들이 먼저 계산이 될 것이다. 

a(_____)/ 가 될 것이며, 이 결과를 A 라고 하자. ______ 은 나중에 계산.

그렇다면 처음의 식은  A * (e-a) * c 가 되는데, 역시 여기서도 밑줄 친 수식들이 먼저 계산이 될 것이다. 

A(___)* 가 될 것이며 이 결과를 B 라고 하자.

그럼 맨 처음 식은 B * c 가 되며 이것은 후위식으로 바꾸면 Bc* 가 될 것이다.

B를 풀어쓰면 A(___)*c* 가 되고,

A를 풀어쓰면 a(_____)/(___)*c* 이 된다.

이제 나중에 계산하기로 한 b-c+d 를 생각해보자. 생각할 필요도 없다. bc-d+ 이다.

그럼 위의 식은 abc-d+/(___)*c* 가 되고, 

아직 계산하지 않은 나머지인 e-a 는 ea- 가 된다. 

최종적으로 abc-d+/ea-*c* 이 된다.



Ex2)  a + (b-c+d) * (e-a) * c 를 생각해보자.


a + (b-c+d) * (e-a) * c 에서는 a 와 밑줄친 식의 결과를 더하는 연산이 진행되어야 한다.

a(_____________)+ 의 형태가 나온 것이다.

(b-c+d) * (e-a) * c 에서는 역시 밑줄친 수식이 먼저 계산이 될 것이기 때문에

(__________)c* 라고 쓸 수 있다.

두 식을 결합하면 a(_____________)c*+ 이 되고, 

(b-c+d) * (e-a) 에서 b-c+d 의 결과를 A, e-a 의 결과를 B라고 하면 후위식으로 AB* 가 될 것이다.

역시 위의 식을 다시 결합하면  aAB*c*+ 가 되고,

A를 풀어쓰면 bc-d+, B를 풀어쓰면 ea- 가 된다.

대입하면 최종적으로 abc-d+ea-*c*+ 가 된다.



<숙제>

- 중위식을 후위식으로 바꾸는 프로그래밍.

- 중위식을 후위식으로 바꾼 다음 그 후위식을 계산하는 프로그래밍.


'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 4-1 : Linked List  (0) 2018.04.18

Week 5-1 : Circular Doubly Linked List / Stack ADT

Tutoring/18-1 DS2018. 5. 8. 11:18

< 180503 >


1) 원형 이중연결리스트 with 더미노드


- 더미노드 : 말그대로 더미인 노드.

>> 더미노드를 사용하면, head 포인터가 가리키는 대상이 바뀔일이 없다. 항상 더미노드를 가리키므로.

>> 이전에는 head 포인터가 가리키는 대상이 변경될 여지가 있으면 이중 포인터를 써야했는데, 

     더미노드를 쓰면 그럴 필요가 없어진다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
 
typedef struct listNode {
    int data;
    struct listNode *llink, *rlink;
} ListNode;
 
int main()
{
    ListNode *head = NULL;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->rlink = head;
    head->llink = head;
 
}
cs


>> 또한 지금까지는 head 포인터는 NULL 로만 초기화 했지만, 더미노드 사용하는 경우 더미노드를 만드는 과정을 추가해야한다.

>> 여기서의 더미노드 초기화 코드는 양방향 원형 연결리스트이므로 저런식으로 하면 될 것 같다.



- 삽입하기 / 삭제하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void addNode(ListNode *before, ListNode *newNode)
{
    newNode->rlink = before->rlink;
    newNode->llink = before;
    before->rlink = newNode;
    newNode->rlink->llink = newNode;
}
 
 
void delNode(ListNode *phead, ListNode *remove)
{
    if(remove == phead) return ;
    remove->rlink->llink = remove->llink;
    remove->llink->rlink = remove->rlink;
    free(remove);
}

cs


>> 노드를 삽입하는 함수에서는 순서가 중요하다. 

>> 12번 라인의 예외처리는 삭제하려는 노드가 더미노드인경우 이다. 더미노드를 사용하는 리스트인데 더미노드를 삭제하면 안되기 때문..!



- 지금까지의 내용을 그림으로 그려보면 다음과 같다. (PPT로 안그릴꺼임...ㅡㅡ)





2) 스택 구현하기


- 스택의 정의 : 나중에 들어온 데이터가 먼저 꺼내진다. 

>> 그냥 프링글스 ㅎㅎ


- 스택의 ADT 및 구현하기


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
#include <stdio.h>
#define MAX 100
 
typedef struct stack {
    int s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, int data)
{
    if(isFull(s)) return ;
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
int pop(Stack *s)
{
    return s->s[(s->top)--];
}
 
int main()
{
    Stack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    isFull(&s) ? puts("Full") : puts("Not Full");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    if(!isEmpty(&s)) printf("%d\n", pop(&s));
 
    return 0;
}
cs


>> 실행결과

Empty

Not Full

7

7


>> isFull() 에서 왜 MAX-1 일때가 가득찬 상태인지 생각해보기..!!

>> top 의 역할은 스택을 구성하는 배열에서 가장 마지막에 위치한 데이터의 인덱스..!!



2-2) 연결리스트를 이용한 구현 (참고)


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
   char data;
   struct node * next;
} Node;
 
typedef struct listStack {
   Node * top;
} ListStack;
 
void init(ListStack * list) {
   list->top = NULL;
}
 
int isEmpty(ListStack * list) {
   return list->top == NULL;
}
 
int peek(ListStack * list) {
   if(isEmpty(list)) {
      printf("빈 스택임");
      return -111111;
   }
   
   return (list->top)->data;
}
 
void push(ListStack * list, int data) {
   Node * tmp = (Node*) malloc(sizeof(Node));
   tmp->data = data;
   tmp->next = list->top;
   list->top = tmp;
}
 
void pop(ListStack * list) {
   Node *tmp = list->top;
   list->top = tmp->next;
   free(tmp);
}
 
int main()
{
    ListStack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    return 0; 
}
 

cs


>>  여기서는 pop 할때 데이터를 꺼내지 않도록 설계를 한 경우.




### 스택의 응용 ###


3) 올바른 괄호 문자열

- "()()" 는 올바른 괄호 문자열

 - "(())" 는 올바른 괄호 문자열

- "(()())" 는 올바른 괄호 문자열

- "()(" 는 x

- "())(" 는 x




'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-2 : Linked List  (0) 2018.04.15

Week 4-2 : Circular Linked List

Tutoring/18-1 DS2018. 4. 20. 00:29

< 180419 >


< Homework >


- 단일 연결리스트에서 최대값을 가지는 노드를 맨 마지막으로 보내기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void maxLast(ListNode **phead)
{
    ListNode *p, *cur = *phead;
    ListNode *pMax, *cMax = cur;
 
    if(cur == NULL) return ;
 
    while(cur) {
        if(cur->data > cMax->data) {
            pMax = p; cMax = cur;
        }
        p = cur; cur = p->link;
    }
 
    if(pMax == NULL) *phead = cMax->link;
    else pMax->link = cMax->link;
 
    p->link = cMax;
    cMax->link = NULL;
}
cs


>> while() 문이 끝나면 cur 는 NULL, p 는 마지막 노드를 가리키게 된다.

>> cMax 는 최대값을 가지고 있는 노드를, pMax 는 최대값을 가지고 있는 노드의 이전 노드를 가리키게 된다.



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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct cListNode {
    int data;
    struct cListNode *next;
} CListNode;
 
void CircularListAdd(CListNode **phead, int data)
{
    CListNode *p, *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
 
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    p = *phead;
    while(p->next != *phead)
        p = p->next;
 
    p->next = newNode;
    newNode->next = *phead;
    //*phead = newNode;
}
 
void cDisplay(CListNode *phead)
{
    CListNode *cur = phead;
 
    if(cur == NULL) return ;
 
    do {
        printf("%d\n", cur->data);
        cur = cur->next;
    } while(cur != phead);
}
 
int main()
{
    CListNode *head = NULL; 
    CircularListAdd(&head, 1);
    CircularListAdd(&head, 3);
    CircularListAdd(&head, 7);
    CircularListAdd(&head, 5);
 
    cDisplay(head);    
 
    return 0;
}
cs


>> 9 : 원형 연결리스트의 데이터를 삽입하는 함수.

>> 29 : 원형 연결리스트의 데이터를 출력하는 함수. do ~ while() !!


>> 49 라인의 결과는 1, 3, 7, 5

>> 26 라인의 주석을 해제하면, 49 라인의 결과는 5, 7, 3, 1

>> 즉 26가 없으면 뒤로 삽입, 있으면 앞으로 삽입을 하는 결과가 만들어진다.


>> 다만 위의 코드에서는 삽입을 할때, 항상 맨 마지막 노드를 찾아야 하는 번거로움(?)이 있다. (21-22 라인)

     하지만 헤드포인터를 테일이라고 생각하고 코드를 작성하면 그럴필요가 없어진다..!!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void CircularListAdd2(CListNode **phead, int data)
{
    CListNode *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
    
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    newNode->next = (*phead)->next;
    (*phead)->next = newNode;
    //*phead = newNode;
}
cs


>> main() 에서의 head 를  tail 이라고 생각하는 것이 그림을 그려가는데 있어서 이해하기 쉽다.

>> 14 가 없으면 뒤로 삽입, 14가 있으면 앞으로 삽입하는 코드가 된다.


>> 뒤로 삽입시 출력 결과는 1 5 7 3, 

>> 앞으로 삽입했을 때 결과는 5 1 3 7 이 나온다. 

>> 우리가 작성한 코드대로라면 마지막 노드를 먼저 출력하고 나머지를 출력하기 때문이다.

>> head 포인터가 항상 마지막 노드를 가리키고 있기 때문이다.

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11

Week 4-1 : Linked List

Tutoring/18-1 DS2018. 4. 18. 01:49

< 180417 >


1) 연결리스트에서 특정 값을 찾는 함수.

1
2
3
4
5
6
7
8
9
10
ListNode* search(ListNode *head, int x)
{
    ListNode *p = head;
    while(p) {
        if(p->data == x) 
            return p;
        p = p->link;
    }
    return p; // p == NULL
}
cs


>> main() 에서의 head 포인터가 가리키는 대상이 변경될 가능성이 없기 때문에..!! 싱글포인터 자체로 매개변수로 전달 받는다.

>> 찾는 값이 없으면 NULL 을 리턴한다.



2) 연결리스트에서 최대값을 갖는 노드와 마지막 노드 교환하기.


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
void changeMax(ListNode **phead)
{
    ListNode *prev=NULL, *cur=*phead;
    ListNode *pMax=NULL, *cMax=*phead;
 
    if(*phead == NULL) return ;
    
    while(cur->link != NULL) {
        if(cMax->data < cur->data) {
            cMax = cur;
            pMax = prev;
        }       
        prev = cur;
        cur = cur->link;
    }
    // Compare cMax with last Node
    if(cMax->data < cur->data) {
        cMax = cur;
        pMax = prev;
    }       
 
    // swap node
    pMax == NULL ? (cur->link = (*phead)->link) : (cur->link = pMax->link);
    pMax == NULL ? (*phead = cur) : (pMax->link = cur);
    prev->link = cMax;
    cMax->link = NULL;
}
cs


>> 8 : cur->link != NULL 이라고 조건의 설정해야 cur 포인터가 마지막 노드를 가리키게 된다.

>> 23-26 : 노드를 스왑하는 과정이다. 그림을 그려가며 순서를 잘 파악한 다음 코드로 옮겨버릇하자.

>> 매개변수로는 더블포인터를 주었다. main() 에서의 head 포인터가 가리키는 노드가 변경될 수 있기 때문이다.

     (head 포이터가 가리키는 첫번째 노드가 최대값인 경우)

>> 가만 잘 생각해보면, 굳이 노드를 스왑할 필요는 없어보인다. 두 노드의 data만 swap 하면 되는데, 뭣하러 이리 어렵게 했나 싶다.




3) 두 개의 연결리스트 이어 붙이기.


- 교재의 있는 코드는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* concat(ListNode *head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) return head2;
    if(head2 == NULL) return head1;
    
    p = head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
    return head1;
}
cs


>> 이전까진 별 생각이 없었는데, 다시보니 head1 == NULL 인경우, 이 함수가 종료가 되어도 head1 은 NULL 상태 그대로다.

>> 하지만, head1 != NULL 인 경우, 마지막 노드에 head2 가 가리키는 노드를 이어 붙인다음 head1 의 주소를 리턴한다.

     즉, 위의 경우 head1 의 변경이 없는데, 아래의 경우 head1 의 변경이 생긴다. 일관성이 없다.. 맘에 안든다;;



- 그래서 바꾸어 보았다. 무조건 head1 의 뒤에 이어붙여지는 결과가 될 수 있도록..!!

1
2
3
4
5
6
7
8
9
10
11
12
void concat(ListNode **head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) { *head1 = head2; return ; }
    if(head2 == NULL) return ;
    
    p = *head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
}
cs


>> 8-9 : 루프를 빠져나가면 p는 마지막 노드를 가리키는 상태가 된다.


>> 예시는 아래와 같다.



'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05

Week 3-2 : Linked List

Tutoring/18-1 DS2018. 4. 15. 18:30

< 180412 >



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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode(ListNode** phead, ListNode* newNode)
{
    if(*phead == NULL) *phead = newNode;
    else {
        newNode->link = *phead;
        *phead = newNode;
    }
}
 
int main()
{
    ListNode *head = NULL;
    addNode(&head, create_node(10, NULL)); 
    addNode(&head, create_node(20, NULL)); 
     
    return 0;
}
cs


>> 19 : 메인함수에서의 head 가 NULL 인경우 바로 뉴노드를 연결하면 된다.

>> 20-23 : head 가 어떤 노드를 가지고 있다면, 새로운 노드가 그 노드를 가리키고, head 가 뉴노드를 가리키도록 한다.


>> 이런식으로 진행이 된다.




2) 노드 추가하기 2 (교재처럼..) 


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode2(ListNode **phead, ListNode *p, ListNode *newNode)
{
    if(*phead == NULL) *phead = newNode;
    else if(p == NULL) {
        newNode->link = *phead;
        *phead = newNode;
    }
    else {
        newNode->link = p->link;
        p->link = newNode;
    }
}
 
void display(ListNode *phead)
{
    while(phead) {
        printf("%d ", phead->data);
        phead = phead->link;
    }
}   
 
int main()
{
    ListNode *head = NULL;
    ListNode *node;
    addNode2(&head, NULL, create_node(10, NULL)); 
    node = create_node(20, NULL);
    addNode2(&head, NULL, node); 
    addNode2(&head, NULL, create_node(30, NULL)); 
    display(head); puts("");
 
    addNode2(&head, node, create_node(40, NULL));
    display(head); 
    return 0;
}
cs


>> addNode2() 를 보자.  

>> 첫번째 매개변수는 메인함수의 head 의 주소를, p 에는 새로 삽입할 노드의 이전 노드를, 마지막은 새로 삽입할 노드를 가리킨다.

>> 19 : 헤드가 비어있는 경우,

>> 20 : p == NULL 이란 것은 맨 왼쪽에 노드를 삽입하는 경우

>> 그 외의 경우는 p 노드의 다음자리에 새로운 노드를 삽입하는 경우 이다.


>> 실행결과


30 20 10 

30 20 40 10



>> 그림으로 보면 아래와 같다.


- 45 라인까지의 실행결과.




- 48 라인에서 addNode2() 가 호출된 직후의 상황

>> phead 는 *phead 라고 생각하는게 나을것 같다.




- addNode2() 가 호출된 다음, 함수가 종료되기 직전의 상황.

>> phead 는 *phead 라고 생각하는게 나을것 같다.




3) display() 함수 (30-36 라인)


>> display() 함수를 보쟈. 함수의 내용은 어렵지 않을 것이다. 하지만 addNode() 와 비교해보면, 이중포인터로 받지 않는다는 것이 차이점이다.

>> 이것은 main() 의 head 가 가리키는 노드가 변경될 가능성이 있을 경우에는 이중포인터로 받아야 하지만, 

     display() 는 그럴필요가 없기 때문에 이중포인터로 받을 필요가 없다..!!



4) 노드의 삭제


'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05
Week 2-1 : How to code Recursive function2  (0) 2018.04.04

티스토리툴바