![[DAY 03] Singly Linked List 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F995476465A6A8E0A30)
반응형
Linked List의 종류
1. Single Linked List
2. Double Linked List
3. Single 환형 Linked List
4. Double 환형 Linked List (실무에서 많이 씀)
2. 삭제
삭제는
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 | #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct card // 자기 참조 구조체 { char name[10]; int age; struct card *next; // 다음 노드를 가리키는 용도 } CARD; void main() { CARD *head, *cur, *new1, *del; int pos = 0, findPos = 0; char findName[10]; int i; head = cur = new1 = del = NULL; // 첫 번째 노드 생성 및 데이터 입력 if ((head = new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } printf("Input name, age : "); scanf("%s %d", new1->name, &new1->age); new1->next = NULL; // 두 번째 노드 생성 및 데이터 입력 if ((new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } printf("Input name, age : "); scanf("%s %d", new1->name, &new1->age); new1->next = NULL; // 첫 번째 노드와 두 번째 노드를 연결하기 위해 cur = head; // cursor pointer로 마지막 노드를 잡는다. while (cur->next != NULL) { cur = cur->next; // 다음 노드를 이동 } new1->next = cur->next; // step 1. 뒷부분부터 연결 cur->next = new1; // step 2. 앞부분 연결 if ((new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } printf("Input name, age : "); scanf("%s %d", new1->name, &new1->age); new1->next = NULL; // Search cur = head; while (cur->next != NULL) { cur = cur->next; // 다음 노드를 이동 } new1->next = cur->next; cur->next = new1; // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->age); cur = cur->next; pos++; } // 원하는 위치 입력 while (findPos < 1 || (pos + 1) < findPos) { printf("(1 ~ %d)의 값을 입력하세요 : ", pos + 1); scanf("%d", &findPos); } // 노드 생성 if ((new1 = (CARD *)calloc(1, sizeof(CARD))) == NULL) { puts("failed to memory allocation!"); exit(-1); } printf("Input name, age : "); scanf("%s %d", new1->name, &new1->age); new1->next = NULL; // 삽입 전 노드 검색 cur = head; for (i = 0; i < findPos - 2; i++) { cur = cur->next; } /* while (pos + 1 > 2) { cur = cur->next; pos--; } */ // 노드 삽입 if (findPos == 1) { new1->next = head; head = new1; } else { new1->next = cur->next; cur->next = new1; } // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->age); cur = cur->next; pos++; } // 삭제하고자 하는 이름 입력 printf("삭제하고 싶은 이름을 입력하세요 : "); scanf("%s", findName); cur = head; // 삭제하고자 하는 노드가 첫 번째일 경우 if (strcmp(findName, cur->name) == 0) { del = cur; head = head->next; del->next = NULL; free(del); puts("삭제가 완료되었습니다!"); } else { // 탐색 while (strcmp(findName, cur->next->name)) { cur = cur->next; // 탐색 실패 if (cur->next == NULL) { puts("찾고자 하는 이름이 없습니다!"); exit(-1); } } del = cur->next; cur->next = del->next; free(del); puts("삭제가 완료되었습니다!"); } // 전체 출력 cur = head; while (cur != NULL) { printf("%s\t%d \n", cur->name, cur->age); cur = cur->next; pos++; } } | cs |
헤드 포인터가 움직이기 때문에 case를 나눈 것이다.
더미 노드를 만들게 되면 그런 경우가 없다
삭제 전 노드를 찾아서 (알고리즘)
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 181 182 | #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; }Node; int Insert(struct Node*cur, int position); int Delete(struct Node*cur, int position); int SetData(struct Node*cur, int position, int data); int GetData(struct Node*cur, int position, int* data); void Printouts(Node *cur); #define ASSERT(exp) if(!(exp)) { puts("Err\n"); } void main(void) { Node* root = (Node*)malloc(sizeof(Node)); root->next = NULL; int r, n; int i; // 0번위치에 10개 삽입 for (i = 0; i < 10; i++) { r = Insert(root, 0); ASSERT(r); r = SetData(root, 0, i + 1); ASSERT(r); } // 삽입확인 for (i = 0; i < 10; i++) { r = GetData(root, i, &n); ASSERT(r); ASSERT(n == 10 - i); } Printouts(root); //모두삭제 for (i = 0; i < 10; i++) { r = Delete(root, 0); ASSERT(r); } Printouts(root); //마지막위치에 10개삽입 for (i = 0; i < 10; i++) { r = Insert(root, i); ASSERT(r); r = SetData(root, i, i + 1); ASSERT(r); } Printouts(root); //짝수번째모두삭제 for (int i = 10 - 1; i >= 0; i -= 2) { r = Delete(root, i); ASSERT(r); } Printouts(root); //짝수번째다시삽입 for (int i = 1; i < 10; i += 2) { r = Insert(root, i); ASSERT(r); r = SetData(root, i, i + 1); ASSERT(r); } Printouts(root); //복원확인 for (int i = 0; i < 10; i++) { r = GetData(root, i, &n); ASSERT(r); ASSERT(n == i + 1); } Printouts(root); //에러확인(예외처리가 제대로 되었는 지 확인) for (int i = 10; i < 20; i++) { r = GetData(root, i, &n); ASSERT(!r); } Printouts(root); //역순으로삭제 for (int i = 10 - 1; i >= 0; i--) { r = Delete(root, i); ASSERT(r); } Printouts(root); ASSERT(root->next == NULL); delete root; root = NULL; //좋은습관 } int Insert(Node *cur, int position) { Node *new1; int i; new1 = NULL; // 0번 위치에 삽입 new1 = (Node *)malloc(sizeof(Node)); new1->next = NULL; // 현재 몇 개의 노드가 있는지 탐색 for (i = 0; i < position; i++) { if (cur->next == NULL) return 0; cur = cur->next; } new1->next = cur->next; // step 1. 뒷부분부터 연결 cur->next = new1; // step 2. 앞부분 연결 return 1; } int Delete(Node*cur, int position) { Node *del; int i; // 현재 몇 개의 노드가 있는지 탐색 for (i = 0; i < position; i++) { if (cur->next == NULL) return 0; cur = cur->next; } del = cur->next; cur->next = del->next; del->next = NULL; free(del); return 1; } int SetData(struct Node *cur, int position, int data) { int i; for (i = 0; i < position; i++) { if (cur->next == NULL) return 0; cur = cur->next; } cur->next->data = data; return 1; } int GetData(Node *cur, int position, int *data) { do { if (cur->next == NULL || cur == NULL) // 실패 return 0; else cur = cur->next; // 다음으로 } while (position--); // 루프를 다 돌고 나면 position = -1 이 되어 있고, // cur 목표 node가 되어 있다. *data = cur->data; return 1; } void Printouts(Node *cur) { puts("DATA\t"); while (cur->next != NULL) { printf("%d\t", cur->next->data); cur = cur->next; } puts(""); } | cs |
사실 이거 day 04 에 한거임
반응형