Download presentation
Presentation is loading. Please wait.
1
쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express
2
동적 메모리 할당에 대한 개념을 이해하고 응용으로 연결 리스트를 학습합니다.
이번 장에서 학습할 내용 동적 메모리 할당에 대한 개념을 이해하고 응용으로 연결 리스트를 학습합니다. 동적 메모리 연결 리스트
3
메모리 할당 방법 정적(static) 자동(automatic) 동적(dynamic) 정적/자동 메모리 할당의 단점
생존 시간(lifetime): 프로그램 시작 프로그램 끝 실행 중에는 메모리가 일정하게 유지되므로 별도의 관리가 불필요함 자동(automatic) 생존 시간: 해당 블록 실행 시작 블록 끝 메모리 할당 및 해제(반납)가 블록과 연동되어 자동으로 이루어짐 실행 시간 스택(runtime stack) 사용 동적(dynamic) 생존 시간: 동적 메모리 할당 동적 메모리 해제 프로그래머가 생존 시간 결정 힙(heap) 사용 정적/자동 메모리 할당의 단점 메모리의 크기가 프로그램 시작 전에 결정되어 고정됨 예: int a[100]; // 배열의 크기에 변수를 사용할 수 없음 결정된 크기보다 더 큰 데이터를 처리할 수 없음 결정된 크기보다 작은 데이터를 처리하면 메모리 낭비 유발
4
동적 메모리 할당 사용자의 요구에 따라 실행 중에 메모리 할당 및 해제 할당 사용 해제
필요한 만큼만 메모리 할당 가능 메모리를 효율적으로 사용 라이브러리 함수 사용: <stdlib.h> 할당: malloc(), calloc() 재할당: realloc() 해제: free()
5
동적 메모리 할당/해제 함수 void *malloc(size_t size); size 바이트만큼 동적 메모리 블록 할당
반환 값: 성공 동적 메모리 블록 시작 포인터, 실패 NULL 할당된 메모리 블록은 초기화되지 않음 void free(void *p); p가 가리키는 동적 메모리 해제 p가 NULL 포인터이면 무시 malloc #include <stdlib.h> int *p; p = (int*)malloc(sizeof(int)); // 할당 if (p == NULL) … // 에러 처리 *p = 123; // 사용 free(p); // 해제 p ? free p 123
6
예제 #include <stdio.h> #include <stdlib.h> int main(void) {
int *score; int i; score = (int*)malloc(10 * sizeof(int)); if (score == NULL) { fprintf(stderr, "동적 메모리 할당 오류\n"); exit(1); } for (i = 0; i < 10; i++) score[i] = i; for (i = 0; i < 10; i++) printf("%d\n", score[i]); free(score); return 0; 1 2 3 4 5 6 7 8 9
7
예제 #include <stdio.h> #include <stdlib.h> int main(void) {
char *pc; int i; if (!(pc = (char*)malloc(26 + 1))) fprintf(stderr, "out of memory\n"), exit(1); for (i = 0; i < 26; i++) pc[i] = 'a' + i; pc[i] = '\0'; puts(pc); free(pc); return 0; } abcdefghijklmnopqrstuvwxyz
8
예제 #include <stdio.h> #include <stdlib.h>
#include <string.h> struct Book { int number; char title[20]; }; int main(void) { struct Book *p; int i; if (!(p = (struct Book *)malloc(2 * sizeof *p))) fprintf(stderr, "메모리 부족\n"), exit(1); p->number = 1; strcpy(p->title, "C Programming"); (p+1)->number = 2; strcpy((p+1)->title, "Data Structure"); for (i = 0; i < 2; i++) printf("%d: %s\n", p[i].number, p[i].title); free(p); return 0; } 1: C Programming 2: Data Structure
9
calloc() void *calloc(size_t n, size_t size);
크기가 size 바이트인 항목 n개를 저장할 수 있는 동적 메모리 할당 ‘size * n’ 바이트 메모리 할당 반환 값: 성공 동적 메모리 블록 시작 포인터, 실패 NULL 할당된 메모리 블록은 0으로 초기화됨 p ? int *p = (int*)malloc(6 * sizeof(int)); // 다음은 모두 24B 할당 p = (int*)calloc(6, sizeof(int)); p = (int*)calloc(sizeof(int), 6); p = (int*)calloc(6 * sizeof(int), 1); p = (int*)calloc(1, 6 * sizeof(int)); p int *p = (int*)calloc(6, sizeof(int));
10
예제 #include <stdio.h> #include <stdlib.h> int main(void) { int *table, size, total, i; size = 5 + rand() % 6; // size: [5, 10] if (!(table = (int*)calloc(size, sizeof(int)))) fprintf(stderr, "out of memory\n"), exit(1); for (i = 0; i < 1000; i++) table[rand() % size]++; for (total = 0, i = 0; i < size; i++) { total += table[i]; printf("%2d: %3d\n", i, table[i]); } printf("\nsize = %d, total = %d\n", size, total); free(table); return 0; } 0: 96 1: 100 2: 103 3: 116 4: 96 5: 109 6: 89 7: 88 8: 109 9: 94 size = 10, total = 1000
11
realloc() void *realloc(void *p, size_t size);
동적 메모리 블록이 다른 위치로 이동될 수 있음 p가 가리키는 이전 메모리 내용은 변경되지 않음 크기가 감소되는 경우에는 감소된 부분만 이전 내용과 동일 증가된 부분은 초기화되지 않음 반환 값: 성공 동적 메모리 블록 시작 포인터, 실패 NULL 성공 반환되는 포인터는 p와 다를 수 있음 실패 p가 가리키는 이전 메모리 내용은 변경되지 않음 p가 NULL이면 malloc()과 동일 q int *q = (int*)realloc(p, 8 * sizeof(int)); 9 2 4 7 5 1 ? p int *p = (int*)malloc(6 * sizeof(int)); 9 2 4 7 5 1 증가 q int *q = (int*)realloc(p, 4 * sizeof(int)); 4 7 5 1 감소
12
realloc() int *p; … if (!(p = (int*)malloc(6 * sizeof(int)))) // 에러 처리
if (!(p = (int*)realloc(p, 8 * sizeof(int)))) // X // free(p) 불가능 (p가 가리키던 이전 메모리를 반환할 수 없음) // 메모리 누수(memory leak) 발생 int *p, *q; … if (!(p = (int*)malloc(6 * sizeof(int)))) // 에러 처리 if (!(q = (int*)realloc(p, 8 * sizeof(int)))) { // O // free(p) 가능 (p가 가리키던 이전 메모리를 반환할 수 있음) } else p = q;
13
예제 #include <stdio.h> #include <stdlib.h> unsigned get_size(void); void job(void *p, unsigned size); int main(void) { unsigned max_size = 0, size, i; void *p = NULL, *q; for (i = 0; i < 5; i++) { if ((size = get_size()) > max_size) { printf("realloc %uKB => ", size); if (!(q = realloc(p, size * 1024))) { puts("failed"); size = max_size; } else { puts("succeeded"); max_size = size; p = q; } } job(p, size); } printf("\nmax size = %uKB\n", max_size); free(p); return 0; } unsigned get_size(void) { return (rand() + 1) * 100; } void job(void *p, unsigned size) { printf("job %p %uKB\n", p, size); // do something } realloc 4200KB => succeeded job 006D KB realloc KB => succeeded job 00AF KB job 00AF KB realloc KB => failed realloc KB => failed max size = KB
14
예제 #include <stdio.h> #include <stdlib.h> int *input(int *p_count); int main(void) { int *list, *p, *end, count, sum; list = input(&count); if (count < 1) { fprintf(stderr, "no data\n"); free(list); exit(1); } p = list; end = p + count; sum = 0; do { sum += *p; } while (++p < end); printf("average = %g\n", (double)sum / count); free(list); return 0; } int *input(int *p_count) { enum { INCR_SIZE = 100 }; int *list = NULL, *p, size = 0, count = 0, score; while (scanf("%d", &score) == 1) { if (size <= count) { size += INCR_SIZE; if (!(p = realloc(list, size * sizeof(int)))) { fprintf(stderr, "out of memory\n"); free(list); exit(1); } list = p; } list[count++] = score; } *p_count = count; return list; } ^Z average = 45
15
연결 리스트 배열(array) 연결 리스트(linked list) 간단하고 다루기 쉬움 특정 위치의 원소에 대한 접근이 빠름
삽입/삭제가 비효율적 연결 리스트(linked list) 각 원소가 포인터를 사용하여 다음 원소를 가리킴 다루기 어렵고 특정 위치의 원소에 대한 접근이 느림 삽입/삭제가 용이함 삽입 B A C D E N 삭제 B A C D E
16
연결 리스트 노드(node) = 데이터 필드(data field) + 링크 필드(link field)
일반적으로 동적 메모리를 사용하여 생성 헤드 포인터(head pointer): 첫 번째 노드를 가리키는 포인터 자기 참조 구조체(self-referential structure): 멤버 중에 자신과 같은 타입의 구조체를 가리키는 포인터가 있는 구조체 struct node { int data; struct node *link; };
17
기본적인 연결 리스트 조작 NODE *p1; p1 = (NODE*)malloc(sizeof(NODE));
p1->data = 10; p1->link = NULL; NODE *p2; p2 = (NODE*)malloc(sizeof(NODE)); p2->data = 20; p2->link = NULL; p1->link = p2; free(p1); free(p2); 20 p2
18
예제: 책 리스트 #include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 50 typedef struct NODE { char title[SIZE]; int year; struct NODE *link; } NODE; int main(void) { NODE *list = NULL, *prev, *p, *next; char buffer[SIZE]; while (1) { printf("책 제목: "); if (!gets(buffer)) break; p = (NODE*)malloc(sizeof(NODE)); strcpy(p->title, buffer); printf("책 출판 연도: "); gets(buffer); p->year = atoi(buffer); if (list == NULL) list = p; else prev->link = p; p->link = NULL; prev = p; } putchar('\n'); for (p = list; p != NULL; p = p->link) printf("%s, %d\n", p->title, p->year); for (p = list; p != NULL; p = next) next = p->link, free(p); return 0; } 책 제목: 컴퓨터 개론 책 출판 연도: 2006 책 제목: C 언어 책 출판 연도: 2007 책 제목: ^Z 컴퓨터 개론, 2006 C 언어, 2007
19
예제: 학생 리스트 list.h list.c #ifndef _LIST_H_ #define _LIST_H_ #define NAME_SIZE 20 typedef struct student_node { int id; char name[NAME_SIZE+1]; double gpa; struct student_node *next; } SNODE; SNODE *make_list(void); void free_list(SNODE *p); void out_list(const SNODE *p); // double get_average(const SNODE *p); #endif #include <stdio.h> #include <stdlib.h> #include "list.h" SNODE *make_list(void) { SNODE node, *p, *head = NULL; while (1) { printf("ID NAME GPA: "); if (scanf("%d %s %lf", &node.id, node.name, &node.gpa) != 3) break; if (!(p = (SNODE*)malloc(sizeof *p))) fprintf(stderr, "out of memory\n"), exit(1); *p = node; p->next = head; head = p; // reversed } return head; } void free_list(SNODE *p) { SNODE *q; for (; p; p = q) { q = p->next; free(p); } } void out_list(const SNODE *p) { for (; p; p = p->next) printf("%d %s %g\n", p->id, p->name, p->gpa); } // double get_average(const SNODE *p) { ... }
20
예제: 학생 리스트 (계속) #include "list.h" int main() { SNODE *list; list = make_list(); putchar('\n'); out_list(list); // printf("average = %g\n", get_average(list)); free_list(list); return 0; } ID NAME GPA: 강감찬 4.1 ID NAME GPA: 김유신 4.2 ID NAME GPA: 이순신 4.3 ID NAME GPA: ^Z 이순신 4.3 김유신 4.2 강감찬 4.1
Similar presentations
