2009 Spring Computer Engineering g Programming g 1 Lesson 14 - 제 17 장동적메모리와연결리스트 - 제14 장포인터활용 Lecturer: JUNBEOM YOO jbyoo@konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.
이번장에서학습할내용 동적할당메모리 연결리스트 이중포인터 포인터배열 다차원배열과포인터 main 함수의인수 이번단원에서는보다 advanced된기법으로서동적메모리의할당과다양한포인터의활용을학습하겠습니다. 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 동적메모리할당 if( pi == NULL ) // 반환값이 NULL인지검사 printf(" 동적메모리할당오류 \n"); exit(1); () 2 동적메모리사용 *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.cc 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.cc 1. #include <stdio.h> 2. #include <stdlib.h> 3. int main(void) 4. 5. int *pi; p; 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.cc 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으로초기화된메모리할당 항목단위로메모리를할당 ( 예 ) int *p; p = (int *)calloc(5, sizeof(int)); p p? calloc() 0? 0? 0? 0? 0 void *realloc(void *memblock, size_t size); malloc() realloc() 함수는할당하였던메모리블록의크기를변경 ( 예 ) int *p; p = (int *)malloc(5 * sizeof(int))); p = realloc(p, 7 * sizeof(int))); p p 10 realloc() 10 20 20 30 30 40 40 50 50?? 11
연결리스트 배열 (array) 장점 : 구현이간단하고빠르다 0 단점 : 크기가고정된다. 중간에서삽입, 삭제가어렵다. 1 2 3 4 5 6 7 8 9 연결리스트 (linked list) 각각의원소가포인터를사용하여다음원소의위치를가리킨다. A C D E B 메인메모리 12
연결리스트의장단점 중간에데이터를삽입, 삭제하는경우 A B N C D E A B C D E 메인메모리 메인메모리 데이터를저장할공간이필요할때마다동적으로공간을만들어서쉽게추가 구현이어렵고오류가나기쉽다. 13
연결리스트의구조 노드 (node) = 데이터필드 (data field)+ 링크필드 (link field) 연결리스트의노드는데이터필드와링크필드로이루어집니다. data link 헤드포인터 (head pointer): 첫번째노드를가리키는포인터 첫번째노드를가리키는포인터를헤드포인터라고하고맨마지막노드의링크필드는 NULL 입니다. plist 10 20 30 NULL NULL 40 NULL 50 NULL 14
자기참조구조체 자기참조구조체 (self-referential f l 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; p2->link = NULL; p1->link = p2; free(p1); free(p2); p1 p1 10 NULL 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 plist 10 20 30 NULL 2 1 pprev->link = pnew;// 2 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; plist 10 free(pcurr); pcurr 20 30 NULL 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
이중포인터 이중포인터 (double pointer): ) 포인터를가리키는포인터 int i = 100; // i 는 int 형변수 int *p = &i; // p 는 i 를가리키는포인터 int **q = &p; // q 는포인터 p 를가리키는이중포인터 24
이중포인터 // 이중포인터프로그램 #include <stdio.h> int main(void) int i = 100; int *p = &i; int **q = &p; *p = 200; printf("i=%d *p=%d **q=%d \n", i, *p, **q); **q = 300; printf("i=%d *p=%d **q=%d \n", i, *p, **q); return 0; i=200 *p=200 **q=200 i=300 *p=300 **q=300 25
예제 #2 // 이중포인터프로그램 #include <stdio.h> void set_proverb(char **q); int main(void) char *s = NULL; set_proverb(&s); printf("selected proverb = %s\n",s); return 0; void set_proverb(char **q) static char *str1="a friend in need is a friend indeed"; static char *str2="a little knowledge is a dangerous thing"; *q = str1; selected proverb = A friend in need is a friend indeed 26
포인터배열 포인터배열 (array of pointers): ) 포인터를모아서배열로만든것 int a = 10, b = 20, c = 30, d = 40, e = 50; int *pa[5] = &a, &b, &c, &d, &e ; 27
문자열배열 문자열배열 가장많이사용되는포인터배열 문자열들을효율적으로저장할수있다. char *fruits[ ] = "apple", "blueberry", "orange", melon" ; 28
문자열배열 vs 2 차원배열 문자열들을저장하는 2 차원배열 공간의낭비가발생할수있다. char fname[ ][10] = ; "apple", "blueberry", "orange", melon" 29
문자열상수의의미 문자열상수는문자열의시작번지를반환한다. 포인터배열의각원소들은이시작번지로초기화된다. 30
stringarray.c // 문자열배열 #include <stdio.h> int main(void) int i, n; char *fruits[ ] = "apple", "blueberry", "orange", "melon" ; n = sizeof(fruits)/sizeof(fruits[0]); // 배열원소개수계산 for(i = 0; i < n; i++) printf("%s \n", fruits[i]); return 0; apple blueberry orange melon 31
함수포인터 함수포인터 (function pointer): ) 함수를가리키는포인터 반환형 (* 함수포인터이름 )( 매개변수1, 매개변수2,...); 32
fp1.c // 함수포인터 #include <stdio.h> // 함수원형정의 int add(int, int); int sub(int, int); int main(void) int result; int (*pf)(int, int); // 함수포인터정의 pf = add; result = pf(10, 20); printf("10+20은 %d\n", result); // 함수포인터에함수 add() 의주소대입 // 함수포인터를통한함수 add() 호출 pf = sub; // 함수포인터에함수 sub() 의주소대입 result = pf(10, 20); // 함수포인터를통한함수 sub() 호출 printf("10-20은 %d\n", result); return 0; 33
fp1.c int add(int x, int y) return x+y; int sub(int x, int y) return x-y; 10+200 은 30 10-20은 -10 34
함수포인터의배열 반환형 (* 배열이름 [ 배열의 _ 크기 ])( 매개변수목록 ); int (*pf[5]) (int, int); 35
fp2.c // 함수포인터배열 #include <stdio.h> // 함수원형정의 void menu(void); int add(int x, int y); int sub(int x, int y); int mul(int x, int y); int div(int x, int y); void menu(void) printf("=====================\n"); printf("0. 덧셈 \n"); printf("1. 뺄셈 \n"); printf("2. 곱셈 \n"); printf("3. 나눗셈 \n"); printf("4. 종료 \n"); printf("=====================\n"); 36
fp2.c int main(void) int choice, result, x, y; // 함수포인터배열을선언하고초기화한다. int (*pf[4])(int, int) = add, sub, mul, div ; 함수포인터배열선언 while(1) menu(); printf(" 메뉴를선택하시오 :"); scanf("%d", &choice); if( choice < 0 choice >=4 ) break; printf("2 개의정수를입력하시오 :"); scanf("%d %d", &x, &y); result = pf[choice](x, y); // 함수포인터를이용한함수호출 printf(" 연산결과 = %d\n",result); return 0; 37
fp2.c int add(int x, int y) return x + y; int sub(int x, int y) return x - y; int mul(int x, int y) return x * y; int div(int x, int y) return x / y; ===================== 0. 덧셈 1. 뺄셈 2. 곱셈 3. 나눗셈 4. 종료 ===================== 메뉴를선택하시오 :2 2개의정수를입력하시오 :10 20 연산결과 = 200 ===================== 0. 덧셈 1. 뺄셈 2. 곱셈 3. 나눗셈 4. 종료 ===================== 메뉴를선택하시오 : 38
함수인수로서의함수포인터 함수포인터도인수로전달이가능하다. 39
fp2.c #include <stdio.h> #include <math.h> double f1(double k); double f2(double k); double formula(double (*pf)(double), int n); int main(void) printf("%f\n", formula(f1, 10)); printf("%f\n", formula(f2, 10)); double formula(double (*pf)(double), ) int n) int i; double sum = 0.0; for(i = 1; i < n; i++) sum += pf(i) * pf(i) + pf(i) + 1; return sum; 40
fp2.c double f1(double f(double k) return 1.0 / k; double f2(double k) return cos(k); 13.368736 12.716152 41
다차원배열과포인터 2 차원배열 int m[3][3] 1 행 ->2 행 ->3 행 ->... 순으로메모리에저장 ( 행우선방법 ) 하나의열 m m[0][0] m[0][0] m[0] m[0][1] m[0][1] 1 행 하나의행 m[0][0] m[0][0] ] m[0][1] m[0][1] ] 열 (column) m[0][2] m[0][2] ] m[0][2] m[0][2] m[1][0] m[1][0] m[1][1] m[1][1] m[1] m[1][0] m[1][0] m[1][1] m[1][1] m[1][2] m[1][2] m[1][2] m[1][2] m[2] m[2][0] m[2][0] m[2][1] m[2][1] 2행행m[2][2] m[2][2] (row) m[2][0] m[2][0] m[2][1] m[2][1] 3 행 m[2][2] m[2][2] 42
2 차원배열과포인터 배열이름 m 은 &m[0][0] m[0] 는 1행의시작주소 m[1] 은 2 행의시작주소... m m[0] m[0] m[0][0] m[0][0] m[0][1] m[0][1] m[0][2] m[0][2] m[1] m[1] m[1][0] m[1][0] m[1][1] m[1][1] m[1][2] m[1][2] m[2] m[2] m[2][0] m[2][0] m[2][1] m[2][1] m[2][2] m[2][2] 43
multi_array.c // 다차원배열과포인터 #include <stdio.h> int main(void) int m[3][3] = 10, 20, 30, 40, 50, 60, 70, 80, 90 ; printf("m = %p\n", m); printf("m[0] = %p\n", m[0]); printf("m[1] = %p\n", m[1]); printf("m[2] = %p\n", m[2]); printf("&m[0][0] = %p\n", &m[0][0]); printf("&m[1][0] = %p\n", &m[1][0]); printf("&m[2][0] = %p\n", &m[2][0]); return 0; m = 1245020 m[0] = 1245020 m[1] = 1245032 m[2] = 1245044 &m[0][0] = 1245020 &m[1][0] = 1245032 &m[2][0] = 1245044 44
2 차원배열과포인터연산 m 에대한연산의의미 m은 &m[0][0] m+1 은 m[1] m+2은 m[2] m[0] m[1] m[0][0] ] m[0][0] m[0][1] m[0][1] m[0][2] m[0][2] m[1][0] m[1][0] 1 행 m m+1 m[1][1] m[1][1] 2 행 m[1][2] [][ ] m[1][2] m[2] m[2][0] m[2][0] m+2 m[2][1] m[2][1] 3 행 m[2][2] m[2][2] 45
two_dim_array.c #include <stdio.h> int main(void) int m[3][3] = 10, 20, 30, 40, 50, 60, 70, 80, 90 ; printf("m = %p\n", m); printf("m+1 = %p\n", m+1); printf("m+2 = %p\n", m+2); printf("m[0] = %p\n", m[0]); printf("m[1] = %p\n", m[1]); printf("m[2] = %p\n", m[2]); return 0; m = 1245020 m+1 = 1245032 m+2 = 1245044 m[0] = 1245020 m[1] = 1245032 m[2] = 1245044 46
포인터를이용한배열원소방문 행의평균을구하는경우 double get_row_avg(int m[][cols], int r) int *p, *endp; double sum = 0.0; m[0][0] m[0][0] m[0][1 m[0][1] ] m[0][2] m[0][2] 열 (column) p = &m[r][0]; endp = &m[r][cols]; m[1][0] m[1][0] [][] m[1 m[1][1] [][] ][1 ] m[1 m[1][2] [][] ][2] 행while( p < endp ) sum += *p++; (row) sum /= COLS; m[2][0] m[2][0] m[3][0] m[3][0] m[2][1 m[2][1] ] m[3][1 m[3][1] ] m[2][2] m[2][2] m[3][2] m[3][2] return sum; p endp endp 47
포인터를이용한배열원소방문 전체원소의평균을구하는경우 double get_total_avg(int _ g( m[][cols]) ]) int *p, *endp; double sum = 0.0; m[0][0] m[0][0] m[0][1] m[0][1] m[0][2] m[0][2] 열 (column) p = &m[0][0]; endp = &m[rows-1][cols]; m[1 m[1 ][0] ][0] m[1][1] m[1][1] m[1][2] m[1][2] 행while( p < endp ) sum += *p++; (ro ow) m[2][0] m[2][0] [][] m[2][1] m[2][1] [][] m[2][2] m[2][2] [][] sum /= ROWS * COLS; m[3][0] m[3][0] m[3][1 m[3][1 ] ] m[3][2] m[3][2] return sum; p endp endp 48
void 포인터 순수하게메모리의주소만가지고있는포인터 가리키는대상물은아직정해지지않음 ( 예 ) void *vp; 다음과같은연산은모두오류이다. *vp; // 오류 *(int *)vp; // void형포인터를 int형포인터로변환한다. vp++; // 오류 vp--; // 오류 49
vp.c #include <stdio.h> int main(void) int a[] = 10, 20, 30, 40, 50 ; void *vp; vp = a; // 가능 vp = &a[2]; *vp = 35; vp++; *(int *)vp = 35; // 가능 // 오류 // 오류 // 가능 return 0; 50
main() 함수의인수 지금까지의 main() 함수형태 int main(void).. 외부로부터입력을받는 main() 함수형태 int main(int argc, char *argv[]).. 51
인수전달방법 C: \cprogram> mycopy src dt dst m y c c o o p y \0 \0 argv[0] s s r r c c \0 \0 argv[1] d s s t t \0 \0 3 3 argv[2] argc argv 배열 52
main_arg.carg #include <stdio.h> int main(int argc, char *argv[]) int i = 0; for(i = 0;i < argc; i++) printf(" 명령어라인에서 %d 번째문자열 = %s\n", i, argv[i]); return 0; Microsoft Windows XP [Version 5.1.2600] (C) Copyright 1985-2001 Microsoft Corp. c:\cprogram\mainarg\debug>mainarg src dst 명령어라인에서 0 번째문자열 =mainarg 명령어라인에서 1 번째문자열 =src 명령어라인에서 2 번째문자열 =dst c:\cprogram\mainarg\debug> 53
비주얼 C++ 프로그램인수입력방법 여기에프로그램인수들을넣으면된다. 54
mile2km.c #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) double mile, km; if( argc!= 2 ) printf(" 사용방법 : mile2km 거리 \n"); return 1; mile = atof(argv[1]); km = 1.609 * mile; printf(" 입력된거리는 %f km 입니다. \n", km); return 0; Microsoft Windows XP [Version 5.1.2600] (C) Copyright 1985-2001 Microsoft Corp. c:\cprogram\mainarg\debug>mainarg mainarg 10 입력된거리는 16.090000 km입니다. c:\cprogram\mainarg\debug> 55
Q&A 56