쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트
이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다.
동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic)
정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 ( 예 ) int score_s[100]; 처음에결정된크기보다더큰입력이들어온다면처리하지못함 더작은입력이들어온다면남은메모리공간은낭비
동적메모리할당 동적메모리할당 실행도중에동적으로메모리를할당받는것 사용이끝나면시스템에메모리를반납 score = (int *) malloc(100*sizeof(int)); 필요한만큼만할당을받고메모리를매우효율적으로사용 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) ); );...... } 프로그램
동적메모리할당절차
동적메모리할당예제 #include <stdio.h> #include <stdlib.h> int main(void) { int *score; int i; score = (int *)malloc( 100*sizeof(int) ); if( p == NULL ) // 반환값이 NULL인지검사 { printf(" 동적메모리할당오류 \n"); exit(1); } for(i=0 ; i<100 ; i++) score[i] = 0; free(p); return 0; } 동적메모리할당 동적메모리해제
동적메모리할당 void *malloc(size_t size) size는바이트의수 malloc() 함수는메모리블럭의첫번째바이트에대한주소를반환 만약요청한메모리공간을할당할수없는경우에는 NULL값을반환 int *score; score = (int *)malloc(100*sizeof(int)); if( score == NULL ){... // 오류처리 } score?????
동적메모리사용 할당받은공간은어떻게사용하면좋을까? 첫번째방법 : 포인터를통하여사용 *score = 100; *(score+1) = 200; *(score+2) = 300;... 두번째방법 : 동적메모리를배열과같이취급 score[0] = 100; score[1] = 200; score[2] = 300;... score 100 200 300??
동적메모리반납 void free(void *ptr) free() 는동적으로할당되었던메모리블록을시스템에반납 ptr은 malloc() 을이용하여동적할당된메모리를가리키는포인터 int *score; score = (int *)malloc(100*sizeof(int)); free(score); score?????
예제 #include <stdio.h> #include <stdlib.h> int main(void) { char *pc = NULL; int i= 0; pc = (char *)malloc(100*sizeof(char)); if( pc == NULL ) { printf(" 메모리할당오류 \n"); exit(1); } for(i=0;i<26;i++){ pc[i] = 'a'+i; // 알파벳소문자를순서대로대입 } pc[i] = 0; // NULL 문자추가 printf("%s\n", pc); free(pc); return 0; } abcdefghijklmnopqrstuvwxyz
예제 struct Book { int number; char title[10]; }; int main(void) { struct Book *p; 구조체배열할당 } p = (struct Book *)malloc(2 * sizeof(struct Book)); if(p == NULL){ printf(" 메모리할당오류 \n") ; exit(1); } p->number = 1; strcpy(p->title,"c Programming"); (p+1)->number = 2; strcpy((p+1)->title,"data Structure"); free(p); return 0;
calloc() void *calloc(size_t n, size_t size); calloc() 은 0으로초기화된메모리할당 항목단위로메모리를할당 ( 예 ) int *p; p = (int *)calloc(5, sizeof(int)); malloc() p?????? calloc() p 0 0 0 0 0 0
realloc() void *realloc(void *memblock, size_t size); realloc() 함수는할당하였던메모리블록의크기를변경 ( 예 ) int *p; p = (int *)malloc(5 * sizeof(int))); p = realloc(p, 7 * sizeof(int))); malloc() 1 5 7 4 2 9 p realloc() p 1 5 7 4 2 9??
예제 #include <stdio.h> #include <stdlib.h> #define INCREMENT 100 // 한번에증가시키는크기 double *scores = NULL; int add_score(double new_score) { static int limit = 0; // 현재동적배열의최대크기 static int count = 0; // 현재동적배열의크기 if( count < limit ){ scores[count++]= new_score; } else { int new_limit = limit + INCREMENT; double *new_array = realloc(scores, new_limit*sizeof(double)); if( new_array == NULL ){ fprintf(stderr, " 메모리할당오류 \n"); } else { scores = new_array; limit = new_limit; scores[count++] = new_score; } return count; } }
예제 int main(void) { int i, size; double value, total=0.0; size = 3; for(i=0;i<size;i++) { printf(" 성적 : "); scanf("%lf", &value); add_score(value); } for(i=0;i<size;i++){ total += scores[i]; } printf(" 평균 : %f\n", total/size); return 0; } free(scores); 성적 : 10 성적 : 20 성적 : 30 평균 : 20.000000
중간점검 1. 프로그램의실행도중에메모리를할당받아서사용하는것을 이라고한다. 2. 동적으로메모리를할당받을때사용하는대표적인함수는 이다. 3. 동적으로할당된메모리를해제하는함수는 이다. 4. 동적메모리함수의원형은헤더파일 에정의되어있다.
중간점검 1. 동적할당후에메모리블록을초기화하여넘겨주는함수는 이다. 2. 할당되었던동적메모리의크기를변경하는함수는 이다. 3. 동적메모리할당에서의단위는 이다. 4. malloc() 이반환하는자료형은 이다.
연결리스트 배열 (array) 장점 : 구현이간단하고빠르다 단점 : 크기가고정된다. 중간에서삽입, 삭제가어렵다. 0 1 2 3 4 5 6 7 8 9 연결리스트 (linked list) 각각의원소가포인터를사용하여다음원소의위치를가리킨다. A C D E B 메인메모리
연결리스트의장단점 중간에데이터를삽입, 삭제하는경우 N A C D E A C D E B B 데이터삽입 데이터삭제 데이터를저장할공간이필요할때마다동적으로공간을만들어서쉽게추가 구현이어렵고오류가나기쉽다. 중간에있는데이터를빠르게가져올수없다.
연결리스트의구조 노드 (node) = 데이터필드 (data field)+ 링크필드 (link field) 연결리스트의노드는데이터필드와링크필드로이루어집니다. data link
연결리스트의구조 헤드포인터 (head pointer): 첫번째노드를가리키는포인터 첫번째노드를가리키는포인터를헤드포인터라고하고맨마지막노드의링크필드는 NULL 입니다. plist 10 20 30 NULL NULL 40 NULL 50 NULL
노드생성 노드들은동적으로생성된다.
자기참조구조체 자기참조구조체 (self-referential structure) 는특별한구조체로서구성멤버중에같은타입의구조체를가리키는포인터가존재하는구조체 typedef struct NODE { int data; struct NODE *link; } NODE;
간단한연결리스트생성 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; free(p1); free(p2); p1 10 20 NULL p1 10 20 NULL
연결리스트의응용 소장하고있는책의목록을관리하는프로그램을작성 연결리스트를사용하여서작성
연결리스트를이용한프로그램
실행결과
중간점검 1. 연결리스트에서다음노드는 로가리킨다. 2. 연결리스트의일반적인노드는 필드와 필드로구성되어있다. 3. 구조체의멤버중에자기자신을가리키는포인터가존재하는구조체를 라고한다. 4. 배열과연결리스트의가장큰차이점은무엇인가?
실습 : 영화관리프로그램 구조체배열을동적메모리를이용하여서생성하고여기에영화정보를저장했다가다시화면에예쁘게출력하는프로그램을작성하여보자. 영화정보를사용자로부터받는다.
실행결과 몇편이나저장하시겠습니까? 1 영화제목 : 트랜스포머영화평점 :8.3 ======================== 제목평점 ======================== 트랜스포머 8.300000 ========================
힌트 이문제는물론정적배열을사용하면아주쉬운문제이지만여기서동적메모리할당을이용해보자. 동적메모리를사용하면사용자가원하는만큼의공간을실행시간에할당받을수있다. 먼저영화정보를다음과같이구조체로표현한다. typedef struct movie { // 구조체타입정의 char title[100]; // 영화제목 double rating; // 영화평점 } MOVIE; 사용자가입력하고자하는영화의수를 size에입력받은후에, 동적으로할당 movies = (MOVE *)malloc(sizeof(movie)* size); // 동적메모리할당
예제 #include <stdio.h> typedef struct movie { // 구조체타입정의 char title[100]; // 영화제목 double rating; // 영화평점 } MOVIE; int main(void) { MOVIE *movies; // 동적메모리공간을가리키는포인터 int size, i; printf(" 몇편이나저장하시겠습니까? "); scanf("%d", &size); movies = (MOVIE *)malloc(sizeof(movie)* size); // 동적메모리할당 if( movies == NULL ){ printf(" 동적메모리할당오류 ); exit(1); }
예제 } for(i=0; i<size ;i++) { // size편의영화정보입력 printf(" 영화제목 ); fflush(stdin); // 입력버퍼를비운다. gets(movies[i].title); // 영화제목에는빈칸이있을수있다. printf(" 영화평점 ); scanf("%lf", &(movies[i].rating)); } printf("========================\n"); printf(" 제목평점 ); printf("========================\n"); for(i=0;i<size;i++) printf("%s \t %f", movies[i].title, movies[i].rating); printf("\n========================\n"); free(movies); // 동적메모리공간해제 return 0;
도전문제 사용자가입력한데이터를파일에기록하는코드를추가해보자. 프로그램이시작할때파일에서데이터를읽어오는코드도추가하여보자.
Q & A
감사합니다.