반응형
(오후)
링크가 잘 걸려있는지 항상 체크하여야 한다.
삽입, 삭제가 빈번할 때는 절대로 배열을 쓰지 않는다.
더블 링크 리스트 장점
검색 효율이 좋다
유지 보수성이 좋다
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 < 1 || cnt + 1 < pos) { printf("몇 번째 삽입? : "); scanf("%d", &pos); } // 노드 삽입 new1 = (Node *)calloc(1, sizeof(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 < 1 || cnt + 1 < pos) { printf("몇 번째 삽입? : "); scanf("%d", &pos); } // 노드 삽입 new1 = (Node *)calloc(1, sizeof(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 < 1 || 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 |
반응형