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

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

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

2 이 장의 내용 동적 할당 개념 동적 할당 활용 스택

3 13.1 동적 할당 개념

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

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

6 13.2 동적 할당 활용

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

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

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

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

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

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

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

14 13.3 스택

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

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

17 배열을 이용한 스택 구현 인터페이스 설계 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 상수로서 별도로 정함
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 인수로 스택을 받도록 함

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

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

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

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

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

23 동적 할당 배열을 이용한 스택 구현 인터페이스 설계 설계 노트
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의 인수로 전달됨

24 stack2.h 스택 타입 정의 데이터를 저장할 공간은 선언되지 않음 size는 스택의 크기를 나타냄 스택 인터페이스
(스택을 사용하기 위한 함수)

25 stack2.c (1/2) 오류 메시지 msg를 출력하고 프로그램을 종료함 스택 하나를 할당하여 스택에 대한 포인터를 리턴함
데이터를 저장할 공간을 새로 할당하여 data에 대입

26 stack2.c (2/2) 스택 s에 정수 항목을 넣음 스택 s의 최상위 항목을 빼내어 리턴함 스택 s가 비었는가 검사

27 prNint5.c 필요한 크기로 스택을 생성하는 것 외에는 prNint4.c와 같음 실행결과:
몇 개의 정수를 입력하고 싶으십니까? 5 5 개의 정수를 입력해 주세요: 당신이 입력한 정수를 역순으로 출력합니다:

28 연결 리스트 연결 리스트(linked list) 연결 리스트 예 데이터 항목 여러 개를 포인터를 통해 연결해 둔 리스트
헤더(header): 연결리스트 맨 앞 항목을 가리키는 포인터 맨 끝 항목의 포인터에는 NULL이 저장됨 항목을 추가할 때, 데이터를 저장하기 위한 공간과 포인터를 함께 할당함 맨 앞에 항목을 추가하는 것은 매우 쉽지만 맨 끝에 항목을 추가하는 것은 어려움 연결 리스트 예 데이터 1, 2, 3이 차례로 연결된 연결 리스트

29 연결 리스트 설계 인터페이스 설계 설계 노트 List mkList(); 새로운 연결 리스트를 생성하여 리턴
void addFront(List *lp, int data); lp가 가리키는 연결 리스트의 맨 앞에 data를 추가함 int delFront(List *lp); lp가 가리키는 연결 리스트의 맨 앞 항목을 제거하여 리턴 int isEmptyList(const List l); 연결 리스트 l이 비었는지 검사함 설계 노트 addFront와 delFront는 해당 연결 리스트를 변경해야 하므로 연결 리스트에 대한 포인터를 인수로 전달하도록 하였음 isEmptyList는 연결 리스트 상태를 보기만 하므로 const 인수로 리스트를 전달함 int 외에 다른 데이터를 저장하도록 연결리스트를 설계할 수도 있음

30 list.h 연결 리스트 노드 data: 저장할 데이터 항목 next: 다음 노드를 가리키는 포인터
List는 Node*로 정의됨 연결 리스트 인터페이스

31 list.c (1/2) …(error 함수 정의 생략)… 아무 노드가 없는(NULL로 초기화된) 헤더를 리턴함
③ 링크를 연결함 ② data를 복사한 후 ① 새 노드를 만들고

32 list.c (2/2) ③ 노드를 삭제함 ② 리턴값을 복사한 후 ① 링크를 변경하고

33 연결 리스트를 이용한 스택 구현 인터페이스 설계 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 정해지지 않음
Stack *mkStack(); void push(Stack *s, int item); int pop(Stack *s); int isEmpty(const Stack *s); int isFull(const Stack *s); 설계 노트 스택에 저장할 수 있는 최대 원소 개수는 정해지지 않음 자유 저장공간이 허용하는 한도 내에서 스택에 원소를 저장할 수 있기 때문

34 stack3.h 연결 리스트를 사용하기 위함 스택은 연결 리스트와 동일함 스택 인터페이스 (스택을 사용하기 위한 함수)

35 stack3.c (1/2) 스택을 하나 할당하고 연결 리스트를 새로 만들어 여기에 스택으로서 리턴함 push는 연결 리스트의
addFront 이용 pop은 연결 리스트의 delFront 이용

36 stack3.c (2/2) 연결 리스트가 비었으면 스택도 빈 것임 자유 저장공간을 모두 사용하므로
스택이 꽉 차는 경우는 없다고 가정함 항상 거짓(0)으로 리턴 자유 저장 공간이 꽉 차는 경우를 검사하려면 Stack의 push 함수, 즉 List의 addFront 함수에서 검사하는 것이 바람직함

37 prNint6.c 스택 크기를 정하지 않는 것을 제외하면 prNint5.c와 같음 실행결과:
몇 개의 정수를 입력하고 싶으십니까? 5 5 개의 정수를 입력해 주세요: 당신이 입력한 정수를 역순으로 출력합니다:

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

39 Key Point

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

41 Key Point(고급 주제) 스택이란 후입선출(LIFO: last-in first-out) 구조의 컨테이너이다.
분리 컴파일이란 여러 소스파일로 구성된 프로그램이 있을 때, 개별 소스파일 단위로 컴파일하는 기능을 의미한다. 분리 컴파일은 공동 프로젝트를 진행하기 편리하게 해 주며 컴파일 시간을 단축시켜 준다. 인터페이스는 ‘무엇을 만들 것인가’를 명시하고 구현은 ‘어떻게 만들 것인가’를 명시한다. 프로그램을 작성할 때에는 인터페이스와 구현을 분리하여 작성하는 것이 중요하다.

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

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

44 요약(3/3) 연결 리스트 인터페이스와 구현 필요한 데이터를 포인터로 연결해 놓은 구조 맨 앞에 삽입하는 연산 비용이 저렴함
스택을 구현하는데 적합한 자료구조 인터페이스와 구현 인터페이스: '무엇'을 제공하는지 명시함 구현: '어떻게' 제공하는지 명시함 인터페이스와 구현을 분리하여 프로그램을 작성하면, 구현이 변경되었을 때에도 클라이언트 프로그램을 변경할 필요가 없다.

45 프로그래밍 실습

46 ▶ 프로그래밍 실습 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

47 ▶ 프로그래밍 실습 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>

48 ▶ 프로그래밍 실습 2 연결 리스트를 이용하여 삽입정렬(insertion sort)을 수행하는 프로그램을 작성하라. 삽입정렬이란 데이터를 하나씩 읽을 때마다 제 위치를 찾아서 넣어 주는 정렬 방식이다. 예를 들어, 다음과 같이 다섯 개의 숫자가 있다고 할 때 이들을 오름차순으로 정렬하는 과정은 오른편 그림과 같다. 이런 방식으로 임의의 숫자 n개를 입력받은 후에 이들을 오름차순으로 정렬하는 프로그램을 작성하라. n개의 숫자가 모두 입력되면 EOF가 나타난다고 가정하자. 삽입정렬 예: 3 3 5 2 3 5