쉽게 풀어쓴 C언어 Express 제17장 동적 메모리와 연결 리스트 C Express

동적 메모리 할당에 대한 개념을 이해하고 응용으로 연결 리스트를 학습합니다. 이번 장에서 학습할 내용 동적 메모리 할당에 대한 개념을 이해하고 응용으로 연결 리스트를 학습합니다. 동적 메모리 연결 리스트

메모리 할당 방법 정적(static) 자동(automatic) 동적(dynamic) 정적/자동 메모리 할당의 단점 생존 시간(lifetime): 프로그램 시작  프로그램 끝 실행 중에는 메모리가 일정하게 유지되므로 별도의 관리가 불필요함 자동(automatic) 생존 시간: 해당 블록 실행 시작  블록 끝 메모리 할당 및 해제(반납)가 블록과 연동되어 자동으로 이루어짐 실행 시간 스택(runtime stack) 사용 동적(dynamic) 생존 시간: 동적 메모리 할당  동적 메모리 해제 프로그래머가 생존 시간 결정 힙(heap) 사용 정적/자동 메모리 할당의 단점 메모리의 크기가 프로그램 시작 전에 결정되어 고정됨 예: int a[100]; // 배열의 크기에 변수를 사용할 수 없음 결정된 크기보다 더 큰 데이터를 처리할 수 없음 결정된 크기보다 작은 데이터를 처리하면 메모리 낭비 유발

동적 메모리 할당 사용자의 요구에 따라 실행 중에 메모리 할당 및 해제 할당  사용  해제 필요한 만큼만 메모리 할당 가능  메모리를 효율적으로 사용 라이브러리 함수 사용: <stdlib.h> 할당: malloc(), calloc() 재할당: realloc() 해제: free()

동적 메모리 할당/해제 함수 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

예제 #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

예제 #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

예제 #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

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));

예제 #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

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 감소

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;

예제 #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 006D0020 4200KB realloc 1846800KB => succeeded job 00AF0020 1846800KB job 00AF0020 633500KB realloc 2650100KB => failed realloc 1917000KB => failed max size = 1846800KB

예제 #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; } 10 20 30 40 50 60 70 80 ^Z average = 45

연결 리스트 배열(array) 연결 리스트(linked list) 간단하고 다루기 쉬움 특정 위치의 원소에 대한 접근이 빠름 삽입/삭제가 비효율적 연결 리스트(linked list) 각 원소가 포인터를 사용하여 다음 원소를 가리킴 다루기 어렵고 특정 위치의 원소에 대한 접근이 느림 삽입/삭제가 용이함 삽입 B A C D E N 삭제 B A C D E

연결 리스트 노드(node) = 데이터 필드(data field) + 링크 필드(link field) 일반적으로 동적 메모리를 사용하여 생성 헤드 포인터(head pointer): 첫 번째 노드를 가리키는 포인터 자기 참조 구조체(self-referential structure): 멤버 중에 자신과 같은 타입의 구조체를 가리키는 포인터가 있는 구조체 struct node { int data; struct node *link; };

기본적인 연결 리스트 조작 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

예제: 책 리스트 #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

예제: 학생 리스트 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) { ... }

예제: 학생 리스트 (계속) #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: 2013001 강감찬 4.1 ID NAME GPA: 2013002 김유신 4.2 ID NAME GPA: 2013003 이순신 4.3 ID NAME GPA: ^Z 2013003 이순신 4.3 2013002 김유신 4.2 2013001 강감찬 4.1