programming/data-structures

[DAY 04] Doubly Linked List





(오후)


링크가 잘 걸려있는지 항상 체크하여야 한다.


삽입, 삭제가 빈번할 때는 절대로 배열을 쓰지 않는다.


더블 링크 리스트 장점

검색 효율이 좋다

유지 보수성이 좋다


linked list는 검색 알고리즘이다.






------

답 주석

while(pos>count || pos<0)

count가 끝의 위치를 알고 있고 0은 시작 위치이다

앞뒤를 다 알고 시작하는거야




삽입 알고리즘

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
/*
    The merits in Doubly Linked List
    1. 검색 효율이 뛰어나다.
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> 
 
typedef struct Node
{
    int          data;
    struct Node *next;    // 뒷 노드를 가리키는 포인터
    struct Node *prev;    // 앞 노드를 가리키는 포인터
} Node;
 
void Insert(Node *root);
void Display(Node *root);
 
void main(void)
{
    int num;
    char sayYesOrNo;
 
    Node *root = (Node *)malloc(sizeof(Node));
    root->next = NULL;
    root->prev = NULL;
 
    do {
        puts("========== MENU ==========");
        puts("1. 추가");
        puts("2. 출력");
        puts("==========================");
        printf("뭐 할래? : ");
        scanf("%d"&num);
 
        switch (num)
        {
        case 1:    // 입력
            Insert(root);
            break;
        case 2:    // 출력
            Display(root);
            break;
        }
 
        printf("계속하시겠습니까?(Y/N) : ");
        rewind(stdin);
        scanf("%c"&sayYesOrNo);
    } while (sayYesOrNo == 'Y' || sayYesOrNo == 'y');
 
}
 
void Insert(Node *root)
{
    Node *cur;
    Node *new1;
    int pos = 0;
    int cnt = 0;
 
    // 탐색
    cur = root;
    while (cur->next != NULL) {
        cur = cur->next;
        cnt++;
    }
 
    // 크기 예외처리 필수
    while (pos < || cnt + < pos) {
        printf("몇 번째 삽입? : ");
        scanf("%d"&pos);
    }
    
    // 노드 삽입
    new1 = (Node *)calloc(1sizeof(Node));
 
    cur = root;
    // 탐색
    while (--pos) {
        if (cur->next == NULL || cur == NULL)    // 실패
            break;
        else
            cur = cur->next;    // 다음으로
    }
 
    // 순방향 연결
    new1->next = cur->next;        // NULL
    
    cur->next = new1;
 
    // 역방향 연결
    if (new1->next != NULL) {
        new1->next->prev = new1;
    }
    new1->prev = cur;
    
    // 데이터 입력
    printf("Input Data : ");
    scanf("%d"&(new1->data));
}
 
void Display(Node *root)    // 순방향, 역방향 전체출력할 것
{
    Node *cur;
 
    // 순방향 출력
    puts("순방향 출력");
    cur = root;
    while (cur != NULL) {
        if (cur->next == NULL)
            break;
 
        cur = cur->next;
        printf("%d \t", cur->data);
    }
    puts("");
 
    // 역방향 출력
    puts("역방향 출력");
    while (cur != NULL) {
        if (cur->prev == NULL)
            break;
        printf("%d \t", cur->data);
        cur = cur->prev;
    }
}
cs


삭제 알고리즘은 숙제


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
/*
    The merits in Doubly Linked List
    1. 검색 효율이 뛰어나다.
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> 
 
typedef struct Node
{
    int          data;
    struct Node *next;    // 뒷 노드를 가리키는 포인터
    struct Node *prev;    // 앞 노드를 가리키는 포인터
} Node;
 
void Insert(Node *root);
void Delete(Node *root);
void Display(Node *root);
 
void main(void)
{
    int num;
    char sayYesOrNo;
 
    Node *root = (Node *)malloc(sizeof(Node));
    root->next = NULL;
    root->prev = NULL;
 
    do {
        puts("========== MENU ==========");
        puts("1. 추가");
        puts("2. 삭제");
        puts("3. 출력");
        puts("==========================");
        printf("뭐 할래? : ");
        scanf("%d"&num);
 
        switch (num)
        {
        case 1:    // 입력
            Insert(root);
            break;
        case 2:    // 삭제
            Delete(root);
            break;
        case 3:    // 출력
            Display(root);
            break;
        }
 
        printf("계속하시겠습니까?(Y/N) : ");
        rewind(stdin);
        scanf("%c"&sayYesOrNo);
    } while (sayYesOrNo == 'Y' || sayYesOrNo == 'y');
 
}
 
void Insert(Node *root)
{
    Node *cur;
    Node *new1;
    int pos = 0;
    int cnt = 0;
 
    // 탐색
    cur = root;
    while (cur->next != NULL) {
        cur = cur->next;
        cnt++;
    }
 
    // 크기 예외처리 필수
    while (pos < || cnt + < pos) {
        printf("몇 번째 삽입? : ");
        scanf("%d"&pos);
    }
    
    // 노드 삽입
    new1 = (Node *)calloc(1sizeof(Node));
 
    cur = root;
    // 탐색
    while (--pos) {
        if (cur->next == NULL || cur == NULL)    // 실패
            break;
        else
            cur = cur->next;    // 다음으로
    }
 
    // 순방향 연결
    new1->next = cur->next;        // NULL
    
    cur->next = new1;
 
    // 역방향 연결
    if (new1->next != NULL) {
        new1->next->prev = new1;
    }
    new1->prev = cur;
    
    // 데이터 입력
    printf("Input Data : ");
    scanf("%d"&(new1->data));
}
 
void Delete(Node *root)
{
    Node *cur, *del, *find;
    int pos = 0;
    int cnt = 0;
 
    cur = del = find = NULL;
 
    // 탐색
    cur = root;
    while (cur->next != NULL) {
        cur = cur->next;
        cnt++;
    }
 
    // 크기 예외처리 필수
    while (pos < || cnt < pos) {
        printf("몇 번째 삭제? : ");
        scanf("%d"&pos);
    }
 
    // 탐색
    cur = root;    
    while (--pos) {
        if (cur->next == NULL || cur == NULL)    // 실패
            break;
        else
            cur = cur->next;    // 다음으로
    }
 
    // 포인터 연결
    del = cur->next;
    find = del->next;
 
    if (del->next == NULL) {
        cur->next = NULL;
        del->prev = NULL;
    } else {
    cur->next = find;
    del->next = NULL;
 
    // 역방향 연결
    find->prev = del->prev;
    del->prev = NULL;
    }
 
    free(del);
}
 
void Display(Node *root)    // 순방향, 역방향 전체출력할 것
{
    Node *cur;
 
    // 순방향 출력
    puts("순방향 출력");
    cur = root;
    while (cur != NULL) {
        if (cur->next == NULL)
            break;
 
        cur = cur->next;
        printf("%d \t", cur->data);
    }
    puts("");
 
    // 역방향 출력
    puts("역방향 출력");
    while (cur != NULL) {
        if (cur->prev == NULL)
            break;
        printf("%d \t", cur->data);
        cur = cur->prev;
    }
    puts("");
}
cs