제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.
이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함 더작은입력이들어온다면남은메모리공간은낭비 3
동적메모리 동적메모리 실행도중에동적으로메모리를할당받는것 사용이끝나면시스템에메모리를반납 필요한만큼만할당을받고메모리를매우효율적으로사용 malloc() 계열의라이브러리함수를사용 운영체제 요구 #include #include <stdio.h> <stdio.h> #include #include <stdlib.h> <stdlib.h> 할당 int int main(void) main(void) { int int *p; *p; p = (int (int *)malloc( *)malloc( sizeof(int) sizeof(int) ); );...... } 프로그램 4
동적메모리할당의과정 #include <stdio.h> #include <stdlib.h> int main(void) { int *pi; // 동적메모리를가리키는포인터 1 동적메모리할당 pi = (int *)malloc(sizeof(int)); // 1 동적메모리할당 2 동적메모리사용 if( pi == NULL ) // 반환값이 NULL인지검사 { printf(" 동적메모리할당오류 \n"); exit(1); } *pi = 100; // 2 동적메모리사용 printf("%d\n", *pi); 3 동적메모리반납 free(pi); // 3 동적메모리반납 return 0; } 5
malloc() 과 free() void *malloc(size_t size); malloc() 은바이트단위로메모리를할당 size는바이트의수 malloc() 함수는메모리블럭의첫번째바이트에대한주소를반환 만약요청한메모리공간을할당할수없는경우에는 NULL값을반환 동적메모리 1 바이트가필요합니다. 사용후엔반드시반납해주세요.. 필요한바이트수 malloc() void free(void *ptr); free() 는동적으로할당되었던메모리블록을시스템에반납 ptr 은 malloc() 을이용하여동적할당된메모리를가리키는포인터 void * 타입의포인터 6
malloc1.c 1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. int main( void ) 5. { 6. char *pc = NULL; 7. 8. pc = (char *)malloc( sizeof(char) ); 9. if( pc == NULL ) 10. { 11. printf( " 메모리할당오류 \n" ); 12. exit(1); 13. } 14. *pc = 'm'; 15. printf( "*pc = %c\n", *pc ); 16. free( pc ); 17. 18. return 0; 19. } 1000 바이트가할당되었습니다. 메모리를반납하였습니다. 7
malloc2.c 1. // 메모리동적할당 2. #include <stdio.h> 3. #include <stdlib.h> 4. int main(void) 5. { 6. char *pc = NULL; 7. int i = 0; 8. pc = (char *)malloc(100*sizeof(char)); 9. if( pc == NULL ) 10. { 11. printf(" 메모리할당오류 \n"); 12. exit(1); 13. } 14. for(i=0;i<26;i++) 15. { 16. *(pc+i) = 'a'+i;// 알파벳소문자를순서대로대입 17. } 18. *(pc+i) = 0; // NULL 문자추가 19. printf("%s\n", pc); 20. free(pc); 21. return 0; 22. } abcdefghijklmnopqrstuvwxyz 8
malloc3.c 1. #include <stdio.h> 2. #include <stdlib.h> 3. int main(void) 4. { 5. int *pi; 6. pi = (int *)malloc(5 * sizeof(int)); 7. if(pi == NULL){ 8. printf(" 메모리할당오류 \n") ; 9. exit(1); 10. } 11. pi[0] = 100; // *(pi+0) = 100; 와같다. 12. pi[1] = 200; // *(pi+1) = 200; 와같다. 13. pi[2] = 300; // *(pi+2) = 300; 와같다. 14. pi[3] = 400; // *(pi+3) = 400; 와같다. 15. pi[4] = 500; // *(pi+4) = 500; 와같다. 16. free(pi); 17. return 0; 18. } 9
malloc4.c 1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <string.h> 4. struct Book { 5. int number; 6. char title[10]; 7. }; 8. int main(void) 9. { 10. struct Book *p; 11. p = (struct Book *)malloc(2 * sizeof(struct Book)); 12. if(p == NULL){ 13. printf(" 메모리할당오류 \n") ; 14. exit(1); 15. } 16. p->number = 1; 17. strcpy(p->title,"c Programming"); 18. (p+1)->number = 2; 19. strcpy((p+1)->title,"data Structure"); 20. free(p); 21. return 0; 22. } 10
calloc() 과 realloc() void *calloc(size_t n, size_t size); malloc() calloc() 은 malloc() 과는다르게 0 으로초기화된메모리할당 항목단위로메모리를할당 ( 예 ) p? calloc()???? int *p; p = (int *)calloc(5, sizeof(int)); p 0 0 0 0 0 void *realloc(void *memblock, size_t size); malloc () realloc() 함수는할당하였던메모리블록의크기를변경 p 10 20 30 40 50 ( 예 ) int *p; p = (int *)malloc(5 * sizeof(int))); re alloc () p = realloc(p, 7 * sizeof(int))); p 10 20 30 40 50?? 11
연결리스트 배열 (array) 장점 : 구현이간단하고빠르다 단점 : 크기가고정된다. 중간에서삽입, 삭제가어렵다. 0 1 2 3 4 5 6 7 8 9 연결리스트 (linked list) 각각의원소가포인터를사용하여다음원소의위치를가리킨다. A C D E B 메인메모리 12
연결리스트의장단점 중간에데이터를삽입, 삭제하는경우 A N C D E A C D E B B 메인메모리 메인메모리 데이터를저장할공간이필요할때마다동적으로공간을만들어서쉽게추가 구현이어렵고오류가나기쉽다. 13
연결리스트의구조 노드 (node) = 데이터필드 (data field) + 링크필드 (link field) 연결리스트의노드는데이터필드와링크필드로이루어집니다. data link 헤드포인터 (head pointer): 첫번째노드를가리키는포인터 첫번째노드를가리키는포인터를헤드포인터라고하고맨마지막노드의링크필드는 NULL 입니다. plist 10 20 30 NULL NULL 40 NULL 50 NULL 14
자기참조구조체 자기참조구조체 (self-referential structure) 는특별한구조체로서구성멤버중에같은타입의구조체를가리키는포인터가존재하는구조체 // 데이터의정의 typedef struct data { int id; char name[20]; char phone[12]; } DATA; // 노드의정의 typedef struct NODE { DATA data; struct NODE *link; } NODE; 15
간단한연결리스트생성 NODE *p1; p1 = (NODE *)malloc(sizeof(node)); p1->data = 10; p1->link = NULL; NODE *p2; p2 = (NODE *)malloc(sizeof(node)); p2->data = 20; p1 p1 10 NULL p2->link = NULL; p1->link = p2; p1 10 20 NULL free(p1); free(p2); 16
연결리스트의삽입연산 NODE *insert_node(node *plist, NODE *pprev, DATA item); 1. 리스트의처음에삽입하는경우 pnew->link = plist; plist 10 20 30 NULL plist = pnew; pnew 5 2. 리스트의중간에삽입하는경우 pprev pnew->link = pprev->link;// 1 pprev->link = pnew;// 2 plist 10 20 30 NULL 2 1 pnew 5 17
연결리스트의삽입연산 NODE *insert_node(node *plist, NODE *pprev, DATA item) { NODE *pnew = NULL; if(!(pnew = (NODE *)malloc(sizeof(node))) ) { printf(" 메모리동적할당오류 \n"); exit(1); } } pnew->data = data; if( pprev == NULL ) // 연결리스트의처음에삽입 { pnew->link = plist; plist = pnew; } else // 연결리스트의중간에삽입 { pnew->link = pprev->link; pprev->link = pnew; } return plist; 18
연결리스트의삭제연산 NODE *delete_node(node *plist, NODE *pprev, NODE *pcurr); 1. 리스트의처음을삭제하는경우 plist = pcurr->link; free(pcurr); plist 10 20 30 NULL pcurr 2. 리스트의중간에삽입하는경우 pprev->link = pcurr->link; free(pcurr); plist 10 20 30 40 NULL pprev pcurr 19
연결리스트의삭제연산 NODE *delete_node(node *plist, NODE *pprev, NODE *pcurr) { if( pprev == NULL ) plist = pcurr->link; else pprev->link = pcurr->link; } free(pcurr); return plist; 20
연결리스트의순회연산 void print_list(node *plist) { NODE *p; p = plist; printf("( "); } while( p ) { } printf(")\n"); printf("%d ", p->data); p = p->link; plist 10 20 30... 90 NULL p p p p 21
노드의개수세기 1. int get_length(node *plist) 2. { 3. NODE *p; 4. int length = 0; 5. p = plist; 6. while( p ) 7. { 8. length++; 9. p = p->link; 10. } 11. printf(" 리스트의길이는 %d\n", length); 12. return length; 13. } 22
합계구하기 1. int get_sum(node *plist) 2. { 3. NODE *p; 4. int sum = 0; 5. p = plist; 6. while( p ) 7. { 8. sum += p->data; 9. p = p->link; 10. } 11. printf(" 리스트의합계는 %d\n", sum); 12. return sum; 13. } 23
Q & A 24