×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,720,221명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형



[ 구조체(C) 및 클래스(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
#include <stdio.h>
#include <malloc.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
 
typedef struct Node
{
    int data;
    Node *next;
}node;
 
int main()
{
    node *head = NULL// 이것은 구조체를 만든 것이 아닌 node 구조체를 가리킬 수 있는 포인터를 만든 것이다.
    node *tail = NULL// node node1; 과는 다르다.
    node *cur = NULL;
    node *newnode = NULL;
    node *delnode;
    node *delnextnode;
 
    int value;
 
    printf("예외 : 0 입력시 연결 리스트 모든 값이 출력됩니다.\n");
    printf("예외 : -1 입력시 연결 리스트 모든 값이 출력됩니다.\n\n");
 
    while (1)
    {
        printf("자연수를 입력해 주세요 : ");
        
        scanf("%d", &value);
 
        // 연결 리스트 값 출력 ( value == 0 ) 
        if (value == 0)
        {
            if (head == NULL)
            {
                printf("연결 리스트에 값이 존재하지 않습니다.\n");
                continue;
            }
 
            else
            {
                
                cur = head;
                printf("%d ", cur->data);
                while (cur->next != NULL// tail->next는 NULL이다.
                {
                    cur = cur->next;
                    printf("%d ", cur->data);
                }  printf("\n");
            }
        }
 
 
        // 연결 리스트 삭제 과정 ( value == -1 ) 
        else if (value == -1)
        {
            if (head == NULL)
            {
                printf("삭제할 노드가 없습니다.\n");
                continue;
            }
 
            else
            {
                delnode = head;
                delnextnode = head->next;
 
                printf("%d를 삭제합니다.\n", delnode->data); 
                free(delnode);
 
                while (delnextnode != NULL)
                {
                    delnode = delnextnode; // delnode는 그다음 노드를 가리키게된다.
                    delnextnode = delnextnode->next; // delnextnode는 delnode 다음 노드를 가리킨다.
                    
                    printf("%d를 삭제합니다.\n", delnode->data);
                    free(delnode);
                }
                // 모든 노드를 삭제하면서 free(delnode);를 시행했으니 결국 head가 가리키던 node 및 tail이 가리키던 node가 다 메모리 헤제가 되면서
                // head와 tail이 쓰레기 값을 보고 있게된다. 그것을 방지해주기 위해 모두 NULL로 초기화 한다.
                head = NULL;
                tail = NULL;
                cur = NULL;
            }
 
        }
 
 
        else if (value < 1// 예외처리는 모든 코딩에서 아주 중요하다.
        {
            printf("다시 입력해 주세요.\n");
            continue;
        }
 
 
        else
        {
            // 노드의 추가 과정
            newnode = (node*)malloc(sizeof(node));
            newnode->data = value; // 새로 생긴 node에 data를 넣는다.
            newnode->next = NULL// 새로 생긴 node의 next 포인터는 NULL을 가리키도록 한다. 
            if (head == NULL)
                head = newnode; // 만약 head가 아무것도 가리키지 않고있다면 newnode를 가리키게 한다.
            else
                tail->next = newnode; // 그렇지 않다면 tail의 next 즉, tail은 node를 가리키니 node의 next가 newnode를 가리키게 한다.
        
            tail = newnode;
        }
 
    }
 
 
    return 0;
}
 
Crocus










[ 클래스를 통한 표현 ]


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
#include <iostream>
 
using namespace std;
 
class node
{
 
private:
    int data;
    node *next;
 
public:
    void inputData(int value)
    {
        data = value;
    }
 
    void init()
    {
        next = NULL;
    }
 
    // next라함은 a -> next(b)에서 a의 next를 의미한다.
    void doNext(node *newnode)
    {
        next = newnode;
    }
    
    // 연결 리스트에 연결된 노드들을 삭제하는 과정
    void doDelete(node *delnode, node *delnextnode)
    {
        node *tmp = delnode;
 
        delnextnode = tmp->next;
 
        cout << tmp->data<< "를 삭제합니다." << endl;
 
        delete tmp;
 
        while (delnextnode != NULL)
        {
            tmp = delnextnode; // delnode는 그다음 노드를 가리키게된다.
            delnextnode = tmp->next;
            cout << tmp->data<< "를 삭제합니다." << endl;
            delete tmp;
        }
 
    }
 
    // 그 포인터가 가지는 데이터를 가져온다.
    int getData()
    {
        return data;
    }
 
    // 전체 노드를 보기 위한 함수
    void see(node *head, node *cur) 
    {
        cur = head;
        
        cout << cur->data << " ";
            while (cur->next != NULL// tail->next는 NULL이다.
            {
                cur = cur->next;
                cout << cur->data << " ";
            }
            cout << endl;
    }
};
 
int main()
{
    node *head = NULL// 이것은 구조체를 만든 것이 아닌 node 구조체를 가리킬 수 있는 포인터를 만든 것이다.
    node *tail = NULL// node node1; 과는 다르다.
    node *cur = NULL;
    node *newnode = NULL;
 
    int value;
 
    cout << "예외 : 0 입력시 연결 리스트 모든 값이 출력됩니다." << endl;
    cout << "예외 : -1 입력시 연결 리스트 모든 값이 출력됩니다.\n" << endl;
 
    while (1)
    {
        cout << "자연수를 입력해 주세요 : " ;
        cin >> value;
 
        // 연결 리스트 값 출력 ( value == 0 )
        if (value == 0)
        {
                if (head == NULL)
                {
                    cout << "연결 리스트에 값이 존재하지 않습니다." << endl;
                    continue;
                }
 
                else
                {
                    cur->see(head,cur);
                }
        }
 
 
 
        // 연결 리스트 삭제 과정 ( value == -1 )
        else if (value == -1)
        {
            if (head == NULL)
            {
                printf("삭제할 노드가 없습니다.\n");
                continue;
            }
 
            else
            {
                node *delnode = head;
                node *delnextnode = NULL;
 
                delnode->doDelete(delnode, delnextnode);
                                
                // 모든 노드를 삭제하면서 free(delnode);를 시행했으니 결국 head가 가리키던 node 및 tail이 가리키던 node가 다 메모리 헤제가 되면서
                // head와 tail이 쓰레기 값을 보고 있게된다. 그것을 방지해주기 위해 모두 NULL로 초기화 한다.
                head = NULL;
                tail = NULL;
                cur = NULL;
            }
        }
 
        else if (value < 1// 예외처리는 모든 코딩에서 아주 중요하다.
        {
            cout << "다시 입력해 주세요."<< endl;
 
            continue;
        }
 
        else
        {
            // 노드의 추가 과정
            newnode = new node; // node의 크기만큼 newnode에 공간을 할당해 준다.
            newnode->inputData(value);  // 새로 생긴 node에 data를 넣는다.
            newnode->init();  // 새로 생긴 node의 next 포인터는 NULL을 가리키도록 한다. 
 
            if (head == NULL)
                head = newnode; // 만약 head가 아무것도 가리키지 않고있다면 newnode를 가리키게 한다.
            else
                tail->doNext(newnode); // 그렇지 않다면 tail의 next 즉, tail은 node를 가리키니 node의 next가 newnode를 가리키게 한다.
        
            tail = newnode;
        }
        
    }
    return 0;
}
 
 
Crocus















값 출력 과정에서 알고리즘


만약 head가 NULL을 가리킨다면?? 아무것도 없다는 뜻이니 값이 없다는 상태를 출력한다.


그게 아니라면 cur은 head가 가리키는 주소를 가리킨다. 


즉, 연결 리스트의 가장 첫 부분을 가리키게 된다.


그다음 그 값을 cur->data(즉, cur이 가리키는 노드의 data 값)을 출력하고


while문의 조건을 확인한다. while문의 조건은 cur이 가리키는 노드의 next가 가리키는 것이 NULL이 아니라면


cur = cur->next;를 취한다.


이것의 의미는 cur이라는 포인터는 (cur = ) cur이 가리키는 노드의 next가 가리키는 주소를 가리켜라 (cur = cur->next;)라는 뜻이다.


그리고 그다음 값을 또 출력하며 조건이 맞지 않을 때 까지 반복한다.







값 삭제 과정에서의 알고리즘


출력과정과 동일한 알고리즘이고 그림을 보고 한번 어떠한 알고리즘으로 돌아가는지 생각해봤으면 한다.



그리고 [ 구조체를 통한 표현 ]부분에서 노드 삭제 과정의 


head = NULL, tail = NULL, cur = NULL;의 의미를 한번 생각 해보는 시간을 가졌으면 좋겠다.



반응형