×
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원(알고리즘 학습러)
반응형
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
 
#pragma once
#include <iostream>
 
using namespace std;
 
typedef int DATA;
 
class Node
{
    friend class List; 
private:
    DATA data; 
    Node *next; 
 
};
 
class List
{
    friend class Node;
private:
    Node *tail;
 
    int numOfData;
 
public:
    void ListInit(List *plist)
    {
        plist->tail = NULL;
        plist->numOfData = 0;
    }
 
    void LInsert(List *plist, DATA data)
    {
        Node *newNode = new Node;
        newNode->data = data;
 
        if (plist->tail == NULL)
        {
            plist->tail = newNode;
            newNode->next = newNode;
        }
 
        else
        {
            newNode->next = plist->tail->next; // 이 세 과정이 tail을 유지시키고, 원형 연결 리스트로 만든다.
            plist->tail->next = newNode;
            plist->tail = newNode;
        
            Node *tmp = plist->tail->next; // 처음을 의미
            Node *tmp_1 = plist->tail->next->next; // 그 다음을 의미
            
            int val = tmp->data; // 그것의 데이터
            int val_1 = tmp_1->data;
            for (int i = 0; i < plist->numOfData; i++)
            {
                for (int j = i; j < plist->numOfData; j++)
                {
                    if (val > val_1)
                    {
                        int temp = val;
                        tmp->data = val_1;
                        tmp_1->data = temp;
 
                        tmp_1 = tmp_1->next;
                        val_1 = tmp_1->data;
                    }
                    else
                    {
                        tmp_1 = tmp_1->next;
                        val_1 = tmp_1->data;
                    }
                }
                tmp = tmp->next;
                val = tmp->data;
                tmp_1 = tmp->next;
                val_1 = tmp_1->data;
            }
 
            
        }
 
 
        (plist->numOfData)++;
    }
 
    DATA LRemove(List *plist)
    {
        if (plist->numOfData == 0)
            return 0;
 
            Node *rpos = plist->tail->next;
            DATA result = plist->tail->data;
            Node *arr = plist->tail->next; // 처음을 보도록
 
            
            while(1)
            {
                if (plist->tail == arr->next) // 끝과 처음의 다음(즉, 끝)이 같을 경우
                {
                    break;
                }
 
                else
                    arr = arr->next;
            }
 
            delete plist->tail;
            plist->tail = arr;
            plist->tail->next = rpos;
 
            (plist->numOfData)--;
            
            return result;
    }
 
    int LCount(List *plist)
    {
        cout << "현재 개수 : " << plist->numOfData << endl;
 
        if (plist->numOfData == 0return 0;
 
        cout << "처음 ::  " << plist->tail->next->data << endl;
        cout << "끝 :: " << plist->tail->data << endl;
 
        Node *arr = plist->tail->next;
        for (; plist->tail != arr;)
        {
            cout << arr->data <<" ";
            arr = arr->next;
        }
 
        // for문에서 출력 되지 못하는 마지막 값 출력
        cout << arr->data << endl
        return 1;
    }
};
Crocus





앞의 연결 리스트를 이해했다면 원형 연결 리스트 또한 tail->next == NULL이 아니라는 점만 제외하면 대부분이 같다는 것을 느낄 수 있다.


구조체로 변형 시키는 것은 클래스 함수를 다 밖으로 빼고, 변수를 struct로 변형 시킨 후 약간의 부분만 수정하면 된다.



[ 주의 할 코드 구간 ]


이 코드는 삽입을 하는 순간 오름차순 순으로 정렬을 하는 코드이므로 오름차순을 원치 않는다면


위 코드에서 아래 코드 부분을 제거하면 된다.


하지만 이 코드를 분석해보고 포인터의 선택정렬은 일반 변수 선택정렬과 다르다는 것을


 한번 짚고 넘어갈 수 있으면 아주 좋은 경험이 될 것이다.

 


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 val = tmp->data; // 그것의 데이터
int val_1 = tmp_1->data;
for (int i = 0; i < plist->numOfData; i++)
{
    for (int j = i; j < plist->numOfData; j++)
    {
        if (val > val_1)
        {
            int temp = val;
            tmp->data = val_1;
            tmp_1->data = temp;
 
            tmp_1 = tmp_1->next;
            val_1 = tmp_1->data;
        }
        
        else
        {
            tmp_1 = tmp_1->next;
            val_1 = tmp_1->data;
        }
    }
 
    tmp = tmp->next;
    val = tmp->data;
    tmp_1 = tmp->next;
    val_1 = tmp_1->data;
}
Crocus






이 코드에 대한 알고리즘


Node 클래스와 List 클래스를 형성 후 List list;를 선언하여 하나의 list 클래스를 생성한다. 


그리고 list의 tail 포인터와 numOfData를 이용하여 리스트의 위치를 파악하고, 리스트의 개수를 조사한다.


생성자를 이용하지 않고, ListInit를 이용하여 처음 list 클래스를 초기화 시켜주고, 


LInsert를 통해 Node 클래스를 new를 통해 공간을 할당 해주고 그 노드끼리 연결한다.


 tail은 list의 끝을 가리키도록 한다.


그리고 원형으로 만들어주는데 이때 원형이라 함은 plist->tail = newNode; newNode->next = newNode;를 통해 형성한다.


첫 원형의 시작은 아래의 코드에서부터 시작된다.



1
2
3
4
5
if (plist->tail == NULL)
{
    plist->tail = newNode;
    newNode->next = newNode;
}
Crocus



이 코드를 보면 tail이 NULL일때 tail은 newNode를 가리키게 되는데, 


그다음 newNode의 next도 newNode를 가리키게 된다.





그 뒤로 계속 노드를 형성하면 꼬리부분에 newnode를 만들어주면서 tail을 계속 newnode를 가리키게 하고, 원형 연결 리스트를 만들어준다.


// 이 세 과정이 tail을 유지시키고, 원형 연결 리스트로 만든다.


newNode->next = plist->tail->next; 


 plist->tail->next = newNode; 


plist->tail = newNode;


그리고 insert를 할 때마다 포인터를 통해 data를 비교하여 서로의 포인터를 바꾸는 것이 아닌 포인터 속 값만 바꾸는 행위를 취한다.


제거 코드는 rpos, arr 포인터 및 result int형 변수를 이용하여 포인터를 이동시키며 연결리스트에서 빠지는 노드는 메모리 해제를 시킨다.


출력 코드는 numOfData를 이용하여 for(int i = 0 ; i < numOfData; i++)를 이용하여도 되지만


리스트인 만큼 포인터를 이용하여 리스트를 출력하는 알고리즘이다.








반응형