반응형

0. 자료구조를 하기 앞서


1. http://www.acmicpc.net 에 가입 되어 있지 않다면 가입한다. (이메일 인증이 있다면 이메일 인증까지)


2. https://www.acmicpc.net/group/3060 를 들어가서 가입 신청을 누른다.


3. 연습 문제란에 있는 문제를 풀어본다.

(어려운 문제가 아닌 위의 사이트에서 입 출력을 어떻게 해서 문제를 어떻게 푸는지 알려주기위함)



1. 연결 리스트 사용이유?

- 연결 리스트는 배열과 같이 크기가 정해져 있는 자료구조와 달리 메모리를 동적으로 사용할 수 있다는 장점이 있다.

- 연결 리스트개념을 알아야 포인터를 자유자제로 잘 다룰 수 있고, 추후에 배울 트리, 그래프 코딩을 잘 할 수 있다.


** 참고 **

int arr[100];같은 것을 인접 행렬이라하고, 포인터를 이용하여 리스트로 이루어 진것을 인접 리스트라 한다.



2. 이중 연결리스트

이제 연결리스트가 무엇인지 알았으니 이중 연결리스트를 배워보도록 한다.


** 아니 연결리스트도 안하고 이중 연결리스트를 한다구요?? **


지금 이 시간을 통해 이중 연결리스트를 배우면 연결 리스트는 자동으로 따라오게 된다.


따라서 연결 리스트를 넘기고 이중 연결리스트를 바로 배워보도록 하자.


심지어 여기서는 더미노드가 있는 이중 연결리스트를 만들어 볼 것이다.


더미노드 생성 이유?

1. 더미노드가 있으면 이중 연결리스트에서 head와 tail이 움직일 필요가 없어진다.

2. 삽입/삭제 시 코드가 간결해지고 논리가 쉬워진다.

등등.. 연결리스트에 더미노드가 필요한 이유



(스스로 해보기)

직접 더미노드가 없는 이중 연결리스트를 제작해보자.

그리고 뭐때문에 더미더미 거리는지 한번 확인해보자.

http://www.crocus.co.kr/342 (더미노드가 없는 이중 연결 리스트 설명)

http://www.crocus.co.kr/343?category=150836 (더미노드가 없는 이중 연결 리스트 코드)






3. 더미 노드가 있는 이중 연결 리스트 그림






(더미 노드의 유무 차이를 위의 그림을 통해 이해해보자)



4. 더미 노드가 있는 이중 연결 리스트 코드


1. struct로 짜도 되고 class로 짜도 된다.

2. friend class LIST를 통해 NODE 클래스의 private값을 LIST 클래스가 이용 할 수 있게 된다.

3. 생성자 소멸자 주석을 지워서 생성자 소멸자가 호출되는 것도 한번 보자.


아래 코드를 짜보고 main부분과 all 부분을 적절히 수정하여 https://www.acmicpc.net/problem/11720 문제를 풀어보자.


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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
class NODE{
    friend class LIST;
 
private:
    int data;
    NODE *left;
    NODE *right;
};
 
class LIST {
private:
    NODE *head;
    NODE *tail;
    
public:
    LIST(){
        //cout << "\n\n생성자 호출\n\n" << endl;
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
    }
 
    ~LIST() { 
        init();
        delete head;
        delete tail;
 
        //cout << "\n\n소멸자 호출\n\n " << endl; 
    }
 
    void init() {
        // 더미노드 사이 모든 값 삭제
        NODE *pos = head;
        while (pos->right != NULL)
        {
            NODE *delNode = pos;
            pos = pos->right;
 
            delete delNode;
        }
        delete tail; // 마지막 tail이 삭제되지 않았다.
 
        // 더미노드 새로 생성(생성자와 동일)
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
    }
    void insert(int val) {
        // 리스트가 형성되어 있지 않았을 때
        if (head->right == NULL)
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->left = head;
            head->right = newNode;
            
            newNode->right = tail;
            tail->left = newNode;
        }
 
        else
        {
            NODE *newNode = new NODE;
            newNode->data = val;
            
            newNode->left = tail->left;
            tail->left->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
    }
    void del(int val) {
        NODE *pos = head;
        bool isFind = false;
        while (pos->right != NULL)
        {
            if (pos->data == val)
            {
                pos->left->right = pos->right;
                pos->right->left = pos->left;
                delete pos;
                isFind = true;
                break;
            }
            pos = pos->right;
        }
 
        if (!isFind)
            cout << "삭제할 데이터가 없습니다." << endl;
    }
 
    void all() {
        NODE *pos = head;
        while (pos != NULL)
        {
            // 더미노드는 출력하지 않는다.
            if (!(pos == head || pos == tail))
                cout << pos->data << " ";
        
            pos = pos->right;
        }
        cout << endl;
    }
};
int main()
{
    LIST list;
 
    while (1)
    {
        int num;
        cout << "1 :: 초기화\n2 :: 추가\n3 :: 삭제\n4 :: 전체출력\n5 :: 종료\n입력 :: ";
        cin >> num;
 
        if (num == 1)
            list.init();
 
        else if (num == 2)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            list.insert(val);
        }
 
        else if (num == 3)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            list.del(val);
        }
 
        else if (num == 4)
            list.all();
        
        else if (num == 5)
            break;
        
        cout << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus









반응형

'Tutoring > Data Structure' 카테고리의 다른 글

튜터링 연습문제 1주차  (0) 2018.03.21
hash  (0) 2018.03.04
heap  (0) 2018.03.04
Tree, Binary Tree, Tree traversal  (0) 2018.03.01
Stack, Queue, Deque  (0) 2018.03.01