노드 구조체
1 2 3 4 5 | typedef struct _node { int data; struct _node* next; } Node; | cs |
리스트 구조체
1 2 3 4 5 | typedef struct _list { Node* head; int size; } List; | cs |
List* create_list() : 리스트를 만들고 주소를 리턴
1 2 3 4 5 6 7 8 | List* create_list() { List* new_list = (List*)malloc(sizeof(List)); new_list->head = NULL; new_list->size = 0; return new_list; } | cs |
Node* create_node(int data) : 노드를 만들고 주소를 리턴
1 2 3 4 5 6 7 8 | Node* create_node(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = NULL; return new_node; } | cs |
bool list_empty(List* L) : 리스트의 size가 0이면 1을 리턴 아니면 0을 리턴
1 2 3 4 5 | bool list_empty(List* L) { if(L->size) return 0; else return 1; } | cs |
void push_back(List* L, int data) : 리스트의 맨 뒤에 데이터 삽입
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void push_back(List* L, int data) { Node* new_node = create_node(data); Node* tmp = L->head; if(list_empty(L)) L->head = new_node; else { while(tmp->next) tmp = tmp->next; tmp->next = new_node; } L->size++; } | cs |
void node_insert(List* L, int idx, int data) : idx가 범위를 리스트 사이즈보다 크거나 같으면 push_back호출 아니면 해당 idx에 삽입
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | void node_insert(List* L, int idx, int data) { if(idx >= L->size) push_back(L, data); else { Node* new_node = create_node(data); if(idx == 0) { new_node->next = L->head; L->head = new_node; } else { Node* tmp = L->head; for(int i = 0; i < idx - 1; i++) tmp = tmp->next; new_node->next = tmp->next; tmp->next = new_node; } L->size++; } } | cs |
void node_delete(List* L, int idx) : idx가 범위를 벗어나면 맨 뒤를 삭제 아니면 해당 idx 노드 삭제
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 | void node_delete(List* L, int idx) { if(!list_empty(L)) { Node* tmp = L->head; if(idx == 0) { L->head = tmp->next; free(tmp); } else if(idx >= L->size - 1) { Node* before = NULL; while(tmp->next) { before = tmp; tmp = tmp->next; } free(tmp); if(before != NULL) before->next = NULL; else L->head = NULL; } else { Node* before = NULL; for(int i = 0; i < idx; i++) { before = tmp; tmp = tmp->next; } before->next = tmp->next; free(tmp); } L->size--; } } | cs |
void list_print(List* L) : 리스트 데이터 전부 출력
1 2 3 4 5 6 7 8 9 10 11 | void list_print(List* L) { Node *tmp = L->head; while(tmp) { printf("%d ", tmp->data); tmp = tmp->next; } puts(""); } | cs |
아래는 풀 코드 및 예제입니다.
실행 환경 cpp
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 | #include <cstdio> #include <cstdlib> typedef struct _node { int data; struct _node* next; } Node; typedef struct _list { Node* head; int size; } List; List* create_list() { List* new_list = (List*)malloc(sizeof(List)); new_list->head = NULL; new_list->size = 0; return new_list; } Node* create_node(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->next = NULL; return new_node; } bool list_empty(List* L) { if(L->size) return 0; else return 1; } void push_back(List* L, int data) { Node* new_node = create_node(data); Node* tmp = L->head; if(list_empty(L)) L->head = new_node; else { while(tmp->next) tmp = tmp->next; tmp->next = new_node; } L->size++; } void node_insert(List* L, int idx, int data) { if(idx >= L->size) push_back(L, data); else { Node* new_node = create_node(data); if(idx == 0) { new_node->next = L->head; L->head = new_node; } else { Node* tmp = L->head; for(int i = 0; i < idx - 1; i++) tmp = tmp->next; new_node->next = tmp->next; tmp->next = new_node; } L->size++; } } void node_delete(List* L, int idx) { if(!list_empty(L)) { Node* tmp = L->head; if(idx == 0) { L->head = tmp->next; free(tmp); } else if(idx >= L->size - 1) { Node* before = NULL; while(tmp->next) { before = tmp; tmp = tmp->next; } free(tmp); if(before != NULL) before->next = NULL; else L->head = NULL; } else { Node* before = NULL; for(int i = 0; i < idx; i++) { before = tmp; tmp = tmp->next; } before->next = tmp->next; free(tmp); } L->size--; } } void list_print(List* L) { Node *tmp = L->head; while(tmp) { printf("%d ", tmp->data); tmp = tmp->next; } puts(""); } int main() { List* new_list = create_list(); for(int i = 0; i < 10; i++) push_back(new_list, i); for(int i = 0; i < 10; i++){ node_delete(new_list, i); list_print(new_list); printf("size = %d\n", new_list->size); } return 0; } | cs |
'CS기본지식 > 자료구조' 카테고리의 다른 글
| [C언어] 우선순위 큐(Priority Queue) (3) | 2017.09.07 |
|---|---|
| [2263] 트리의 순회 (1) | 2017.08.27 |
| 스택 계산기 (0) | 2017.06.13 |
| [1918] 후위표기식 (2) | 2017.06.13 |
| 이중 연결 리스트 (0) | 2017.04.22 |