Part 13 동적 할당 ©우균, 창병모 이 슬라이드는 부산대학교 우균이 작성하였습니다. 오류나 수정할 사항 있으면 woogyun@pusan.ac.kr로 연락 주세요.

이 장의 내용 동적 할당 개념 동적 할당 활용 동적 할당과 스택 자기 참조 구조체

13.1 동적 할당 개념

메모리 할당에 따른 변수 분류 할당과 해제 메모리 할당 방법에 따른 변수 분류 할당(allocation): 변수를 나타내기 위해 메모리 일부를 점유하는 것 해제(deallocation): 더 이상 변수가 필요 없을 때, 변수를 위해 점유해 두었던 메모리를 반납하는 것 메모리 할당 방법에 따른 변수 분류 변수 구분 변수 종류 정적변수 전역변수, 파일범위변수, static 지역변수 동적변수 자동변수 비정적 지역변수, 매개변수 동적 할당 변수 힙 할당 변수 동적 할당 변수(dynamically allocated variables)를 자동변수(automatic variables)와 구별하기 위해 ‘수동 할당 변수(manually allocated variables)’라고 부르기도 한다.

자유 저장공간 프로세스 이미지 세그먼트 프로세스(process): 수행 중인 프로그램 프로세스 이미지(process image): 프로세스가 점유하고 있는 메모리 구획 세그먼트 정적 세그먼트(static segment): 프로그램 수행 중에 내용이 거의 변하지 않는 코드와 리터럴이 저장됨. 코드 세그먼트(code segment)라고 부르기도 함 동적 세그먼트(dynamic segment) 스택(stack): 자동변수가 할당되는 공간 자유 저장공간(free store): 동적 할당 변수가 할당되는 공간. 힙(heap)이라고도 함

13.2 동적 할당 활용

메모리 관리 함수 자유 저장공간 메모리 관리 함수 자유 저장공간을 사용하는 이유 void *malloc(size_t size); size 바이트만큼 메모리 공간을 할당하여 이 공간의 시작주소를 void* 형으로 리턴함 size 바이트만큼 메모리 공간을 할당할 수 없으면 NULL(0)을 리턴함 void free(void *p); 인수로 주어진 포인터 p가 가리키는 공간을 해제함 자유 저장공간을 사용하는 이유 필요한 메모리 공간이 실행시간에 동적으로 결정되는 상황에 대처하기 위해 동적으로 변화하는 자료구조를 구현하기 위해 동적 자료구조 예: 리스트(list), 트리(tree)

prNint.c 임의 개수의 정수를 입력받은 후 역순으로 출력하는 프로그램 입력할 정수를 저장할 변수를 동적으로 할당함 실행결과: 몇 개의 정수를 입력하고 싶으십니까? 5 5 개의 정수를 입력해 주세요: 1 2 3 4 5 당신이 입력한 정수를 역순으로 출력합니다: 5 4 3 2 1

prNint2.c (1/2) 오류검사가 추가된 버전 오류 메시지를 표준오류스트림 stderr에 출력하는 방법은 PART 14 참고 입력한 n이 올바른 값인지 검사 malloc이 성공적으로 메모리를 할당하였는지 검사

prNint2.c (2/2) 이 결과는 컴퓨터마다 다를 수 있음 실행결과 1: 몇 개의 정수를 입력하고 싶으십니까? -3 오류: 정수 개수를 잘못 입력하였습니다. 프로그램을 종료합니다. 이 결과는 컴퓨터마다 다를 수 있음 실행결과 2: 몇 개의 정수를 입력하고 싶으십니까? 1234567890123 오류: 메모리가 부족합니다. 프로그램을 종료합니다.

assert 매크로 assert assert 활용 시 주의사항 디버깅할 때에 특정 조건을 검사하기 위한 매크로 프로그램 수행 중 '수식'이 참이면 오류 메시지를 출력하고 프로그램을 종료시킴 assert 활용 시 주의사항 assert 매크로는 전처리기를 통해 무시하도록 조정할 수 있음 NDEBUG(no debug)를 선언하면 assert 매크로를 무시함 IDE 환경에서: Release 모드로 프로젝트 설정 명령줄 환경에서: cl -DNDEBUG 파일이름 요즘엔 소프트웨어 안정성을 위해, 디버깅이 끝난 후에도 assert를 생략하지 않도록 권유하고 있음

prNint3.c (1/2) assert를 이용하여 malloc 오류를 검사하는 버전 이 부분은 prNint2.c와 동일함

prNint3.c (2/2) 전제조건이 잘못된 지점(파일명, 행 번호)을 가리킴 assert가 출력한 부분 실행결과: 몇 개의 정수를 입력하고 싶으십니까? 1234567890123 Assertion failed: p != NULL, file prNint3.c, line 28 abnormal program termination assert가 출력한 부분

13.3 동적 할당과 스택

컨테이너 컨테이너(container) 구조 컨테이너 구조와 동적 할당 컨테이너 종류 다른 자료를 저장하기 위한 자료구조 배열도 컨테이너 구조라고 볼 수 있음 컨테이너 구조와 동적 할당 동적 할당은 보통 컨테이너 구조를 관리할 때 사용함 컨테이너를 만들 당시에는 컨테이너에 얼마나 많은 데이터를 넣어야 하는지 잘 모르기 때문 컨테이너 종류 큐(queue): 넣은 순서대로 나오는 컨테이너 스택(stack): 가장 최근에 넣은 것이 먼저 나오는 컨테이너 데크(deque: Double-Ended Queue): 양쪽 끝에서 넣고 뺄 수 있는 컨테이너

스택의 특징 스택 스택연산 후입선출(後入先出, LIFO: last-in first-out) 방식의 컨테이너 나중에 들어온 데이터가 가장 먼저 나가는 구조 스택연산 PUSH(s, d):  스택 s에 데이터 d를 넣음 POP(s):      스택 s의 최상위 데이터를 추출하여 리턴함 IS_EMPTY(s): 스택 s가 비었는지 확인함 IS_FULL(s):  스택 s가 꽉 찼는지 확인함 4

배열을 이용한 스택 구현 인터페이스 설계 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 상수로서 별도로 정함 Stack *mkStack(); void push(Stack *s, int item); int pop(Stack *s); int isEmpty(const Stack *s); int isFull(const Stack *s); 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 상수로서 별도로 정함 함수 isEmpty와 isFull은 스택의 상태만 검사하는 함수이므로 const 인수로 스택을 받도록 함

stack.h 스택 최대 크기: 스택에 저장 가능한 원소 개수 스택 타입 정의 스택 인터페이스 (스택을 사용하기 위한 함수)

stack.c (1/2) 오류 메시지 msg를 출력하고 프로그램을 종료함 스택 하나를 할당하여 top을 초기화한 후 스택에 대한 포인터를 리턴함 스택 s에 정수 item을 넣음 넣기 전에 스택이 꽉 찼는가 검사함

stack.c (2/2) 스택 s의 최상위 항목을 빼내어 리턴함 스택 s가 비었는지 검사 스택 s가 꽉 찼는가 검사

prNint4.c (1/2) 스택을 이용하여 입력받은 정수를 역순으로 출력하는 프로그램 스택 타입을 이용하기 위해 "stack.h"를 포함시킴

prNint4.c (2/2) 입력받은 정수를 차례로 스택에 넣음 스택이 빌 때까지 스택에서 원소를 하나씩 꺼내어 출력함 실행결과: 몇 개의 정수를 입력하고 싶으십니까? 1이상 10이하로 입력해 주세요. 5 5 개의 정수를 입력해 주세요: 1 2 3 4 5 당신이 입력한 정수를 역순으로 출력합니다: 5 4 3 2 1

동적 할당 배열을 이용한 스택 구현 인터페이스 설계 설계 노트 Stack *mkStack(int size); void push(Stack *s, int item); int pop(Stack *s); int isEmpty(const Stack *s); int isFull(const Stack *s); 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 스택을 처음 만들 때 정함 스택의 최대 원소 개수는 함수 mkStack의 인수로 전달됨

stack2.h 스택 타입 정의 데이터를 저장할 공간은 선언되지 않음 size는 스택의 크기임 스택 생성 함수

인터페이스와 구현 인터페이스 구현 '무엇(what)'을 만들 것인가 명시함 제공해야 할 기능이 무엇인지 명시할 뿐, 어떻게 그러한 기능을 제공해야 하는지는 명시하지 않음 구현 '어떻게(how)' 만들어지는지 명시함 구현이 없다면 인터페이스를 만족시킬 방법이 없음 인터페이스와 구현을 분리하면, 구현 내용이 변경되어도 해당 인터페이스를 이용하는 클라이언트 프로그램(client program)은 변경될 필요가 없음

13.4 자기 참조 구조체

자기 참조 구조체의 용도 자기 참조 구조체란? 자기 참조 구조체가 필요한 이유 자기 참조 구조체의 장점 및 단점 구조체의 필드에 구조체 포인터 타입이 사용된 구조체 해당 필드를 통해 자신과 같은 형태의 구조체를 참조할 수 있음 자기 참조 구조체가 필요한 이유 유연한 개수의 레코드를 저장해야 할 때 사용함(연결 리스트) 컨테이너 구조가 복잡하게 얽혀 있는 경우에 사용함(트리나 그래프) 자기 참조 구조체의 장점 및 단점 장점: 데이터 구조를 마음대로 구성할 수 있음 단점: 포인터를 사용해야 하기 때문에 데이터 구조가 불완전하게 생성될 가능성이 있으므로 주의해야 함

연결 리스트 연결 리스트(linked list) 연결 리스트 예 데이터 항목 여러 개를 포인터를 통해 연결해 둔 리스트 헤드(head): 연결리스트 맨 앞 항목을 가리키는 포인터 맨 끝 항목의 포인터에는 NULL이 저장됨 연결 리스트 예 학생 데이터 연결 리스트

연결 리스트 관리 연결 리스트 관리의 필요성 큐 형태의 연결 리스트 예 head 포인터를 리스트 앞에 레코드를 추가하기는 쉽지만 리스트 뒤에 레코드를 추가하기는 어려움 그래서 tail 포인터도 관리하는 것이 좋음 큐 형태의 연결 리스트 예

student4.c (1/2) 힙이 꽉 차는 경우를 검사하려면 매 malloc 호출 후에 검사해야 함 학생 레코드 구조체 (연결 리스트를 위한 포인터 next가 선언되어 있음) student 레코드 동적 할당 및 연결

Key Point

Key Point 프로그램 수행 도중 할당되거나 해제되는 변수를 동적 할당 변수라고 하고 프로그램 시작 시 할당되어 프로그램 종료 시 해제되는 변수를 정적 할당 변수라고 한다. 동적 할당 변수를 간단히 동적변수라고 하고 정적 할당 변수를 간단히 정적변수라고 한다. 수동으로 할당되는 변수를 저장하기 위한 공간을 ‘힙(heap)’이라고 한다. 동적 할당을 사용하는 이유는 메모리를 절약하기 위해서다. 라이브러리 함수 malloc은 수동으로 메모리를 할당할 때 사용하고 free는 수동으로 할당한 메모리를 해제할 때 사용한다. 라이브러리 함수 malloc은 메모리 할당에 실패하면 NULL, 즉 (void *)0을 리턴한다. 프로그램 내 특정 지점에서 반드시 만족해야 할 전제조건을 검사할 경우에는 assert 매크로를 활용하면 편리하다. 스택이란 후입선출(LIFO: last-in first-out) 구조의 컨테이너이다.

요약(1/3) 프로세스 이미지 동적 할당 동적 할당 라이브러리 실행중인 프로그램이 차지하고 있는 메모리 영역 정적 세그먼트와 동적 세그먼트로 나누어져 있음 동적 할당 프로그램 실행 중에 필요한 만큼 메모리(변수)를 할당하는 것 동적 할당 메모리는 동적 세그먼트의 자유 저장공간에 할당됨 동적 할당 라이브러리 void *malloc(size_t size); size 바이트만큼 메모리 공간을 할당하여 이 공간의 시작주소를 void* 형으로 리턴함. 메모리가 부족하면 NULL(0)을 리턴함 void free(void *p); 인수로 주어진 포인터 p가 가리키는 공간을 해제함

요약(2/3) assert 매크로 컨테이너 스택 전제조건을 검사하기 위한 매크로 NDEBUG가 정의되면 assert는 무시됨 컨테이너 다른 여러 데이터를 저장하기 위한 데이터 구조 예: 배열, 리스트, 큐, 스택, 데크 스택 후입선출(LIFO) 컨테이너 구현 1: 배열을 이용한 구현 구현 2: 동적 할당된 배열을 이용한 구현 구현 3: 연결 리스트를 이용한 구현

요약(3/3) 연결 리스트 인터페이스와 구현 필요한 데이터를 포인터로 연결해 놓은 구조 자기 참조 구조체로 구현할 수 있음 인터페이스: ‘무엇’을 제공하는지 명시함 구현: ‘어떻게’ 제공하는지 명시함 인터페이스와 구현을 분리하여 프로그램을 작성하면, 구현이 변경되었을 때에도 클라이언트 프로그램을 변경할 필요가 없다.

프로그래밍 실습

▶ 프로그래밍 실습 1-1 도서 목록 관리 프로그램을 작성하려고 한다. 각 도서는 저자, 도서명, 출판년도 정보를 저장하고 있다. 여기에서 저자, 도서명은 각 도서마다 다르므로 동적 할당을 이용하여 메모리를 할당한다. (1) n 개의 도서 목록을 읽어 들여 이를 출력하는 프로그램을 작성하라. 하나의 도서 정보는 세 개의 행으로 구성되어 있다. 첫 번째 행에는 저자명이 오고, 두 번째 행에는 도서명이, 세 번째 행에는 출판년도가 나타난다. 도서 목록에서 각 도서 정보는 하나의 빈 행으로 구별한다(입력형식 참고). 각 도서 정보는 저자명, 도서명, 출판년도 순으로 출력한다. 한 행에 하나의 도서 정보가 나타나도록 출력하되 각 필드는 쉼표로 구별한다(출력형식 1 참고). 입력형식: Polya How to solve it 1957 Kernighan and Ritchie Programming Language C 1988 출력형식 1: Polya, How to solve it, 1957 Kernighan and Ritchie, Programming Language C, 1988

▶ 프로그래밍 실습 1-2 (2) 출력 형식을 HTML 형식으로 바꾸어 출력하여라. 제목은 “내가 좋아하는 책들”이라고 하고 각 도서 목록은 <ul>의 <li>로 나타낸다. 단 도서명 부분은 <em>으로 강조하여 나타낸다(출력형식 2 참고). (3) 읽어 들인 도서 목록을 출판년도 내림차순으로 출력하는 프로그램을 작성하라. 출력 형식은 역시 HTML로 한다. 출력형식 2: <html>   <head><title>내가 좋아하는 책들</title></head>   <body>     <ul>       <li> Polya, <em>How to solve it</em>, 1957</li>       <li> Kernighan and Ritchie, <em>Programming Language C</em>, 1988</li>     </ul>   </body> </html>

▶ 프로그래밍 실습 2 문자열을 n개 입력 받아 이들 문자열을 사전순으로 정렬하는 프로그램을 작성하라. 이 프로그램은 처음에 문자열 개수를 나타내는 정수 n을 먼저 입력 받는다. 그 다음 각 문자열을 저장하는 데 필요한 공간을 할당한다. 문자열의 최대 길이는 #define 상수 MAX_LENGTH로 정한다. 문자열을 읽어 들일 때는 MAX_LENGTH 길이의 char형 배열에 읽어 들이지만, 일단 읽은 뒤에는 각 문자열 저장에 필요한 만큼만 메모리를 할당하여 문자열을 저장한다. 사전순으로 정렬하기 위해서 라이브러리 함수 qsort를 이용한다.