동적할당 Heeseung Jo
이장의내용 동적할당개념동적할당활용동적할당과스택자기참조구조체 2
동적할당개념
메모리할당에따른변수분류 할당과해제 할당 (allocation): 변수를나타내기위해메모리일부를점유하는것 해제 (deallocation): 더이상변수가필요없을때, 변수를위해점유해두었던메모리를반납하는것 메모리할당방법에따른변수분류 변수구분 정적변수 동적변수 변수종류전역변수, 파일범위변수, static 지역변수자동변수비정적지역변수, 매개변수동적할당변수힙할당변수, 프로그램이유지되는동안지속 동적할당변수 (dynamically allocated variables) 를자동변수 (automatic variables) 와구별하기위해 ' 수동할당변수 (manually allocated variables)' 라고부르기도함 4
자유저장공간 프로세스이미지 프로세스 (process): 수행중인프로그램 프로세스이미지 (process image): 프로세스가점유하고있는메모리구획 세그먼트 정적세그먼트 (static segment): 프로그램수행중에내용이거의변하지않는코드와리터럴이저장됨 - 코드세그먼트 (code segment) 라고부르기도함 동적세그먼트 (dynamic segment) - 스택 (stack): 자동변수가할당되는공간 - 자유저장공간 (free store): 동적할당변수가할당되는공간 힙 (heap) 이라고도함 5
동적할당활용
메모리관리함수 자유저장공간메모리관리함수 void *malloc(size_t size); - size 바이트만큼메모리공간을할당하여이공간의시작주소를 void* 형으로리턴 - size 바이트만큼메모리공간을할당할수없으면 NULL(0) 을리턴 void free(void *p); - 인수로주어진포인터 p 가가리키는공간을해제 자유저장공간을사용하는이유 필요한메모리공간이실행시간에동적으로결정되는상황에대처하기위해 동적으로변화하는자료구조를구현하기위해 동적자료구조예 : 리스트 (list), 트리 (tree) 7
prnint.c 임의개수의정수를입력받은후역순으로출력하는프로그램 실행결과 : 몇개의정수를입력하고싶으십니까? 5 5 개의정수를입력해주세요 : 1 2 3 4 5 당신이입력한정수를역순으로출력합니다 : 5 4 3 2 1 입력할정수를저장할변수를동적으로할당함 8
prnint2.c (1/2) 오류검사가추가된버전 오류메시지를표준오류스트림 stderr 에출력하는방법은 PART 14 참고 입력한 n 이올바른값인지검사 malloc 이성공적으로메모리를할당하였는지검사 9
prnint2.c (2/2) 실행결과 1: 몇개의정수를입력하고싶으십니까? -3 오류 : 정수개수를잘못입력하였습니다. 프로그램을종료합니다. 이결과는컴퓨터마다다를수있음 실행결과 2: 몇개의정수를입력하고싶으십니까? 1234567890123 오류 : 메모리가부족합니다. 프로그램을종료합니다. 10
assert 매크로 assert 디버깅할때에특정조건을검사하기위한매크로 assert( 수식 ); 형태로사용함 프로그램수행중 ' 수식 ' 이참이면오류메시지를출력하고프로그램을종료시킴 assert 활용시주의사항 assert 매크로는전처리기를통해무시하도록조정할수있음 NDEBUG(no debug) 를선언하면 assert 매크로를무시함 - IDE 환경에서 : Release 모드로프로젝트설정 - 명령줄환경에서 : cl -DNDEBUG 파일이름 요즘엔소프트웨어안정성을위해, 디버깅이끝난후에도 assert 를생략하지않도록권유하고있음 11
prnint3.c (1/2) assert 를이용하여 malloc 오류를검사하는버전 이부분은 prnint2.c 와동일함 malloc 리턴값을 assert 로검사함 12
prnint3.c (2/2) 전제조건이잘못된지점 ( 파일명, 행번호 ) 을가리킴 실행결과 : 몇개의정수를입력하고싶으십니까? 1234567890123 Assertion failed: p!= NULL, file prnint3.c, line 28 assert 가출력한부분 abnormal program termination 13
동적할당과스택
컨테이너 컨테이너 (container) 구조 다른자료를저장하기위한자료구조 배열도컨테이너구조라고볼수있음 컨테이너구조와동적할당 동적할당은보통컨테이너구조를관리할때사용함 컨테이너를만들당시에는컨테이너에얼마나많은데이터를넣어야하는지잘모르기때문 컨테이너종류 큐 (queue): 넣은순서대로나오는컨테이너 스택 (stack): 가장최근에넣은것이먼저나오는컨테이너 데크 (deque: Double-Ended Queue): 양쪽끝에서넣고뺄수있는컨테이너 15
스택의특징 스택 후입선출 ( 後入先出, LIFO: last-in first-out) 방식의컨테이너 나중에들어온데이터가가장먼저나가는구조 스택연산 PUSH(s, d): 스택 s에데이터 d를넣음 POP(s): 스택 s의최상위데이터를추출하여리턴함 IS_EMPTY(s): 스택 s가비었는지확인함 IS_FULL(s): 스택 s가꽉찼는지확인함 4 16
배열을이용한스택구현 인터페이스설계 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 인수로스택을받도록함 17
stack.h 스택최대크기 : 스택에저장가능한원소개수 스택타입정의 스택인터페이스 ( 스택을사용하기위한함수 ) 18
stack.c (1/2) 오류메시지 msg 를출력하고프로그램을종료함 스택하나를할당하여 top 을초기화한후스택에대한포인터를리턴함 스택 s 에정수 item 을넣음넣기전에스택이꽉찼는가검사함 19
stack.c (2/2) 스택 s 의최상위항목을빼내어리턴함 스택 s 가비었는지검사 스택 s 가꽉찼는가검사 20
prnint4.c (1/2) 스택을이용하여입력받은정수를역순으로출력하는프로그램 스택타입을이용하기위해 "stack.h" 를포함시킴 21
prnint4.c (2/2) 입력받은정수를차례로스택에넣음 스택이빌때까지스택에서원소를하나씩꺼내어출력함 실행결과 : 몇개의정수를입력하고싶으십니까? 1 이상 10 이하로입력해주세요. 5 5 개의정수를입력해주세요 : 1 2 3 4 5 당신이입력한정수를역순으로출력합니다 : 5 4 3 2 1 22
인터페이스와구현 인터페이스 Stack *mkstack(); void push(stack *s, int item); int pop(stack *s); int isempty(const Stack *s); int isfull(const Stack *s); 구현 ' 무엇 (what)' 을만들것인가명시함 제공해야할기능이무엇인지명시할뿐, 어떻게그러한기능을제공해야하는지는명시하지않음 ' 어떻게 (how)' 만들어지는지명시함 구현이없다면인터페이스를만족시킬방법이없음 인터페이스와구현을분리하면, 구현내용이변경되어도해당인터페이스를이용하는클라이언트프로그램 (client program) 은변경될필요가없음 25
자기참조구조체
자기참조구조체의용도 자기참조구조체란? 구조체의필드에구조체포인터타입이사용된구조체 해당필드를통해자신과같은형태의구조체를참조할수있음 자기참조구조체가필요한이유 유연한개수의레코드를저장해야할때사용함 ( 연결리스트 ) 컨테이너구조가복잡하게얽혀있는경우에사용함 ( 트리나그래프 ) 자기참조구조체의장점및단점 장점 : 데이터구조를마음대로구성할수있음 단점 : 포인터를사용해야하기때문에데이터구조가불완전하게생성될가능성이있으므로주의해야함 27
연결리스트 연결리스트 (linked list) 데이터항목여러개를포인터를통해연결해둔리스트 헤드 (head): 연결리스트맨앞항목을가리키는포인터 맨끝항목의포인터에는 NULL이저장됨 연결리스트예 학생데이터연결리스트 28
연결리스트관리 연결리스트관리의필요성 head 포인터를리스트앞에레코드를추가하기는쉽지만리스트뒤에레코드를추가하기는어려움 그래서 tail 포인터도관리하는것이좋음 큐형태의연결리스트예 29
student4.c 학생레코드구조체 ( 연결리스트를위한포인터 next 가선언되어있음 ) 힙이꽉차는경우를검사하려면매 malloc 호출후에검사해야함 student 레코드동적할당및연결 30
프로그래밍실습
프로그래밍실습 문자열을 n 개입력받아이들문자열중 'a' 로시작하는문자열만출력하는프로그램을작성 처음에문자열개수를나타내는정수 n 을먼저입력받음 이후로는문자열들을계속입력받음 각문자열을저장하는데필요한공간을할당 - 문자열의최대길이는 #define 상수 MAX_LENGTH 로정의 - 문자열을읽어들일때는 MAX_LENGTH 길이의 char 형배열에읽어들이지만, 일단읽은뒤에는각문자열저장에필요한만큼만메모리를할당하여문자열을저장 사전순으로정렬하기위해서라이브러리함수 qsort 를이용 34